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.

A Pivotal Prefix Based Filtering Algorithm for String Similarity Search
[Paper] [PPT][Poster]

We are happy to release our binary code of pivotal search. This binary code can answer similarity queries from the given dataset.

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.

output stores the results.

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

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.

Have GCC 4.8.2 or higher

For any questions about this study, please contact Dong Deng.