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.
No takes yet. Share an insight, caveat, or question.
Ostrovsky et al. (2007) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: