A pivotal prefix based filtering algorithm for string similarity search
A pivotal prefix based filtering algorithm for string similarity search
复制标题
DOI：
10.1145/2588555.2593675
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Dong Deng;Guoliang Li;Jianhua Feng
中科院分区：
文献类型：
--
作者：
Dong Deng;Guoliang Li;Jianhua Feng
研究了具有编辑距离约束的字符串相似性搜索问题，即给定一组数据串和一个查询串，查找与查询相似的字符串。现有的算法使用基于签名的框架。它们首先为每个字符串生成签名，然后删除与查询没有共同签名的不相似字符串。然而，现有的方法涉及大量的签名和许多签名是不必要的。减少签名的数量不仅增加了剪枝能力，而且降低了过滤成本。为了解决这个问题，我们提出了一种新的关键前缀过滤器，显着减少了签名的数量。我们证明了关键过滤器实现更大的修剪功率和更少的过滤成本比国家的最先进的过滤器。我们开发了一个动态规划方法来选择高质量的关键前缀签名修剪不相似的字符串与非连续的错误查询。我们提出了一个对齐过滤器，认为签名之间的对齐修剪大量的连续错误的查询不同的对。在三个真实的数据集上的实验结果表明，该方法具有很高的性能，比现有的方法提高了一个数量级。
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.