SINGS: Similarity Search in Large Graph Databases
No Thumbnail Available
Date
2010-06-29T01:55:49Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Graphs are popular models for representing complex structured data and similarity search for graphs has become a fundamental research problem. Many techniques have been proposed to support similarity search on graphs based on the graph edit distance. However, they all suffer from certain drawbacks: high computational complexity, poor scalability in terms of the number of graphs and the size of the graph, or
not taking full advantage of indexes. To address these problems, in this paper, we propose SINGS, an indexing and query processing framework for graph similarity search. An effective two-level index based on star structures is constructed and a novel search strategy based on the new indexing structure is also proposed. Two algorithms adapted from the TA and CA algorithms are seamlessly integrated into this proposed strategy for speeding up graph search. Extensive experiments are conducted on both real and
synthetic datasets to evaluate the effectiveness and scalability of our approaches.