计算机工程

• 先进计算 • 上一篇    下一篇

基于索引的内存相似性连接算法

董明秀a,b,王鹏a,b,汪洋a,b,李秋虹a,b,汪卫a,b   

  1. (复旦大学 a.计算机科学技术学院; b.上海市数据科学重点实验室,上海 201203)
  • 收稿日期:2014-12-19 出版日期:2016-01-15 发布日期:2016-01-15
  • 作者简介:董明秀(1988-),女,硕士研究生,主研方向为时间序列相关性查询、分布式计算;王鹏,副教授、博士研究生;汪洋、李秋虹,博士研究生;汪卫,教授、博士研究生。
  • 基金项目:
    国家自然科学基金资助项目(61103009);上海市科委大数据专项基金资助项目(13511504800)。

Memory Similarity Join Algorithm Based on Index

DONG Mingxiu  a,b,WANG Peng  a,b,WANG Yang  a,b,LI Qiuhong  a,b,WANG Wei  a,b   

  1. (a.School of Computer Science; b.Shanghai Key Laboratory of Data Science,Fudan University,Shanghai 201203,China)
  • Received:2014-12-19 Online:2016-01-15 Published:2016-01-15

摘要: 在传统的相似性连接算法中,精确计算和分区阶段互相独立,精确计算时需要对每个分区中的所有数据进行两两比较,计算量较大。针对该问题,设计一种新的内存索引——距离树,并在其基础上提出两结构内存相似性连接算法。根据数据的潜在分布将其分发到不同的分区中 ,保证具有一定相似度的数据对分配在同个或相邻的分区内,同时通过树节点之间的位置信息保存分区阶段的计算结果,使精确计算阶段仅需对每个分区中相邻的叶节点数据进行比较计算。实验结果表明,与TOUCH算法相比,基于距离树的算法可使运行速度提高2倍~3倍,并具 有更好的可扩展性。

关键词: 相似性连接, 磁盘, 查询, 内存, 索引, 分区

Abstract: In traditional similarity join algorithms,data partition and refined calculation are isolated.During the refined calculation phase,all pairs of data in the same partition need to be compared with each other which leads to a large number of comparison computations.In order to solve this problem,this paper designs a new memory index:DistanceTree,and proposes an in-memory similarity join algorithm based on it.This algorithm distributes data into different partitions according to the potential distribution of data,ensures the data with same similarity to the same or adjacent partitions,and saves the calculation results of partition phase through the tree node location information.By leveraging the calculation result,only pairs of data in the same or adjacent leaf nodes need to be compared.Experimental results show that similarity join algorithm based on DistanceTree is 2 times~3 times more efficient than TOUCH algorithm and also is more scalable.

Key words: similarity join, disk, query, memory, index, partition

中图分类号: