String Similarity Search: A Hash-Based Approach

String similarity search is a fundamental query that has been widely used for DNA sequencing, error-tolerant query auto-completion, and data cleaning needed in database, data warehouse, and data mining. In this paper, we study string similarity search based on edit distance that is supported by many database management systems such as <italic>Oracle </italic> and <italic>PostgreSQL</italic>. Given the edit distance, <inline-formula><tex-math notation="LaTeX"> ${\mathsf {ed}} (s,t)$</tex-math><alternatives><inline-graphic xlink:href="yu-ieq1-2756932.gif"/></alternatives> </inline-formula>, between two strings, <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq2-2756932.gif"/></alternatives></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$t$</tex-math><alternatives><inline-graphic xlink:href="yu-ieq3-2756932.gif"/></alternatives> </inline-formula>, the string similarity search is to find every string <inline-formula><tex-math notation="LaTeX">$t$ </tex-math><alternatives><inline-graphic xlink:href="yu-ieq4-2756932.gif"/></alternatives></inline-formula> in a string database <inline-formula><tex-math notation="LaTeX">$D$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq5-2756932.gif"/></alternatives></inline-formula> which is similar to a query string <inline-formula><tex-math notation="LaTeX">$s$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq6-2756932.gif"/></alternatives></inline-formula> such that <inline-formula> <tex-math notation="LaTeX">${\mathsf {ed}} (s, t) \leq \tau$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq7-2756932.gif"/></alternatives></inline-formula> for a given threshold <inline-formula><tex-math notation="LaTeX">$\tau$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq8-2756932.gif"/></alternatives></inline-formula>. In the literature, most existing work takes a filter-and-verify approach, where the filter step is introduced to reduce the high verification cost of two strings by utilizing an index built offline for <inline-formula><tex-math notation="LaTeX">$D$</tex-math> <alternatives><inline-graphic xlink:href="yu-ieq9-2756932.gif"/></alternatives></inline-formula>. The two up-to-date approaches are prefix filtering and local filtering. In this paper, we study string similarity search where strings can be either short or long. Our approach can support long strings, which are not well supported by the existing approaches due to the size of the index built and the time to build such index. We propose two new hash-based labeling techniques, named <inline-formula><tex-math notation="LaTeX">$\mathsf {OX}$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq10-2756932.gif"/></alternatives></inline-formula> label and <inline-formula> <tex-math notation="LaTeX">$\mathsf {XX}$</tex-math><alternatives><inline-graphic xlink:href="yu-ieq11-2756932.gif"/> </alternatives></inline-formula> label, for string similarity search. We assign a hash-label, <inline-formula> <tex-math notation="LaTeX">${\mathsf {H}} _s$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq12-2756932.gif"/></alternatives></inline-formula>, to a string <inline-formula> <tex-math notation="LaTeX">$s$</tex-math><alternatives><inline-graphic xlink:href="yu-ieq13-2756932.gif"/> </alternatives></inline-formula>, and prune the dissimilar strings by comparing two hash-labels, <inline-formula> <tex-math notation="LaTeX">${\mathsf {H}} _s$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq14-2756932.gif"/></alternatives></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {H}} _t$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq15-2756932.gif"/></alternatives></inline-formula>, for two strings <inline-formula> <tex-math notation="LaTeX">$s$</tex-math><alternatives><inline-graphic xlink:href="yu-ieq16-2756932.gif"/> </alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$t$</tex-math><alternatives> <inline-graphic xlink:href="yu-ieq17-2756932.gif"/></alternatives></inline-formula> in the filter step. The key idea is to take the dissimilar bit-patterns between two hash-labels. We discuss our hash-based approaches, address their pruning power, and give the algorithms. Our hash-based approaches achieve high efficiency, and keep its index size and index construction time one order of magnitude smaller than the existing approaches in our experiment at the same time.