Almost Linear Size Edit Distance Sketch

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10492979" target="_blank" >RIV/00216208:11320/24:10492979 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1145/3618260.3649783" target="_blank" >https://doi.org/10.1145/3618260.3649783</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3618260.3649783" target="_blank" >10.1145/3618260.3649783</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Almost Linear Size Edit Distance Sketch

Popis výsledku v původním jazyce

We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string rho and computes a sketch sk(rho)(x;k), which is a compressed version of x. The recovery algorithm is given two sketches sk(rho)(x;k) and sk(rho)(y;k) as well as the public random string rho used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) &gt; k will output large. The size of the sketch output by the sketching algorithm on input x is k2(O(root log(n)loglog(n))) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS2021), and Bhattacharya and Koucky (STOC2023).

Název v anglickém jazyce

Almost Linear Size Edit Distance Sketch

Popis výsledku anglicky

We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string rho and computes a sketch sk(rho)(x;k), which is a compressed version of x. The recovery algorithm is given two sketches sk(rho)(x;k) and sk(rho)(y;k) as well as the public random string rho used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) &gt; k will output large. The size of the sketch output by the sketching algorithm on input x is k2(O(root log(n)loglog(n))) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS2021), and Bhattacharya and Koucky (STOC2023).

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the Annual ACM Symposium on Theory of Computing

ISBN

979-8-4007-0383-6

ISSN

0737-8017

e-ISSN

—

Počet stran výsledku

12

Strana od-do

956-967

Název nakladatele

Association for Computing Machinery

Místo vydání

New York, N.Y.

Místo konání akce

Vancouver

Datum konání akce

24. 6. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001254099900087