Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
share
Edit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread applications. The goal of the problem is to preprocess n strings of length d to quickly answer queries q of the form: if there is a database string within edit distance r of q, return a database string within edit distance cr of q. A data structure solving this problem is analyzed using two criteria: the amount of extra space used in preprocessing, and the expected time to answer a query. Previous approaches to this problem have either used trie-based methods, which give exact solutions at the cost of expensive queries, or embeddings, which only work for large (superconstant) values of c. In this work we achieve the first bounds for any approximation factor c, via a simple and easy-to-implement hash function. This gives a running time of Õ(d3^rn^1/c), with space Õ(3^r n^1 + 1/c + dn). We show how to apply these ideas to the closely-related Approximate Nearest Neighbor problem for edit distance, obtaining similar time bounds.
READ FULL TEXT