Proceedings of the VLDB Endowment · 2013 · 60 citations · 19 references
ComputingBioinformaticsComputer ScienceData StructuresDatabasesStructural BioinformaticsData Structure AlgorithmsGraph AlgorithmsGraph MiningSearching AlgorithmsCandidate GenerationEdit DistanceGraph PartitioningGraph SearchGraph SimilarityGraph Similarity SearchPruningSubstructure Search
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.
19
A min-max cut algorithm for graph partitioning and data clustering
Chris Ding, Xiaofeng He, Hongyuan Zha et al. · 2002 · 831 citations
Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang et al. · Proceedings of the VLDB Endowment · 2009 · 403 citations