Efficient Approximation of Edit Distance

The similarity between two strings is often measured by some variant of edit distance, depending on the intended application. But even the basic version of this distance, which is simply the minimum number of character insertions, deletions and substitutions needed to transform one string to the other, presents remarkable algorithmic challenges.

This talk will examine the task of approximating the basic edit distance between two strings, starting with the classical RAM model and moving on to computational models which impose further constraints, such as the query complexity model and the sketching model. Beyond their concrete applications, these investigations provide a wealth of information about the problem, teaching us state of the art techniques and uncovering the limitations of certain methodologies. We will then come full circle with improved algorithms for the classical RAM model. During this journey, we may encounter special cases like permutation strings, whose patterns are all distinct, and smoothed instances, which are a mixture of worst-case and average-case inputs.

Finally, we shall discuss known gaps and open problems in the area, including variants of the basic edit distance, such as allowing block moves, or edit distance between trees, and hopefully touch upon related computational problems like nearest-neighbor search.

Authors and Affiliations

1. Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

   Robert Krauthgamer

Editors and Affiliations

1. Faculty of Industrial Engineering and Management Technion, Technion Institute of Technology, Bloomfield Hall 308, 32000, Haifa, Israel

   Oren Kurland

2. Bar-Ilan University, Israel

   Moshe Lewenstein

3. Department of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel

   Ely Porat

Reprints and permissions

© 2013 Springer-Verlag Berlin Heidelberg

Policies and ethics