Constant factor approximations to edit distance on far input pairs in nearly linear time.

Michal Koucký Michael E. Saks

Published 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