Top-k相似连接算法性能优化

摘要：

相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型:基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明:与Topk-join算法相比,Opt-join取得了1.28倍～3.09倍的性能提升.实验数据还显示:随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势.

关键词：Top-k相似连接、事件驱动框架、Token批处理、哈希查找优化

所属期刊栏目：27

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61370205;上海市自然科学基金13ZR1400800;中央高校基本科研业务费专项资金;National Natural Science Foundation of China61370205;Shanghai Municipal Natural Science Foundation13ZR1400800;The Fundamental Research Funds for the Central Universities

在线出版日期：2017-01-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：3051-3066