Page 445 - 《软件学报》2025年第9期
P. 445

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


                                                      p(3), 将样本图中的三角形数目除以该概率, 便可以估算滑动窗口
                 窗口中的一个三角形被加入样本图的概率即为
                 中的三角形数目. 然而, 为了计算         p(3), 需要估算滑动窗口中的边数        |W|. 如第  2.1  节所述, 虽然滑动窗口在时间尺
                 度的长度是固定的, 但是其中的边数会随着图流流量而变化. 一方面, 算法无法发现滑动窗口中非样本边的过期,
                 另一方面, 在二项计数语义下, 需要估算去除重复边的互异边数目, 这都导致了估算的困难. SWTC                           首先计算与滑
                 动窗口相交的两个片段内的边数            |SL old +SL new |, 然后再根据  |SL old +SL new | 进一步估算滑动窗口中的边数  |W|. 下面
                 分别对这两个步骤进行介绍.

                    为了估算    |SL old +SL new |, SWTC 借助了经典的基数估算算法  Hyperloglog sketch [38] . Hyperloglog sketch 需要为
                 每一条边计算一个服从概率为           1/2 的几何分布的权重, 并在每个子流中保存目标区间内的权重最大值. 结合                      K  个
                 子流中保存的最大权重, 它便可以估算出目标权重内的边数. 原本的 Hyperloglog sketch                使用哈希函数进行子流划
                 分和权重生成, 以估算互异边的数目, 但如果将哈希函数替换为随机函数, 它也能支持含重复边的计数. SWTC 已
                 经为每条边计算了一个服从均匀分布的优先级                 G(e), 可以将该优先级转换为服从概率为           1/2 的几何分布的权重,
                                          ⌉
                               ⌈
                          R(e) = −log(1−G(e)) . 不难发现,  G(e) 越大,
                 计算方式为                                       R(e) 也越大, 因此. 在一个子流     S i  中, 最近两个片段  SL old
                                                                               β 和   中的优先级较高者. 我们可
                                                                                  ϵ
                 和   SL new  内  G(e) 最大的边, 也就是  R(e) 最大的边, 而这条边就是该子流中保存的
                 以根据这条边的优先级, 直接计算出子流             S i  中在   SL old +SL new  内的最大  R(e), 记为  . 所有  K  个子流的   组成了
                                                                                                 R i
                                                                                 R i
                 一个 Hyperloglog sketch, 可以使用文献     [38] 中的提供的公式估算       |SL old +SL new |, 具体公式为  |SL old +SL new | =
                   α K K 2
                   K    , 其中
                 ∑           α K = 0.7213/(1+1.079/K).
                     2 −R i
                   i=1
                    有了   |SL old +SL new |, 就可以进一步估算滑动窗口内的边数      |W|. 作者证明一个子流中获得有效样本的概率为
                                                                                                      K
                 p = |W|/|SL new +SL old |, 而这一概率又可以通过  m/K 计算, 也就是用产生有效样本的子流数目          m 除以子流总数  .
                 因此可以按照     |W| = m/K ×|SL old +SL new | 来估算滑动窗口内的边数.
                    当使用哈希函数实现子流划分函数             H(·) 和优先级计算函数      G(·) 时, 可以估算出滑动窗口内去重后的互异常
                 边的数目, 用于二项计数语义下的估算, 而使用随机函数时, 可以估算出包含重复边在内的边数, 用于带权计数语
                 义下的估算. 这也和上文中采样方法的设置一致.
                                                                            p(3), 我们可以将滑动窗口内的三角
                    ● 滑动窗口内三角形数目的估算: 有了每个三角形被加入样本图的概率
                 形数目则估算为      τ/p(3), 其中  τ 为样本图中的三角形数目. SWTC 算法在图流更新的过程中持续更新                   τ 的值, 每
                                                                          τ 上. 而当样本边因过期而被删除, 或者
                 当有新样本边被加入样本集时, 算法计数该边引入的三角形数目并累加到
                 被同一个子流中优先级更高的新边替换时, 算法计数因为该边删除而减少的三角形数目并从                              τ 中减去.
                    ● 改进方案——分组异步采样: SWTC 中的样本边数目会随着时间推移发生周期性变化. 当前时间恰好在路
                 径点时, 滑动窗口只和一个片段相交            (即情况  3), 样本边数目达到最大值, 之后则逐步降低, 在即将到达下一个路
                 径点时达到最小值. 为了避免样本集大小的波动带来估算准确率的不稳定, Gou                        等人  [16] 又提出了名为分组异步采
                                             K  个子流分为若干组, 每组采用不同的路径点进行图流切分, 以此来保证各组
                 样的改进方案. 该方案中, SWTC 将
                 的样本边数目此消彼长, 总体的样本集合大小则保持稳定.
                    下文中, 我们将以 SWTC 的采样算法为基础, 构建            CBS 算法.

                 2.3   采样前计数策略
                    采样前计数策略最早在         TRIEST [17] 文献中被提出, 在后续工作 ThinkD   [18]  中被进一步改进. 该策略的核心思想
                 是充分利用图流中每一条边的拓扑信息, 估算该边的添加或者删除给全图三角形数目带来的增加值或减少值. 假
                                                                    e
                 设已有一个样本图       G s , 对于图流中每条新加入的边       e, 该策略估算   在快照图中构成的新三角形集合             ∆ 的大小. 为
                                   e
                 了估算   |∆|, 该策略查找   在  G s  中构成的三角形集合  . 可知     ∆ 中的一个三角形被计入        ∆ s  的充要条件为该三角形
                                                         ∆ s
                 除了   e 之外的两条边均被采样, 因此       |∆| = |∆ s |/p(2), 其中  p(2) 表示图流中给定的两条边被采样的概率, 具体值由采
                                              τ 计数快照图中的三角形数目估算值, 并在每条新边   到达时按照上述方法
                                                                                       e
                 样算法决定. 该策略使用一个计数器
                 估算其在快照图中构成的三角形数目             |∆|, 将其累加到  τ 上, 之后再调用采样算法, 决定        e 是否被加入样本图      G s . 采
   440   441   442   443   444   445   446   447   448   449   450