Streaming algorithms for embedding and computing edit distance in the low distance regime

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331498" target="_blank" >RIV/00216208:11320/16:10331498 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/2897518.2897577" target="_blank" >http://dx.doi.org/10.1145/2897518.2897577</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2897518.2897577" target="_blank" >10.1145/2897518.2897577</a>

Result language
angličtina
Original language name
Streaming algorithms for embedding and computing edit distance in the low distance regime
Original language description
The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit flips needed for converting x into y. Whereas, the Hamming distance between x and y is the number of bit flips needed for converting x to y. In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. We show a randomized embedding with quadratic distortion. Namely, for any x,y satisfying that their edit distance equals k, the Hamming distance between the embedding of x and y is O(k2) with high probability. This improves over the distortion ratio of O( n * n) obtained by Jowhari (2012) for small values of k. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. We provide several applications for this embedding. Among our results we provide a one-pass (streaming) algorithm for edit distance running in space O(s) and computing edit distance exactly up-to distance s1/6. This algorithm is based on kernelization for edit distance that is of independent interest.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA14-10003S" target="_blank" >GA14-10003S: Restricted computations: Algorithms, models, complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
ISBN
978-1-4503-4132-5
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
712-725
Publisher name
ACM 2016
Place of publication
New York, NY, USA
Event location
Cambridge, MA, USA
Event date
Jun 18, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)