A partition-based approach to structure similarity search
Open Access
- 1 November 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 7 (3) , 169-180
Abstract
Graphs are widely used to model complex data in many applications, such as bioinformatics, chemistry, social networks, pattern recognition, etc. A fundamental and critical query primitive is to efficiently search similar structures in a large collection of graphs. This paper studies the graph similarity queries with edit distance constraints. Existing solutions to the problem utilize fixed-size overlapping substructures to generate candidates, and thus become susceptible to large vertex degrees or large distance thresholds. In this paper, we present a partition-based approach to tackle the problem. By dividing data graphs into variable-size non-overlapping partitions, the edit distance constraint is converted to a graph containment constraint for candidate generation. We develop efficient query processing algorithms based on the new paradigm. A candidate pruning technique and an improved graph edit distance algorithm are also developed to further boost the performance. In addition, a cost-aware graph partitioning technique is devised to optimize the index. Extensive experiments demonstrate our approach significantly outperforms existing approaches.Keywords
This publication has 18 references indexed in Scilit:
- Efficient processing of graph similarity queries with edit distance constraintsThe VLDB Journal, 2013
- NeMaProceedings of the VLDB Endowment, 2013
- TreeSpan2012
- Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching2011
- SAPPERProceedings of the VLDB Endowment, 2010
- Comparing starsProceedings of the VLDB Endowment, 2009
- Taming verification hardnessProceedings of the VLDB Endowment, 2008
- Substructure similarity search in graph databases2005
- On the editing distance between undirected acyclic graphs and related problems1995
- Inexact graph matching for structural pattern recognitionPattern Recognition Letters, 1983