Near-Optimal Sublinear Time Algorithms for Ulam Distance
Lists
Only you see this
Abstract
We give near-tight bounds for estimating the edit distance between two non-repetitive strings (Ulam distance) with constant approximation, in sub-linear time. For two strings of length d and at edit distance R, our algorithm runs in time and outputs a constant approximation to R. We also prove a matching lower bound (up to logarithmic terms). Both upper and lower bounds are improvements over previous results from, respectively, [Andoni-Indyk-Krauthgamer, SODA'09] and [Batu-Ergun-Kilian-Magen-Raskhodnikova-Rubinfeld-Sami, STOC'03].
BibTeX
@inproceedings{andoni2010near,
author = {Alexandr Andoni and Huy L. Nguyen},
title = {{Near-Optimal Sublinear Time Algorithms for Ulam Distance}},
booktitle = {SODA},
year = {2010},
doi = {10.1137/1.9781611973075.8},
}Loading related content...