A Pivotal Prefix Based Filtering Algorithm for String Similarity Search

Dong Deng, Guoliang Li, Jiannan Wang

Abstract

We study the string similarity search problem with edit-distance constraints, which, given a set of data strings and a query string, finds the similar strings to the query. Existing algorithms use a signature-based framework. They first generate signatures for each string and then prune the dissimilar strings which have no common signatures to the query. However existing methods involve large numbers of signatures and many signatures are unnecessary. Reducing the number of signatures not only increases the pruning power but also decreases the filtering cost. To address this problem, we propose a novel pivotal prefix filter which significantly reduces the number of signatures. We prove the pivotal filter achieves larger pruning power and less filtering cost than state-of-the-art filters. We develop a dynamic programming method to select high-quality pivotal prefix signatures to prune dissimilar strings with non-consecutive errors to the query. We propose an alignment filter that considers the alignments between signatures to prune large numbers of dissimilar pairs with consecutive errors to the query. Experimental results on three real datasets show that our method achieves high performance and outperforms the state-of-the-art methods by an order of magnitude.

Code

Overview

We are happy to release our binary code of pivotal search. This binary code can answer similarity queries from the given dataset.For further information please send an email to Dong Deng.

Input

Run pivotal similarity search from command line:

Description:

• filename is the file name of string collections, where strings are separated by \n.

• queryfile is the file name of queries, where queries are separated by \n.

• threshold is the edit-distance threshold.

• q is the gram length.

• num (optional) is the number of strings loaded from the file. Default is reading all strings.

• output stores the result pairs.

Output

pivotal search prints three lines for each result (data, query):

for example

Description:

The first line consists of the data string id and its content. The second line consists of the content of the query string and its id which is the line number of it in the query file. The third line is a blank line. One example output for the result (pvldb, vldb) is shown on the bottom.

Requirement

Have GCC 4.8.2 or higher

Download

• code

• code+datasets

Contact

If you have any questions about this study, please feel free to contact Dong Deng.