An efficient graph indexing method
Date
2012
Authors
Wang, X.
Ding, X.
Tung, A.K.H.
Ying, S.
Jin, H.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings - International Conference on Data Engineering, 2012, iss.6228085, pp.210-221
Statement of Responsibility
Conference Name
IEEE 28th International Conference on Data Engineering, ICDE 2012 (1 Apr 2012 - 5 Apr 2012 : Arlington, US)
Abstract
Graphs are popular models for representing complex structure data and similarity search for graphs has become a fundamental research problem. Many techniques have been proposed to support similarity search based on the graph edit distance. However, they all suffer from certain drawbacks: high computational complexity, poor scalability in terms of database size, or not taking full advantage of indexes. To address these problems, in this paper, we propose SEGOS, an indexing and query processing framework for graph similarity search. First, an effective two-level index is constructed off-line based on sub-unit decomposition of graphs. Then, a novel search strategy based on the index is proposed. Two algorithms adapted from TA and CA methods are seamlessly integrated into the proposed strategy to enhance graph search. More specially, the proposed framework is easy to be pipelined to support continuous graph pruning. Extensive experiments are conducted on two real datasets to evaluate the effectiveness and scalability of our approaches.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2012 IEEE