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

苟向阳 等: 高精度滑动窗口模型下的图流三角形近似计数算法 4357

e
样前计数策略可以处理全动态模型中的显式删除, 对于每一条删除的边 e, 该策略计算 在 G s 中构成的三角形数
e
e
目 |∆ s |, 之后估算 在快照图中构成的三角形数目为 |∆ s |/p(2), 这些三角形会因为 的删除而消失, 所以需要从 τ 中
G s 中删除. 查询时, 该策略直接返回 作为三角形数目估算
τ
减去该值. 之后检查 e 是否为样本边, 若是, 则将其从
值. 将采样前计数策略应用在滑动窗口模型时的主要困难在于处理边过期. 该策略需要知晓每一次边的删除, 无论
其是否为样本边. 全动态模型中, 删除是由图流中的数据项指明的, 因此算法总能知晓. 而在滑动窗口中, 边删除,
或者说边过期, 是随着时间推移自发发生的, 非样本边没有被保存, 因此无法知晓其何时过期. 为了处理这一问题.
下文将提出处理过期数据的全新策略.

3 CBS 算法

本节将提出高精度的滑动窗口模型下的图流三角形近似计数算法 CBS. CBS 算法结合 SWTC 算法和采样前
计数策略, 并提出处理数据过期的策略. 实验表明, 本算法相比 SWTC 算法在相同空间下取得了更高的估算精度.
我们将在第 3.1 节介绍基础版本的 CBS 算法, 并在第 3.2 节进一步提出误差修正策略 ETM, 进一步提高估算的精
确度并保证其无偏性.

3.1 基础版 CBS 算法
基础版 CBS 算法结合 SWTC 和采样前计数, 并使用时间切片的策略以处理过期数据. 算法选择一系列固定
N/d 的区间 (interval). 这一切片策略与 SWTC 中的方案类似, 称切分后的片段
的路径点, 将时间轴切分为长度为
为区间 (interval) 以便与 SWTC 采样算法中的图流片段 (slice) 区分. 此外, 本文称该方法为时间划分而非图流切
片, 因为下文中会研究时间戳落入每个区间的三角形, 而非仅关注时间戳在该区间内的图流数据项. 在任意时刻
T , 滑动窗口至多与 d +1 个区间相交, 这些区间的并集可以表示为 (⌊Td/N⌋× N/d − N,T], 是滑动窗口 (T − N,T) 的
超集.
图 6 展示了 CBS 算法中一个时间划分的示例, 其中每个区间的长度为 3, 而滑动窗口的长度为 6. 当前时刻为
13, 滑动窗口与 3 个区间相交, 也就是区间 3, 4 和 5. 这 3 个区间的并集是 (6, 13] (注意区间 5 是 (12, 15], 但由于
当前时间是 13, 所以其中只包含到时刻 13 为止的数据), 而滑动窗口为 (7, 13]. 而等到时刻 15, 滑动窗口只与 2 个
区间相交 (区间 4 和 5), 这 2 个区间的并集刚好为滑动窗口.

滑动窗口

t=1 t=3 t=5 t=6 t=7 t=8 t=10 t=11 t=12 t=13 t=13
(v 1 , v 4 ) (v 2 , v 3 ) (v 5 , v 6 ) (v 3 , v 5 ) (v 6 , v 8 ) (v 1 , v 7 ) (v 7 , v 8 ) (v 1 , v 8 ) (v 1 , v 6 ) (v 2 , v 8 ) (v 1 , v 2 )
区间 1 区间 2 区间 3 区间 4 区间 5
图 6 CBS 区间切分

进一步的, 我们定义图流中的有效三角形如下.
N 的滑动窗口以及当前时刻 , 图流中的有效三角形由图流中的 3 条边
T
● 有效三角形: 给定一个长度为
[(v i ,v j ),(v i ,v k ),(v j ,v k )] 组成, 这 3 条边都在 T 时刻之前出现过, 且 3 条边的时间戳的最大值和最小值之差不超过 N .
T , 图流中的有效三角形包括目前在滑动窗口中的, 以及曾经在滑动窗口中出现过的三角形. 此外, 定
在时刻
义有效三角形的时间戳如下.
● 有效三角形的时间戳: 一个有效三角形的时间戳为它的 3 条边的时间戳的最小值.
有如下定理.
定理 1. 在 T 时刻, 一个三角形在快照图中的充要条件是该三角形是一个时间戳在 (T − N,T] 之内的有效三
角形.
证明: 若该三角形在快照图中, 则它一定由滑动窗口中的边组成, 因此 3 条边的时间戳都在 (T − N,T] 之内, 所
以组成该三角形的 3 条边的时间戳之差不超过 N, 其中的最小值也在 (T − N,T] 之内, 因此该三角形是一个时间戳