Constant factor approximations to edit distance on far input pairs in nearly linear time.
Michal KouckýMichael E. SaksPublished in: CoRR (2019)
Keyphrases
- edit distance
- constant factor
- string similarity
- approximation algorithms
- similarity join
- worst case
- edit operations
- similarity measure
- graph matching
- lower bound
- levenshtein distance
- normalized edit distance
- graph edit distance
- distance function
- string edit distance
- dynamic programming
- minimum cost
- string matching
- approximate matching
- distance measure
- pairwise
- sample complexity
- data sets
- finite alphabet
- special case
- upper bound
- query processing
- text classification