Efficient Graph Similarity Search Over Large Graph Databases

Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs g in the graph database D that approximately match the query graph q, rather than exact graph matching. In this paper, we study the problem of graph similarity search, w...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2015-04, Vol.27 (4), p.964-978
Main Authors: Zheng, Weiguo, Zou, Lei, Lian, Xiang, Wang, Dong, Zhao, Dongyan
Format: Article
Language:English
Subjects:
Chemicals
Compounds
Graph matching
Graphs
Heuristic
Indexes
Lower bounds
Partitioning algorithms
Pruning
Query processing
Search problems
Searching
Similarity
Transforms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs g in the graph database D that approximately match the query graph q, rather than exact graph matching. In this paper, we study the problem of graph similarity search, which retrieves graphs that are similar to a given query graph under the constraint of graph edit distance. We propose a systematic method for edit-distance based similarity search problem. Specifically, we derive two lower bounds, i.e., partition-based and branch-based bounds, from different perspectives. More importantly, a hybrid lower bound incorporating both ideas of the two lower bounds is proposed, which is theoretically proved to have higher (at least not lower) pruning power than using the two lower bounds together. We also present a uniform index structure, namely u-tree, to facilitate effective pruning and efficient query processing. Extensive experiments confirm that our proposed approach outperforms the existing approaches significantly, in terms of both the pruning power and query response time.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2014.2349924