一种基于R*树的自相似性连接算法

摘要

相似性连接是很多研究问题的基础,不少实际问题也都可以归结为相似性连接.针对两个输入集合相同的相似性连接问题,以R*树作为索引结构,提出一种高效的自相似性连接算法Self-SJ,返回最相似的k个对象对.该算法利用了分支界限思想,在使用剪枝策略减少候选对象对的同时,也避免了重复节点对的计算,因而比传统的基于R*树的算法更加快速.在真实数据集上的实验表明,Self-SJ不仅具有更短的运行时间,对于参数k也具有良好的可扩展性.