Paper Info
Title
Hypergraph querying using structural indexing and layer-related-closure verification.
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.
Year
DOI
Venue
2016
10.1007/s10115-015-0829-4
Knowledge and Information Systems
Keywords
Field
DocType
Hypergraph matching, Data mining, Indexing, Pattern matching verification
Graph,Data mining,Graph indexing,Graph isomorphism,Computer science,Constraint graph,Hypergraph,Index set,Search engine indexing,Theoretical computer science,Search problem
Journal
Volume
Issue
ISSN
46
3
0219-3116
Citations 
PageRank 
References 
0
0.34
26
Authors
2
Name
Order
Citations
PageRank
Xinran Yu132.53
Turgay Korkmaz282759.69