Page 166 - 《软件学报》2020年第12期

3832 Journal of Software 软件学报 Vol.31, No.12, December 2020

点是合并五元组所需的时间变少,这一点可以结合表 2 得到;第 2 点是 hop 值避免了大量不必要的三元组更新
与继承.在大多数图里,第 2 点节约的时间超过第 1 点.
Table 3 Comparison between time of getting tuples
表 3 获取元组时间比较
2SCENT 本文
数据集 窗口及最大长度
Exact Bloom Exact Bloom
24h 4 136.0 152.5 92.4 120.8
Wiki-talk
36h 4 294.4 263 142.6 159.6
40h 5 18.0 23.4 6.5 8.4
CollegeMsg
50h 5 30.2 41.3 10 12.9
10h 4 31.7 11.0 9.3 7.7
Higgs
20h 4 63.8 17.5 13.4 8.9
8day 4 131.4 218.3 101.5 191.8
Stackoverflow
10day 4 169.4 256 111.4 203.0

4.3.2 寻找环路时间
表 4 展示了利用不同方式获得的元组来进行动态深度优先搜索所消耗的时间.首先进行横向比较,即同一
算法下,不使用布隆过滤器和使用布隆过滤器获得的元组,它们在进行搜索时消耗的时间也会有不同.从表中可
见:对类似 CollegeMsg,Wiki-talk 和 Stackoverflow 的图来说,两种方式下搜索的时间大致相同.但是在 higgs 图中
却有较大的区别.产生这样的区别的原因在于:采用布隆过滤器的方式有时也能进一步缩小候选节点集合,但是
缩小的程度因图而异.

Table 4 Comparison between time for dynamic bfs
表 4 动态深度优先搜索算法时间比较
2SCENT 本文
数据集 窗口及最大长度
Exact Bloom Exact Bloom
24h 4 35.1 34 29.7 28.8
Wiki-talk
36h 4 60.7 60.5 41.3 41.7
40h 5 44.9 44.3 18.9 18.9
CollegeMsg
50h 5 260.5 257.9 116.2 112.6
10h 4 8.5 3.8 3.9 2.2
Higgs
20h 4 66.9 50.0 15.8 11.8
8day 4 53.7 53.0 44.0 43.1
Stackoverflow
10day 4 81.0 78.0 46.6 46.0
接下来比较 2SCENT 算法与本文算法,显然,我们的算法在获取小于等于某一长度的时序环时消耗的时间
比原算法少,有时减少的时间可以达到之前的 70%以上.算法起效的原因主要有 3 个方面:第一,一般而言,长环
路的搜索更为复杂,搜索时间更长,因此我们减少的五元组可以使搜索时间有一定的提升;第二,我们的算法进
一步减少了候选节点集合的大小,这避免了一部分初始化工作;第三,我们在达到限制长度时及时地停止了搜
索,避免为产生不符合要求的环消耗时间.
4.4 运行内存比较

表 5 为获取候选元组(不包括元组合并)阶段,算法在运行过程中所占用的最大内存.首先,我们可以发现:使
用布隆过滤器相对于原始的方式总是可以节约大量内存;且随着时间窗口的增大,内存的增长并不大,这体现了
布隆过滤器在节约内存方面的巨大作用.
在表格中,除了 stackoverflow,在其他图上,本文算法的内存占用总是优于原算法.在该图上,内存消耗反而
增加.为了分析这一现象可能发生的原因,我们将 wiki-talk 与 stackoverflow 作对比可以看到:两者的时间下降比
例较为相似,但是在内存表现上却差距较大.我们通过实验观察了这两个图在算法运行过程中所避免继承的三
7
6
元组数量的情况,我们发现:在 wiki-talk 中,这个值大约为 3.4×10 ;而在 stackoverflow 中,这个值约为 4.6×10 ,其
中存在着较大的差距.这是由于相对于 2SCENT 算法,我们的算法由于引入了 hop 值增加了一定的内存占用,但
是也因为 hop 避免了一部分三元组继承以减少内存占用.因此,总体内存相对于 2SCENT 算法的增减来自于增