2020/07/28 by Brakensiek, Joshua, Charikar, Moses, Rubinstein, Aviad
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.14368
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, previous work showed that in certain regimes it is possible to solve the following \em gap edit distance problem in sub-linear time: distinguish between inputs of distance ≤ k and >k2. Our main result is a very simple algorithm for this benchmark that runs in time O(n/√(k)), and in particular settles the open problem of obtaining a truly sublinear time for the entire range of relevant k. Building on the same framework, we also obtain a k-vs-k2 algorithm for the one-sided preprocessing model with O(n) preprocessing time and O(n/k) query time (improving over a recent O(n/k+k2)-query time algorithm for the same problem [GRS'20].