基于分区索引的集合相似连接

摘要：

针对传统的索引和过滤算法处理在线相似连接时的不足,提出新的索引方法和过滤算法.在采用倒排索引的基础上,将索引按照位置和长度的相关信息进行划分,以减少查询空间,加强倒排索引的执行效率.此外,设计加权签名过滤算法,用来估计2个集合交的长度的上限,提高过滤的效率.集合的相似连接通常应用于过滤验证的工作框架里,主要采用2个步骤:先产生候选结果集合；再对候选集合进行验证.通过对真实数据集的实验,结果表明,该过滤算法可以和其他过滤算法一起协同应用于过滤-验证的工作框架里,对数据进行在线相似连接处理,同时在计算效率上也有显著的提升.

关键词：相似连接、分区、加权签名、过滤、相似函数

所属期刊栏目：46

分类号：TP311.13(计算技术、计算机技术)

在线出版日期：2012-05-25（万方平台首次上网日期，不代表论文的发表时间）

页码：286-293