Efficient exact set-similarity joins
Efficient exact set-similarity joins
复制标题
DOI：
--
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
A. Arasu;Venkatesh Ganti;R. Kaushik
中科院分区：
文献类型：
--
作者：
A. Arasu;Venkatesh Ganti;R. Kaushik
给定两个输入的集合集合，集合相似性连接 (SSJoin) 会识别具有高度相似性的所有集合对（每个集合中的一个）。最近的工作已将 SSJoin 确定为数据清理中有用的原始运算符。在本文中，我们提出了 SSJoin 的新算法。我们的算法有两个重要特征：它们是精确的，即它们总是产生正确的答案，并且它们具有精确的性能保证。我们相信我们的算法是第一个同时具备这两个功能的算法；以前具有性能保证的算法只是概率上的近似。我们通过对现实生活和合成数据集进行彻底的实验评估来证明我们算法的有效性。
Given two input collections of sets, a set-similarity join (SSJoin) identifies all pairs of sets, one from each collection, that have high similarity. Recent work has identified SSJoin as a useful primitive operator in data cleaning. In this paper, we propose new algorithms for SSJoin. Our algorithms have two important features: They are exact, i.e., they always produce the correct answer, and they carry precise performance guarantees. We believe our algorithms are the first to have both features; previous algorithms with performance guarantees are only probabilistically approximate. We demonstrate the effectiveness of our algorithms using a thorough experimental evaluation over real-life and synthetic data sets.