Edit distance in near-linear time: It's a constant factor
A Andoni, NS Nosatzki - 2020 IEEE 61st Annual Symposium on …, 2020 - ieeexplore.ieee.org
We present an algorithm for approximating the edit distance between two strings of length n
in time n 1+ ε, for any, up to a constant factor. Our result completes a research direction set …
in time n 1+ ε, for any, up to a constant factor. Our result completes a research direction set …
Theoretical analysis of edit distance algorithms
P Medvedev - Communications of the ACM, 2023 - dl.acm.org
Theoretical Analysis of Edit Distance Algorithms Page 1 EDIT DISTANCE—A CLASSICAL
problem in computer science—has received ongoing attention from both practitioners and …
problem in computer science—has received ongoing attention from both practitioners and …
Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing
We introduce fast-decodable indexing schemes for edit distance which can be used to
speed up edit distance computations to near-linear time if one of the strings is indexed by an …
speed up edit distance computations to near-linear time if one of the strings is indexed by an …
Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation
W Kuszmaul - arXiv preprint arXiv:1904.09690, 2019 - arxiv.org
Dynamic time warping distance (DTW) is a widely used distance measure between time
series. The best known algorithms for computing DTW run in near quadratic time, and …
series. The best known algorithms for computing DTW run in near quadratic time, and …
Improved algorithms for edit distance and LCS: beyond worst case
Edit distance and longest common subsequence are among the most fundamental problems
in combinatorial optimization. Recent developments have proven strong lower bounds …
in combinatorial optimization. Recent developments have proven strong lower bounds …
Approximate similarity search under edit distance using locality-sensitive hashing
S McCauley - arXiv preprint arXiv:1907.01600, 2019 - arxiv.org
Edit distance similarity search, also called approximate pattern matching, is a fundamental
problem with widespread database applications. The goal of the problem is to preprocess …
problem with widespread database applications. The goal of the problem is to preprocess …
Near-linear time edit distance for indel channels
A Ganesh, A Sy - arXiv preprint arXiv:2007.03040, 2020 - arxiv.org
We consider the following model for sampling pairs of strings: $ s_1 $ is a uniformly random
bitstring of length $ n $, and $ s_2 $ is the bitstring arrived at by applying substitutions …
bitstring of length $ n $, and $ s_2 $ is the bitstring arrived at by applying substitutions …
A simple sublinear algorithm for gap edit distance
We study the problem of estimating the edit distance between two $ n $-character strings.
While exact computation in the worst case is believed to require near-quadratic time …
While exact computation in the worst case is believed to require near-quadratic time …
Theoretical analysis of edit distance algorithms: an applied perspective
P Medvedev - arXiv preprint arXiv:2204.09535, 2022 - arxiv.org
Given its status as a classic problem and its importance to both theoreticians and
practitioners, edit distance provides an excellent lens through which to understand how the …
practitioners, edit distance provides an excellent lens through which to understand how the …
Approximating lcs and alignment distance over multiple sequences
We study the problem of aligning multiple sequences with the goal of finding an alignment
that either maximizes the number of aligned symbols (the longest common subsequence …
that either maximizes the number of aligned symbols (the longest common subsequence …