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

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

并且调用一次过期处理函数, 之后再调用算法 1 处理新边.
∑ d
在查询时, 算法返回所有 d +1 个三角形计数器的和 τ i 作为滑动窗口中三角形数目的估算值.
i=0
CBS 算法事实上是以区间替换的方式实现了三角形计数值的批量过期. 每当到达一个路径点, 就会有一个区
间不再与滑动窗口相交, 将其中的有效三角形数量从计数器中删除, 该操作代表了对于时间戳在该区间内的有效
三角形的批量过期操作. 例如在图 6 中, 等到时刻 15, 滑动窗口不再与区间 3, 也就是 (6,9] 相交, 该区间内的有效
(⌊Td/N⌋× N/d − N,T] 内的三角形数目, 所以
三角形数目便会从计数器中减去. 由于估算的其实是滑动窗口的超集
d, 我们可以
该估算的期望值大于滑动窗口内的三角形数目. 但是通过将区间切分得足够小, 也就是设置足够大的
将误差控制在较小的范围内. 第 3.2 节还会提出进一步的改进策略, 实现无偏估算, 也就是让估算期望值恰好等于
滑动窗口内的三角形数目.

3.2 误差修正算法 ETM
基础版 CBS 算法使用时间戳在最近 d +1 个区间内的有效三角形数量 τ 来作为滑动窗口中三角形数量的估算
值, 而前者在期望上大于后者. 在本节中, 我们进一步提出误差修正算法 ETM (expired triangle-count modification)
来实现无偏估算, 也就是让估算值的期望等于滑动窗口中三角形的数目.
如第 3.1 节所述, 最近 d +1 个区间的并集是 (⌊Td/N⌋× N/d − N,T], 相比滑动窗口 (T − N,T], 多出了时间段
(⌊Td/N⌋× N/d − N,T − N]. 例如在图 6 中, 最近 d +1 个区间是区间 3–5, 它们的并集是 (6,13], 相比滑动窗口 (7,13],
多出的时间段为 (6,7]. 只要能估算出时间戳在该时间段内的有效三角形数目, 并将其从 τ 中减去, 便能让 τ 的期望
I d 中不属于
值等于滑动窗口中的三角形数目. 从另一个角度来说, 该时间段也就是与滑动窗口相交的最早的区间
滑动窗口的部分, 而该时间段内的有效三角形数目, 也就是 I d 已经过期的有效三角形数目, 使用一个误差修正计数
器 τ exp 来记录该值.
然而, 如第 2.3 节所述, 不能使用采样前计数策略来估算过期三角形的数目, 因为它要求算法知晓每一次边过
期, 无论其是否被采样. 而由于 CBS 算法没有保存非样本边, 这一点无法实现. 因此, 本文选择仅使用样本边的信
G s 的过期三角形集合 . 每一个过期三角形被加入
息来估算 τ exp 的值. 每当滑动窗口移动时, 算法记录被采样进 ∆ s
( )/( )
m |W| m(m−1)(m−2)
∆ s 的概率等于它的 3 条边都被采样的概率, 也就是 p(3) = = , 其中 |W| 和 m 分
3 3 |W|(|W|−1)(|W|−2)
别为滑动窗口中的边数以及样本图中的边数. 因此, 算法将 τ exp 增加 |∆ s |/p(3), 以此来实现对于 I d 内过期三角形数
目的无偏估算. 在查询时, 把 τ 0 到 τ d 的 d+1 个计数器加和后, 从中减去 τ exp 的值, 从而实现对于滑动窗口中三角形
数目的无偏估算.
τ exp 记录的是与滑动窗口相交的最旧的区间
值得注意的是, 当时间经过路径点时, 需要把 τ exp 设置为 0. 因为
I d 不再与滑动窗口相交, 算法也会抛弃它的有效三角形计数
内的过期三角形数目. 经过路径点时, 原来最旧的区间
值, 而原来的 I d−1 会变成现在的最旧的区间 , 需要重置 τ exp , 并且重新开始计数新的 I d 中的过期三角形数目.
I d
算法 3 展示了使用 ETM 改进后的 CBS 处理过期数据的算法.
算法 3. 改进版 CBS 处理过期数据.

–
输入: 当前时刻 T , 时间增量 ∆T , 样本图 G s , 三角形计数器 τ 0 τ d , 误差修正计数器 τ exp ;
输出: 删除过期数据后的样本图和三角形计数器.
⌊ ⌋ ⌊ ⌋
(T +∆T)d Td
1. y = −
N N
2. if y > 0 then
//经历了 y 个新区间, 后移旧区间的计数器并初始化前 y 个计数器
3. τ exp = 0
4. for i = d −y; i ⩾ 0; i−− do

5. τ i+y = τ i