The Computational Hardness of Estimating Edit Distance.
Alexandr AndoniRobert KrauthgamerPublished in: SIAM J. Comput. (2010)
Keyphrases
- edit distance
- distance measure
- approximate string matching
- edit operations
- graph matching
- similarity measure
- string matching
- string edit distance
- approximate matching
- distance function
- string similarity
- graph edit distance
- levenshtein distance
- longest common subsequence
- tree structured data
- dynamic programming
- computational complexity
- dissimilarity measure
- tree edit distance
- distance computation
- worst case
- data sets
- np hard
- object recognition
- pattern recognition
- neural network