Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing

Samuel McCauley

Edit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread database applications. The goal of the problem is to preprocess…