MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
复制标题
DOI：
10.1145/3292500.3330853
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Haoyu Zhang;Qin Zhang
中科院分区：
文献类型：
--
作者：
Haoyu Zhang;Qin Zhang
我们研究了计算相似性在编辑距离下在一组字符串上加入的问题。编辑相似性连接是数据库，数据挖掘和生物信息学的一个基本问题。它发现在数据清洁和集成，协作过滤，基因组序列组装等方面的重要应用。在过去的二十年中，这个问题引起了极大的关注。但是，所有以前的算法要么不能很好地扩展到长字符串和较大的相似性阈值，要么遭受不完善的精度。在本文中，我们提出了一种新算法，用于使用基于新颖的弦乐分区的方法加入编辑相似性。我们从数学上表明，算法的可能性很高，可以实现完美的准确性，并在线性时间和数据依赖性验证步骤中运行。现实世界数据集上的实验表明，我们的算法显着优于用于编辑相似性加入的最新算法，并在我们测试的所有数据集上实现了完美的准确性。
We study the problem of computing similarity joins under edit distance on a set of strings. Edit similarity joins is a fundamental problem in databases, data mining and bioinformatics. It finds important applications in data cleaning and integration, collaborative filtering, genome sequence assembly, etc. This problem has attracted significant attention in the past two decades. However, all previous algorithms either cannot scale well to long strings and large similarity thresholds, or suffer from imperfect accuracy. In this paper we propose a new algorithm for edit similarity joins using a novel string partition based approach. We show mathematically that with high probability our algorithm achieves a perfect accuracy, and runs in linear time plus a data-dependent verification step. Experiments on real world datasets show that our algorithm significantly outperforms the state-of-the-art algorithms for edit similarity joins, and achieves perfect accuracy on all the datasets that we have tested.