|
|
Set similarity join using partition index |
HONG Yin-jie, CHEN Gang, CHEN Ke |
Department of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China |
|
|
Abstract To address the deficiency of similarity join online when using traditional indexing and filtering algorithm, we proposed several novel filtering approaches by improving the inverted based and signature based schemes. Enhancing the inverted index to reduce the search spaces, which partition the index according to the information of item’s position and the record’s length. In addition, we designed a novel weighted signature filtering scheme, where the upper bound of the overlap between two sets can be estimated to improve the effectiveness of filtering. Typically, the processing of set similarity join often adopts the filteringrefinement framework, which generates candidates by some filtering schemes and then produces the final results by refining the candidates. The proposed schemes can be seamlessly integrated into the filteringrefinement framework with other filtering schemes to process set similarity join online. Extensive experiments are conducted using real datasets. The experiments results show the efficiency of the proposed schemes.
|
Published: 20 March 2012
|
|
基于分区索引的集合相似连接
针对传统的索引和过滤算法处理在线相似连接时的不足,提出新的索引方法和过滤算法.在采用倒排索引的基础上,将索引按照位置和长度的相关信息进行划分,以减少查询空间,加强倒排索引的执行效率.此外,设计加权签名过滤算法,用来估计2个集合交的长度的上限,提高过滤的效率.集合的相似连接通常应用于过滤验证的工作框架里,主要采用2个步骤:先产生候选结果集合;再对候选集合进行验证.通过对真实数据集的实验,结果表明,该过滤算法可以和其他过滤算法一起协同应用于过滤验证的工作框架里,对数据进行在线相似连接处理,同时在计算效率上也有显著的提升.
|
|
[1] XIAO Chuan, WANG Wei, LIN Xuemin, et al. Efficient similarity joins for near duplicate detection [C]∥ Proceedings of the 17th International Conference on World Wide Web. Beijing: ACM, 2008: 131-140.
[2] ARASU A, GANTI V, KAUSHIK R. Efficient exact setsimilarity joins [C]∥ Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul: ACM, 2006: 918-929.
[3] AGRAWAL P, ARASU A, KAUSHIK R. On indexing errortolerant set containment [C]∥ Proceedings of the ACM SIGMOD International Conference on Management of Data. Indianapolis: ACM, 2010: 927-938.
[4] THEOBALD M, SIDDHARTH J, PAEPCKE A. Spotsigs: robust and efficient near duplicate detection in large web collections [C]∥ Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Singapore: ACM, 2008: 563-570.
[5] CHAUDHURI S, GANTI V, KAUSHIK R. A primitive operator for similarity joins in data cleaning [C]∥ Proceedings of the 22nd International Conference on Data Engineering. Atlanta: IEEE Computer Society, 2006: 5.
[6] SARAWAGI S, KIRPAL A. Efficient set joins on similarity predicates [C]∥ Proceedings of the ACM SIGMOD International Conference on Management of Data. Paris: ACM, 2004: 743-754.
[7] GRAVANO L, IPEIROTIS P G, JAGADISH H V, et al. Approximate string joins in a database (almost) for free [C]∥ Proceedings of 27th International Conference on Very Large Data Bases. Roma. Morgan Kaufmann, 2001: 491-500.
[8] XIAO Chuan, WANG Wei, LIN Xuemin. Edjoin: an efficient algorithm for similarity joins with edit distance constraints [J]. PVLDB, 2008(1): 933-944.
[9] RIBEIRO L, HRDER T. Efficient set similarity joins using minprexes [C]∥ Advances in Databases and Information Systems, 13th East European Conference. Riga: Springer, 2009: 88-102.
[10] BAYARDO R J, MA Y, SRIKANT R. Scaling up all pairs similarity search [C]∥ Proceedings of the 16th International Conference on World Wide Web. Alberta: ACM, 2007: 131-140.
[11] MAMOULIS N. Efficient processing of joins on setvalued attributes [C]∥ Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. California: ACM, 2003: 157-168. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|