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

Memory Similarity Join Algorithm Based on Index

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

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.