面向大规模二部图的分布式Tip分解算法

• 作者: 周旭 翁同峰 杨志邦 李博仁 张吉 李肯立
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 二部图 butterfly计数 分布式系统 tip分解
• 年，卷（期）: 2022,（3）
• 所属期刊栏目: 数据库系统新型技术专题|SPECIAL TOPIC ON NEW TECHNIQUES OF DATABASE SYSTEMS
• 页码范围: 1043-1056
• 页数: 14页
• 分类号: TP311
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.006457

摘要

Tip分解作为图数据管理领域的热点研究问题,已被广泛应用于文档聚类和垃圾邮件组检测等实际场景中.随着图数据规模的爆炸式增长,单机内存已无法满足其存储需求,亟需研究分布式环境下Tip分解技术.现有分布式图计算系统的通信模式无法适用于二部图,为此,首先提出一种基于中继的通信模式,以实现分布式环境下处理二部图时消息的有效传递;其次,提出分布式butterfly计数算法(DBC)和tip分解算法(DTD),特别地,为解决处理大规模二部图时DBC面临的内存溢出问题,提出了一种可控的并行顶点激活策略;最后,引入基于顶点优先级的消息剪枝策略和消息有效性剪枝策略,通过减少冗余通信和计算开销,进一步提高算法效率.实验平台部署于国家超算中心高性能分布式集群上,在多个真实数据集上的实验结果验证了所提算法的有效性和高效性.