2026-07-23T05:17:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13729 2024-03-06T10:52:32Z ddc:004 open_access

Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing McCauley, Samuel edit distance approximate pattern matching approximate nearest neighbor similarity search locality-sensitive hashing 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 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. Previous approaches to this problem either rely on very large (superconstant) approximation ratios c, or very small search radii r. Outside of a narrow parameter range, these solutions are not competitive with trivially searching through all n strings. In this work we give a simple and easy-to-implement hash function that can quickly answer queries for a wide range of parameters. Specifically, our strategy can answer queries in time Õ(d3^rn^{1/c}). The best known practical results require c ≫ r to achieve any correctness guarantee; meanwhile, the best known theoretical results are very involved and difficult to implement, and require query time that can be loosely bounded below by 24^r. Our results significantly broaden the range of parameters for which there exist nontrivial theoretical bounds, while retaining the practicality of a locality-sensitive hash function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samuel McCauley 2021 Is Part Of LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2021.21 urn:nbn:de:0030-drops-137299 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.21 eng https://creativecommons.org/licenses/by/4.0/legalcode