Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints
Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints
复制标题
DOI：
10.14778/1453856.1453957
复制
发表时间：
2008-08-01
影响因子：
2.5
通讯作者：
Lin, Xuemin
中科院分区：
文献类型：
--
作者：
Xiao, Chuan;Wang, Wei;Lin, Xuemin
近来，相似性研究在研究界引起了相当大的兴趣.相似连接是数据集成与清洗、生物信息学、模式识别等领域的一个基本操作。我们专注于有效的算法与编辑距离约束的相似连接。现有的方法主要是基于将编辑距离约束转化为对字符串之间匹配q-gram数目的较弱约束，本文提出了一种研究不匹配q-gram的新视角。在技术上，我们通过分析不匹配的q-gram的位置和内容，得到了两个新的编辑距离下限。一个新的算法，Ed-Join，提出了利用新的基于失配的过滤方法，它实现了大幅减少的候选大小，从而节省计算时间。实验表明，在大规模真实的数据集上，新算法在各种参数设置下的性能优于其他方法。
There has been considerable interest in similarity join in the research community recently. Similarity join is a fundamental operation in many application areas, such as data integration and cleaning, bioinformatics, and pattern recognition. We focus on efficient algorithms for similarity join with edit distance constraints. Existing approaches are mainly based on converting the edit distance constraint to a weaker constraint on the number of matching q-grams between pair of strings.In this paper, we propose the novel perspective of investigating mismatching q-grams. Technically, we derive two new edit distance lower bounds by analyzing the locations and contents of mismatching q-grams. A new algorithm, Ed-Join, is proposed that exploits the new mismatch-based filtering methods; it achieves substantial reduction of the candidate sizes and hence saves computation time. We demonstrate experimentally that the new algorithm outperforms alternative methods on large-scale real datasets under a wide range of parameter settings.