摘要
利用集合相似度自连接算法找出一个集合集中所有相似度大于给定阈值的集合对有着广泛的应用.基于过滤-验证框架和并行分布式计算框架MapReduce的集合相似度连接是近年来的研究热点.但现有算法在阈值低时产生较大规模的候选集,导致性能不理想.针对这一问题,提出采用频繁模式树FP-tree及其派生结构FP-tree*将数据压缩在内存中计算集合相似度自连接以减小候选集规模.首先设计并讨论基于现有FP-tree*的集合相似度连接计算及其优缺点,提出遍历效率更高的线性频繁模式树结构模型TELP-tree及基于它的算法TELP-SJ(TELP-tree self join),其包括分别面向构建树和遍历树的 2阶段过滤算法,这些算法可以减小树规模和减少树遍历.然后,设计基于MapReduce的并行分布式算法FastTELP-SJ.最后,基于 4组真实应用数据集进行 3组性能比较实验.实验结果表明FastTELP-SJ算法面向高维大规模集合相似度自连接计算时,包括执行时间、内存占用率、磁盘使用量和可扩展性的运行效率最好.
基金项目
国家自然科学基金(62272315)
国家自然科学基金(61836005)
国家自然科学基金(62002230)
深圳市基础研究面上项目(JCYJ20210324093212034)
广东省自然科学基金(2019A1515012053)
腾讯"犀牛鸟"-深圳大学青年教师科研基金()
深圳市稳定支持计划项目(20200814105901001)
NETL
NSTL
维普
万方数据