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

来源：软件学报杂志2016年第12期北京时间：

作者：王洪亚,杨利宏,刘晓强

单位：王洪亚，东华大学 计算机科学与技术学院, 上海 20162011,杨利宏，东华大学 计算机科学与技术学院, 上海 20162002,刘晓强，东华大学 计算机科学与技术学院, 上海 20162003

摘要：相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型：基于相似度阈值的相似连接和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批处理;哈希查找优化

基金资助：国家自然科学基金（61370205）；上海市自然科学基金（13ZR1400800）；中央高校基本科研业务费专项资金