Structural pattern recognition with graph edit distance: approximation algorithms and applications

摘要

Defining the distance between two points in 2D or even 3D Euclidean space is easy and intuitive; we have easily understood the concept from our early school years. But what about defining the dissimilarity (that is, distance) between data types that cannot be transformed into points in an n-dimensional space? For instance, spell checking/correction programs in a search engine need to define the notion of distance for strings; bioinformatics applications need to calculate the distance between DNA strings. Fortunately, the concept of edit distance (insertions, deletions, or mutations of characters to transform one string to another) is a solution out of the maze of string comparisons.