Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10465184" target="_blank" >RIV/00216208:11320/23:10465184 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3564246.3585239" target="_blank" >https://doi.org/10.1145/3564246.3585239</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3564246.3585239" target="_blank" >10.1145/3564246.3585239</a>
Alternative languages
Result language
angličtina
Original language name
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Original language description
In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k^2) for edit distance, and also a rolling sketch for edit distance of size O(k^2). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023
ISBN
978-1-4503-9913-5
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
219-232
Publisher name
ACM
Place of publication
USA
Event location
Orlando, FL, USA
Event date
Jun 20, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—