计算机研究与发展

作者：冯禹洪,吴坤汉,黄志鸿,冯洋洲,陈欢欢,白鉴聪,明仲,

关键词：相似度连接, FP树, MapReduce框架, Jaccard函数, 集合,

利用集合相似度自连接算法找出一个集合集中所有相似度大于给定阈值的集合对有着广泛的应用.基于过滤-验证框架和并行分布式计算框架MapReduce的集合相似度连接是近年来的研究热点.但现有算法在阈值低时产生较大规模的候选集，导致性能不理想.针对这一问题，提出采用频繁模式树FP-tree及其派生结构FP-tree*将数据压缩在内存中计算集合相似度自连接以减小候选集规模.首先设计并讨论基于现有FP-tree*的集合相似度连接计算及其优缺点，提出遍历效率更高的线性频繁模式树结构模型TELP-tree及基于它的算法TELP-SJ（TELP-treeselfjoin），其包括分别面向构建树和遍历树的2阶段过滤算法，这些算法可以减小树规模和减少树遍历.然后，设计基于MapReduce的并行分布式算法FastTELP-SJ.最后，基于4组真实应用数据集进行3组性能比较实验.实验结果表明FastTELP-SJ算法面向高维大规模集合相似度自连接计算时，包括执行时间、内存占用率、磁盘使用量和可扩展性的运行效率最好.

来源：2023年第12期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2023年第12期