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

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

的 CBS 算法变体.
2.1 固定概率采样算法
固定概率采样算法 (fixed probability sampling) 即使用固定概率 r 对图流中的每一条边进行采样. 每当图流中
有新边到达时, 算法运行一个满足概率为 r 的伯努利分布的随机函数, 当函数返回值为 1 时, 将新边加入样本集
合, 否则便丢弃该边. 该采样方法被之前的许多三角形估算工作采用 [28,30] . 可以使用固定概率采样维护样本图, 计
3
数样本图中的三角形数目, 并将其乘以 1/r 来估算快照图中的三角形数目. 固定概率采样可以适用于滑动窗口模
型, 只需要实时删除样本集合中的过期样本边即可. 但是在滑动窗口模型下, 固定概率采样算法的样本集大小为
r ×|W|, 其中 |W| 为滑动窗口中的总边数. 虽然滑动窗口在时间尺度的长度 N 是固定的, 但其中边数 |W| 会随着图
流的流量, 也就是单位时间到达的新边数量, 而发生较大改变. 这导致固定概率采样算法的样本集大小会随着图流
流量而不断变化, 我们无法提前预测其上限. 因此, 也无法给出其空间占用的上限, 这会导致在空间紧张的应用场
景中难以对内存分配进行规划.

2.2 SWTC 算法
Gou 等人 [16] 提出的 SWTC 算法是滑动窗口模型下具有固定空间占用的三角形近似估算算法. 在图 3 中给出
了算法的框架图. 该方法基于优先级采样 (priority sampling) [37] . 它首先使用一个随机函数 H(·) 将图流中的每一条
G(·) 为
边划分到 K 个子流中的一个, 其中 K 为提前设定的参数. 之后 SWTC 使用另一个服从均匀分布的随机函数
每一条边 e 分配一个在 (0,1) 内的优先级 G(e), 之后, 算法尝试在每个子流中找到滑动窗口内优先级最高的边作为
K 的样本集. 由于子流划分和优先级赋予都是随机的, 所以每条
样本边. 最终这些样本边便组成了一个大小不超过
G(·) 替换为哈希函数, 算法也可以支持二
边都有相同的概率被采样, 该样本集是一个无偏的样本集. 通过将 H(·) 和
项计数语义.

H(·) 子流 1
根据采样概率，
使用函数 尝试在每个 按比例放大样本
图流 子流 2 G(·)为每 子流内采样 样本图 图中的三角形数
条边计算 滑动窗口中 目以估算滑动窗
… 权重 权重最高的 口中三角形数目
子流 k 边

图 3 SWTC 算法框架

在该算法流程中, 主要的技术挑战有两点, 如何使用固定空间维护每个子流中在滑动窗口内的优先级最高的
边, 以及如何计算滑动窗口中每个三角形被加入样本图的概率. 后者需要在根据样本图中三角形数目估算滑动窗
口中三角形数目时使用, 而为了计算该概率, 主要挑战在于估算滑动窗口中的边数. 下面分别对这两点挑战及
SWTC 的解决办法进行介绍.
● 子流中样本边的维护: 具体来说, 该阶段的挑战来自样本边的过期. 在没有边过期时, 维护优先级最高的边
e
较为简单. 只需要使用一个变量 ϵ 来维护目前优先级最大的边, 每当子流中有新边 到达时, 对比 G(e) 和 G(ϵ), 并
G(e) 更高时使用 ϵ. 然而, 当 过期时, 如何选择其后继则会变得很困难. 子流中存在 之后到达的边, 它
ϵ
ϵ
在 e 替换
ϵ
们仍未过期, 但是由于优先级低于 ϵ 而没有被选为样本边, 算法没有保存它们, 也无法判断 过期后滑动窗口中优
先级最高的边是否在它们之间, 因此难以重新选出样本边. 举例来说, 在图 1 中, 假设图流中时间戳在 (0,6] 内的 4
G(v 1 ,v 4 ) = 0.9 G(v 2 ,v 3 ) = 0.6 G(v 5 ,v 6 ) = 0.8 G(v 3 ,v 6 ) = 0.2. 在时刻 6, 滑动窗口内优先级最高
,
,
,
条边的优先级分别为
的边是 (v 1 ,v 4 ), 算法将其保存为样本边, 而非样本边则没有被保存. 在时刻 7, 边 (v 1 ,v 4 ) 过期, 而算法没有保存滑动
窗口内其他 3 条边, 因此无法找到当前滑动窗口中优先级最高的边. 在时刻 8, 边 (v 1 ,v 7 ) 到达时, 也无法确定其优
先级和滑动窗口内其他 3 条边优先级的大小关系, 难以确定是否应当采样 (v 1 ,v 7 ).