Oblivious string embeddings and edit distance approximations

Abstract

We introduce an oblivious embedding that maps strings of length n under edit distance to strings of length at most n/r under edit distance for any value of parameter r. For any given r, our embedding provides a distortion of Õ(r1+μ) for some μ = o(1), which we prove to be (almost) optimal. The embedding can be computed in Õ(21/μn) time.We also show how to use the main ideas behind the construction of our embedding to obtain an efficient algorithm for approximating the edit distance between two strings. More specifically, for any 1 > ε ≥ 0, we describe an algorithm to compute the edit distance D(S, R) between two strings S and R of length n in time Õ(n1+ε), within an approximation factor of min{n1-ε/3+o(1), (D(S, R/nε)1/2+o(1)}. For the case of ε = 0, we get a Õ(n)-time algorithm that approximates the edit distance within a factor of min{n1/3+o(1), D(S, R)1/2+o(1)}, improving the recent result of Bar-Yossef et al. [2].