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

• 作者: 刘晓强 杨利宏 王洪亚
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: Top-k相似连接 事件驱动框架 Token批处理 哈希查找优化
• 年，卷（期）: 2016,（12）
• 所属期刊栏目: 数据库技术
• 页码范围: 3051-3066
• 页数: 16页
• 分类号: TP311
• 字数: 10958字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005012

摘要

相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型:基于相似度阈值的相似连接和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的性能优势有不断增加的趋势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王洪亚	东华大学计算机科学与技术学院	19	61	3.0	6.0
2	刘晓强	东华大学计算机科学与技术学院	50	310	10.0	16.0
3	杨利宏	东华大学计算机科学与技术学院	1	3	1.0	1.0