Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDE.2012.28
Title: An efficient graph indexing method
Authors: Wang, X.
Ding, X.
Tung, A.K.H. 
Ying, S.
Jin, H.
Issue Date: 2012
Source: Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H. (2012). An efficient graph indexing method. Proceedings - International Conference on Data Engineering : 210-221. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDE.2012.28
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. © 2012 IEEE.
Source Title: Proceedings - International Conference on Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/41250
ISSN: 10844627
DOI: 10.1109/ICDE.2012.28
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

34
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

22
checked on Nov 19, 2017

Page view(s)

66
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.