加速图交集归约框架

交集计算大幅提速

通过范围约减提前剔除不可能落入交集的顶点，让图算法中的集合交集在低代价下完成。

Zheng, Hu · Cong, Xu · 郑卫国

VLDB Journal 2025

技术优势

不用直接求交集

先通过范围归约筛掉大量无关顶点，只在截断后的小子集上求交集，降低计算量。

全局局部都能加速

针对全局交集和局部交集两种典型场景分别设计了高效算法，覆盖不同图计算需求。

两级嵌套再提速

引入两级策略和嵌套归约框架，进一步减少冗余计算，提升整体性能。

真实图上显著快

在真实图数据上大量实验表明，本方法相对最新算法有明显加速。

应用场景

• 图算法优化：用归约框架加速图算法中的集合交集操作
• 大规模图数据处理：通过范围归约降低大规模图上的交集计算成本
• 社交网络分析：加速社交网络中共同邻居、三角形计数等交集操作
• 图数据库加速：提高图数据库中集合查询的响应速度
• 子图匹配：加速子图匹配中的候选顶点交集计算