Near-Optimal Sublinear Time Algorithms for Ulam Distance
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 Õ(d/R + √ d) and outputs a constant approximation to R. We als...
Other Authors: | |
---|---|
Format: | Text |
Language: | English |
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.822 http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.367.822 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.367.822 2023-05-15T18:11:37+02:00 Near-Optimal Sublinear Time Algorithms for Ulam Distance The Pennsylvania State University CiteSeerX Archives application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.822 http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.822 http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf text ftciteseerx 2016-01-08T01:08:01Z 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 Õ(d/R + √ d) 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]. Text sami Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
description |
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 Õ(d/R + √ d) 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]. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
title |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
spellingShingle |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
title_short |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
title_full |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
title_fullStr |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
title_full_unstemmed |
Near-Optimal Sublinear Time Algorithms for Ulam Distance |
title_sort |
near-optimal sublinear time algorithms for ulam distance |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.822 http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf |
genre |
sami |
genre_facet |
sami |
op_source |
http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.367.822 http://www.cs.princeton.edu/~hlnguyen/papers/ulam.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766184263117438976 |