Efficient and Scalable Processing of String Similarity Join
Efficient and Scalable Processing of String Similarity Join
复制标题
字符串相似连接的高效且可扩展的处理
DOI：
10.1109/tkde.2012.195
复制
发表时间：
2013-10
影响因子：
8.9
通讯作者：
Tung, Anthony K. H.
中科院分区：
文献类型：
--
作者：
Rong, Chuitian;Lu, Wei;Wang, Xiaoli;Du, Xiaoyong;Chen, Yueguo;Tung, Anthony K. H.
字符串相似性连接是许多应用程序的基本操作，这些应用程序需要在给定相似性函数和用户指定的阈值的情况下从集合中查找所有字符串对。最近，有相当大的兴趣在设计新的算法与倒排索引的援助，以支持有效的字符串相似连接。这些算法通常采用两步过滤和细化的方法来识别相似的字符串对：1）通过遍历倒排索引来生成候选对;以及2）通过计算相似度来验证候选对。然而，这些算法要么遭受较差的滤波能力（这导致高验证成本），要么招致太多的计算成本以保证滤波能力。在本文中，我们提出了一种多前缀过滤方法的基础上不同的全球秩序，使候选对的数量可以显着减少。我们还提出了一个并行扩展的算法，是高效和可扩展的MapReduce框架。我们使用真实的和合成数据集在集中式和Hadoop系统上进行了广泛的实验，结果表明，我们提出的方法在效率和可扩展性方面优于现有的方法。
The string similarity join is a basic operation of many applications that need to find all string pairs from a collection given a similarity function and a user-specified threshold. Recently, there has been considerable interest in designing new algorithms with the assistant of an inverted index to support efficient string similarity joins. These algorithms typically adopt a two-step filter-and-refine approach in identifying similar string pairs: 1) generating candidate pairs by traversing the inverted index; and 2) verifying the candidate pairs by computing the similarity. However, these algorithms either suffer from poor filtering power (which results in high verification cost), or incur too much computational cost to guarantee the filtering power. In this paper, we propose a multiple prefix filtering method based on different global orderings such that the number of candidate pairs can be reduced significantly. We also propose a parallel extension of the algorithm that is efficient and scalable in a MapReduce framework. We conduct extensive experiments on both centralized and Hadoop systems using both real and synthetic data sets, and the results show that our proposed approach outperforms existing approaches in both efficiency and scalability.
登录
查看更多内容
DOI：
10.1145/223784.223807
发表时间：
1995-05
期刊：
--
影响因子：
--
作者：
Mauricio A. Hernández;S. Stolfo
通讯作者：
Mauricio A. Hernández;S. Stolfo
影响因子：
8.9
作者：
A. Elmagarmid;Panagiotis G. Ipeirotis;V. Verykios
通讯作者：
A. Elmagarmid;Panagiotis G. Ipeirotis;V. Verykios
DOI：
10.1145/1367497.1367516
发表时间：
2008-04
期刊：
--
影响因子：
--
作者：
Chuan Xiao;Wei Wang;Xuemin Lin;J. Yu;Guoren Wang
通讯作者：
Chuan Xiao;Wei Wang;Xuemin Lin;J. Yu;Guoren Wang
DOI：
--
发表时间：
2006-09
期刊：
--
影响因子：
--
作者：
A. Arasu;Venkatesh Ganti;R. Kaushik
通讯作者：
A. Arasu;Venkatesh Ganti;R. Kaushik
DOI：
10.1145/1807167.1807266
发表时间：
2010-06
期刊：
Proceedings of the 2010 ACM SIGMOD International Conference on Management of data
影响因子：
--
作者：
Zhenjie Zhang;Marios Hadjieleftheriou;B. Ooi;D. Srivastava
通讯作者：
Zhenjie Zhang;Marios Hadjieleftheriou;B. Ooi;D. Srivastava