Oblivious string embeddings and edit distance approximations
Tuğkan Batu, Funda Ergün, S. Cenk Şahinalp · 2006
We introduce an oblivious embedding that maps any string of length n to a string of length at most n/r for any user specified value of r. For any given r, our embedding provides a distortion of O(r for some = o(1) under edit distance, which we prove to be (almost) optimal. The embedding can be computed in O(2 n) time. We also