Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422308" target="_blank" >RIV/00216208:11320/20:10422308 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=wrre.me35f" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=wrre.me35f</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

Popis výsledku v původním jazyce

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time (O) over tildeO(n(2-2/7)) that approximates the edit distance within a constant factor.

Název v anglickém jazyce

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

Popis výsledku anglicky

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time (O) over tildeO(n(2-2/7)) that approximates the edit distance within a constant factor.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

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

Rok uplatnění

2020

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 periodika

Journal of the ACM

ISSN

0004-5411

e-ISSN

—

Svazek periodika

67

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

36

Kód UT WoS článku

000595522200005

EID výsledku v databázi Scopus

2-s2.0-85097045603