Almost Linear Size Edit Distance Sketch

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Almost Linear Size Edit Distance Sketch

Original language description

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).

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2024

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 Annual ACM Symposium on Theory of Computing

ISBN

979-8-4007-0383-6

ISSN

0737-8017

e-ISSN

—

Number of pages

12

Pages from-to

956-967

Publisher name

Association for Computing Machinery

Place of publication

New York, N.Y.

Event location

Vancouver

Event date

Jun 24, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001254099900087