Edit Distance Evaluation on Graph Structures
| dc.contributor.author | ZENG, Zhiping | en_US |
| dc.contributor.author | TUNG, Anthony K.H. | en_US |
| dc.contributor.author | WANG, Jianyong | en_US |
| dc.contributor.author | ZHOU, Lizhu | en_US |
| dc.date.accessioned | 2008-11-20T09:40:36Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:09Z | |
| dc.date.available | 2008-11-20T09:40:36Z | en_US |
| dc.date.available | 2017-01-23T07:00:09Z | |
| dc.date.issued | 2008-06-19 | en_US |
| dc.description.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 ..... | en_US |
| dc.format.extent | 345564 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2824 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRA6/08 | en_US |
| dc.title | Edit Distance Evaluation on Graph Structures | en_US |
| dc.type | Technical Report | en_US |