Asymmetric signature schemes for efficient exact edit similarity query processing
Asymmetric signature schemes for efficient exact edit similarity query processing
复制标题
DOI：
10.1145/2508020.2508023
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Jianbin Qin;Wei Wang-;Chuan Xiao;Yifei Lu;Xuemin Lin;Haixun Wang
中科院分区：
文献类型：
--
作者：
Jianbin Qin;Wei Wang-;Chuan Xiao;Yifei Lu;Xuemin Lin;Haixun Wang
给定查询字符串Q，编辑相似性搜索找到数据库中与Q的编辑距离不超过给定阈值τ的所有字符串。现有的编辑相似性查询方法大多采用生成字符串相似性作为签名的方案，并通过在查询和数据签名上设置重叠查询来生成候选。在本文中，我们证明了对于任何这样的签名方案，最小签名数的下界是τ + 1，这比现有的方法所实现的要低。然后，我们提出了几个非对称签名方案，即提取不同数量的签名的数据和查询字符串，达到这个下限。首先建立了一个基本的非对称方案的基础上匹配的两个字符串之间的q-chunk和q-gram。两个有效的查询处理算法（IndexGram和IndexChunk）开发的顶部该计划。我们还提出了新的候选修剪方法，以进一步提高效率。然后，我们推广的基本方案，结合新的想法浮动的q-块，最佳选择的q-块，并减少使用全局排序的签名的数量。其结果是，超级和涡轮家庭的计划开发连同其相应的查询处理算法。我们已经进行了全面的实验研究，使用六个不对称算法和九个以前的国家的最先进的算法。实验结果清楚地展示了我们的方法的效率，并展示了我们提出的算法的空间和时间特性。
Given a query string Q, an edit similarity search finds all strings in a database whose edit distance with Q is no more than a given threshold τ. Most existing methods answering edit similarity queries employ schemes to generate string subsequences as signatures and generate candidates by set overlap queries on query and data signatures. In this article, we show that for any such signature scheme, the lower bound of the minimum number of signatures is τ + 1, which is lower than what is achieved by existing methods. We then propose several asymmetric signature schemes, that is, extracting different numbers of signatures for the data and query strings, which achieve this lower bound. A basic asymmetric scheme is first established on the basis of matching q-chunks and q-grams between two strings. Two efficient query processing algorithms (IndexGram and IndexChunk) are developed on top of this scheme. We also propose novel candidate pruning methods to further improve the efficiency. We then generalize the basic scheme by incorporating novel ideas of floating q-chunks, optimal selection of q-chunks, and reducing the number of signatures using global ordering. As a result, the Super and Turbo families of schemes are developed together with their corresponding query processing algorithms. We have conducted a comprehensive experimental study using the six asymmetric algorithms and nine previous state-of-the-art algorithms. The experiment results clearly showcase the efficiency of our methods and demonstrate space and time characteristics of our proposed algorithms.