Dtrie-allpair:高效的集合T-覆盖连接算法*

贾连印 奚建清 李孟娟 游进国 刘勇 苗德成

(1.华南理工大学计算机科学与工程学院，广东广州510006;2.云南师范大学图书馆，云南昆明650092;3.昆明理工大学信息工程与自动化学院，云南昆明650500)

集合一直是研究者研究的热点，在众多涉及集合的问题中，集合相似度连接问题旨在从大量的集合中查找满足特定相似度阈值的集合对.该问题广泛存在于数据清洗［1-2］、近似重复判断［3］、抄袭检测［4］等领域.

需要注意的是，集合相似度连接问题不同于集合相似度查询问题［5］.集合相似度查询算法通常基于全部数据构建静态的索引结构，同样可用于实现集合相似度连接算法.但高效的集合相似度连接算法为了避免出现重复的结果对而通常在部分数据基础上以动态递增的方式构建索引，因此具有更优的性能.

集合相似度问题同样不同于被广泛研究的集合包含问题［6-11］.集合包含问题通常以集合包含查询为基础，可分为子集查询、超级查询和等值查询.集合包含查询通常用于查询一个集合完全包含或包含于另一个集合.而集合相似度查询或连接则着重于研究集合之间包含的程度.

近年来，研究者提出了多种不同的算法来解决集合相似性连接问题，例如算法 SSJoin［1］、PARTENUM 算法［2］、WTENUM 算法［2］、topk-join 算法［12］、MergeOpt算法［13］等.

众多算法中，Bayardo等［14］提出的 All-pair算法、Xiao等［3］提出的 PPJoin算法具有良好的伸缩性，能非常高效地扩展到上百万记录的All-pair问题的计算.

然而，这类算法通常基于反向索引结构并且基于生成－测……