基于FP-tree和MapReduce的集合相似度自连接算法

作     者：冯禹洪 吴坤汉 黄志鸿 冯洋洲 陈欢欢 白鉴聪 明仲 Feng Yuhong;Wu Kunhan;Huang Zhihong;Feng Yangzhou;Chen Huanhuan;Bai Jiancong;Ming Zhong

作者机构：深圳大学计算机与软件学院广东深圳518060 中国科学技术大学计算机科学与技术学院合肥230027 

基　　金：国家自然科学基金项目(62272315,61836005,62002230) 深圳市基础研究面上项目(JCYJ20210324093212034) 广东省自然科学基金项目(2019A1515012053) 腾讯“犀牛鸟”-深圳大学青年教师科研基金项目 深圳市稳定支持计划项目(20200814105901001) 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2023年第60卷第12期

页      码：2890-2906页

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

主 题 词：相似度连接 FP树 MapReduce框架 Jaccard函数 集合 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

核心收录：

D　O　I：10.7544/issn1000-1239.202111239

馆 藏 号：203125000...