String Similarity Joins and Search Under Edit Distance

As one of the most important distance metrics, edit distance can reflect noise and errors in sequence data and thus has various applications in data cleaning and integration, databases, bioinformatics, collaborative filtering, and natural language processing. On the other hand, edit distance is also difficult to compute and estimate, which draws both theorists’ and practitioners’ interest for decades. In this thesis, we will investigate several of the most critical problems related to edit distance and propose algorithms that are efficient in practice and have provable theoretical guarantees. We summarize our contributions as follows: