Low distortion embeddings for edit distance
Rafail Ostrovsky, Yuval Rabani · Journal of the ACM · 2007
We show that {0, 1} d endowed with edit distance embeds into ℓ 1 with distortion 2 O (√log d log log d ). We further show efficient implementation of the embedding that yield solutions to various computational problems involving edit distance. These include sketching, communication complexity, nearest neighbor search. For all these problems, we improve upon previous bounds.