T.Batu, "Oblivious String Embeddings and Edit Distance Approximations"
  • FENS
  • T.Batu, "Oblivious String Embeddings and Edit Distance Approximations"

You are here

                              Faculty of Engineering and Natural Sciences




Oblivious String Embeddings and Edit Distance Approximations

Tuğkan Batu

London School of Economics

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+\mu) for some \mu=o(1), which we prove to be (almost) optimal. The embedding can be computed in Õ(21/\mun) 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> \epsilon > 0, we describe an algorithm to compute the edit distance ed(S,R) between two strings S and R of length n in time Õ(n1+\epsilon), within an approximation factor of min{n(1-\epsilon)/3+o(1),(ed(S,R) n-\epsilon)1/2+o(1)}. For the case of \epsilon=0, we get a Õ(n)-time algorithm that approximates the edit distance within a factor of min{n1/3+o(1), ed(S,R)1/2+o(1)}, improving the recent result of Bar-Yossef et al..

Joint work with Funda Ergün and Cenk Şahinalp.

Short Bio:
Tuğkan Batu received his Ph.D. from Cornell University in 2001. He held Postdoctoral Fellow positions at the University of Pennsylvania, the University of Texas at Austin, and Simon Fraser University. Currently, he is a Lecturer in the Department of Mathematics at the London School of Economics. 

December 22, 2006, 14:40, FENS L035