Hypergraph querying using structural indexing and layer-related-closure verification. Issue 3 (March 2016)

• Record Type: Journal Article
• Authors: Yu, Xinran; Korkmaz, Turgay
• Is Part Of: Knowledge and information systems. Volume 46:Issue 3(2016:Mar.)
• Page Start: 537
• Page End: 565
• Publication Date: 2016-03
• Subjects: Hypergraph matching -- Data mining -- Indexing -- Pattern matching verification; Expert systems (Computer science) -- Periodicals; Information storage and retrieval systems -- Periodicals; 006.33
• DOI: 10.1007/s10115-015-0829-4
• Languages: English
• ISSNs: 0219-1377

Abstract

Abstract Graph indexing and querying mechanisms have been receiving significant attention due to their importance in analyzing the growing graph datasets in many domains. Although much work has been done in the context of simple graphs, they are not directly applicable to hypergraphs that represent more complex relationships in various applications. The key problem here is to search a given subhypergraph query in a larger hypergraph dataset. This search problem is known to be NP-hard as it is related to graph isomorphism. To solve this search problem in an efficient manner, we first create an index set by extracting the common subhypergraph structures from the given hypergraph dataset. Upon receiving a query, we use the same indexing techniques and create a query index set from the given subhypergraph. Utilizing both indices, we identify the possible locations of the query in the hypergraph dataset. We then start the subhypergraph search to verify whether the query really appears at each location by using an accelerated verification mechanism called layer-related-closure method. Through experiments on a real hypergraph dataset and random datasets, we demonstrate the efficiency and effectiveness of hypergraph indexing and our verification method.