Edit Distance Evaluation on Graph Structures
No Thumbnail Available
Date
2008-06-19
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Graph data has became ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measure to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit dis- tance computation is NP-Hard in general and is unlikely to be approximated within a polynomial time computable fac- tor f(n) in polynomial time. 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, three algorithms AppFull, ExactSub and AppSub are introduced to per- form 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 .....