Page 459 - 《软件学报》2025年第9期

4370 软件学报 2025 年第 36 卷第 9 期

寻求选择. 此外, 作为对比, 本文也测试了精确三角形计数算法的更新速度, 其结果为 0.007 6 Mips, 比 CBS 算法慢
100 倍以上. 而且, 由于三角形计数的时间复杂度受到快照图大小的影响, 该速度会随着滑动窗口增大而快速下降.
当滑动窗口长度增加到 6M 时, 精确三角形计数算法的更新速度会进一步下降到 0.005 Mips, 而此时近似估算算
法的速度依然在 0.4 Mips 以上. 由此可以看出估算算法在速度上的优势.

10 2 CBS SWTC
CBS-FP FP
更新速度 (Mips) 10 1

10 0

1.0 1.5 2.0 2.5 3.0 3.5 4.0
样本比例 (%)
图 15 不同算法的更新速度对比

此外, 表 2 列出了 CBS 和 SWTC 算法的内存消耗值随着样本比例的变化, 滑动窗口大小依然固定为 4M. 可
以看出其内存随着样本比例, 也就是算法中的子流数目 K 线性增长. 而相比之下, 精确三角形计数算法的最大内
存消耗为 468 MB. 因此实验也验证了估算算法在内存消耗上的巨大优势.

表 2 CBS 与 SWTC 算法内存消耗随样本比例变化趋势

样本比例 (%) 1 2 3 4
内存消耗 (MB) 4.5 9 13.4 17.9

5 总 结
本文提出一种基于采样的滑动窗口模型下的图流三角形近似计数算法 CBS. 该算法将目前最好的滑动窗口
模型下的三角形近似计数算法 SWTC 和采样前计数策略结合, 以取得更高的估算精度. 由于采样前计数策略无法
处理滑动窗口模型下的边过期, 本文提出基于时间区间划分的原创过期处理方案, 并进一步提出误差修正方案
ETM. 最终实现的 CBS 算法在相同空间消耗下, 相比 SWTC 算法误差降低了 70% 以上. 随后我们使用真实数据集
进行了大量实验, 实验结果验证了 CBS 算法的高估算精度.

References:
[1] Grewal A, Jiang J, Lam G, Jung T, Vuddemarri L, Li QN, Landge A, Lin J. Recservice: Distributed real-time graph processing at Twitter.
In: Proc. of the 10th USENIX Conf. on Hot Topics in Cloud Computing. Boston: USENIX Association, 2018.
[2] Guha S, McGregor A. Graph synopses, sketches, and streams: A survey. Proc. of the VLDB Endowment, 2012, 5(12): 2030–2031. [doi:
10.14778/2367502.2367570]
[3] Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. SIAM Journal on Computing, 2002, 31(6):
1794–1813. [doi: 10.1137/S0097539701398363]
[4] Qiu XF, Cen WB, Qian ZP, Peng Y, Zhang Y, Lin XM, Zhou JR. Real-time constrained cycle detection in large dynamic graphs. Proc. of
the VLDB Endowment, 2018, 11(12): 1876–1888. [doi: 10.14778/3229863.3229874]
[5] Berry JW, Hendrickson B, LaViolette RA, Phillips CA. Tolerating the community detection resolution limit with edge weighting.
Physical Review E, 2011, 83(5): 056119. [doi: 10.1103/PhysRevE.83.056119]
[6] Eckmann JP, Moses E. Curvature of co-links uncovers hidden thematic layers in the World Wide Web. Proc. of the National Academy of
Sciences of the United States of America, 2002, 99(9): 5825–5829. [doi: 10.1073/pnas.032093399]
[7] Becchetti L, Boldi P, Castillo C, Gionis A. Efficient algorithms for large-scale local triangle counting. ACM Trans. on Knowledge