Please wait a minute...
J4  2012, Vol. 46 Issue (2): 286-293    DOI: 10.3785/j.issn.1008-973X.2012.02.017
计算机技术     
基于分区索引的集合相似连接
洪银杰, 陈刚, 陈珂
浙江大学 计算机科学与技术系,浙江 杭州 310027
Set similarity join using partition index
HONG Yin-jie, CHEN Gang, CHEN Ke
Department of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
 全文: PDF  HTML
摘要:

 针对传统的索引和过滤算法处理在线相似连接时的不足,提出新的索引方法和过滤算法.在采用倒排索引的基础上,将索引按照位置和长度的相关信息进行划分,以减少查询空间,加强倒排索引的执行效率.此外,设计加权签名过滤算法,用来估计2个集合交的长度的上限,提高过滤的效率.集合的相似连接通常应用于过滤验证的工作框架里,主要采用2个步骤:先产生候选结果集合;再对候选集合进行验证.通过对真实数据集的实验,结果表明,该过滤算法可以和其他过滤算法一起协同应用于过滤验证的工作框架里,对数据进行在线相似连接处理,同时在计算效率上也有显著的提升.

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 filteringrefinement 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 filteringrefinement 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.

出版日期: 2012-03-20
:  TP 311.13  
基金资助:

国家自然科学基金资助项目(60803003, 60970124)

通讯作者: 陈刚,男,教授、博导     E-mail: cg@zju.edu.cn
作者简介: 洪银杰(1982—),男,博士生,从事数据库、数据挖掘研究.E-mail: hongyj@zju.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

洪银杰, 陈刚, 陈珂. 基于分区索引的集合相似连接[J]. J4, 2012, 46(2): 286-293.

HONG Yin-jie, CHEN Gang, CHEN Ke. Set similarity join using partition index. J4, 2012, 46(2): 286-293.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2012.02.017        http://www.zjujournals.com/eng/CN/Y2012/V46/I2/286

[1] XIAO Chuan, WANG Wei, LIN Xuemin, 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 setsimilarity 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 errortolerant 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 Xuemin. Edjoin: an efficient algorithm for similarity joins with edit distance constraints [J]. PVLDB, 2008(1): 933-944.
[9] RIBEIRO L, HRDER T. Efficient set similarity joins using minprexes [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 setvalued attributes [C]∥ Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. California: ACM, 2003: 157-168.

[1] 郭立超, 苏宏业, 缑倩雯. 一种新的数据流频繁度变化趋势预测算法[J]. J4, 2012, 46(5): 858-865.
[2] 吴羽,寿黎但,陈刚. CB-LSH:基于压缩位图的高性能LSH索引算法[J]. J4, 2012, 46(3): 377-385.
[3] 江锦华,吴羽,胡天磊,陈刚. 基于路径连接的XML复杂小枝模式查询处理[J]. J4, 2011, 45(1): 1-8.
[4] 周佳庆, 吴羽, 江锦华, 陈刚,董轶. 实时垂直搜索引擎对象缓存优化策略[J]. J4, 2011, 45(1): 14-19.