Low distortion embeddings for edit distance.
Rafail Ostrovsky, Yuval Rabani
Abstract:
We show that $\{0,1\}^d$ endowed with edit distance embeds into $\ell_1$ with distortion $2^{O\left(\sqrt{\log d\log\log d}\right)}$. We further show efficient implementations 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.
comment: J. ACM 54(5): (2007). Preliminary version in Proceedings of (STOC-2005).
Fetch PostScript file of the paper Fetch PDF file of the paper