Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/38881
Title: Comparing stars: On approximating graph edit distance
Authors: Zeng, Z.
Tung, A.K.H. 
Wang, J.
Feng, J.
Zhou, L.
Issue Date: 2009
Source: Zeng, Z.,Tung, A.K.H.,Wang, J.,Feng, J.,Zhou, L. (2009). Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment 2 (1) : 25-36. ScholarBank@NUS Repository.
Abstract: Graph data have become ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measures to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit distance computation is NP-Hard in general. Accordingly, in this paper we introduce three novel methods to compute the upper and lower bounds for the edit distance between two graphs in polynomial time. Applying these methods, two algorithms AppFull and AppSub are introduced to perform different kinds of graph search on graph databases. Comprehensive experimental studies are conducted on both real and synthetic datasets to examine various aspects of the methods for bounding graph edit distance. Result shows that these methods achieve good scalability in terms of both the number of graphs and the size of graphs. The effectiveness of these algorithms also confirms the usefulness of using our bounds in filtering and searching of graphs. © 2009 VLDB Endowment.
Source Title: Proceedings of the VLDB Endowment
URI: http://scholarbank.nus.edu.sg/handle/10635/38881
ISSN: 21508097
Appears in Collections:Staff Publications

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

Page view(s)

103
checked on Dec 15, 2017

Google ScholarTM

Check


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