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

潘敏佳 等:面向时序图数据的快速环枚举算法 3833

加的内存和减少的内存的差值.但是在使用布隆过滤器的算法内均没有出现内存增加的现象,这是因为布隆过
滤器的正向遍历阶段已经将范围缩小的很多,导致继承的数量变少,hop 值占用也变少.
虽然不使用布隆过滤器的算法在较坏的情况下会出现一定的内存增加,但是由于 hop 值本身占用内存较
小,因此预计增加的内存会在可接受的范围内.表格中有些情况下,2SCENT 算法和本文算法占用的内存相同.这
是由于在使用布隆过滤器时,正向遍历时所占的内存比反向遍历时所占的小,hop 值会被用于正向遍历;而我们
记录的是两阶段中占用内存的最大值.
Table 5 Comparison between memory usage
表 5 获取元组算法内存比较表
2SCENT 本文
数据集 窗口及最大长度
Exact Bloom Exact Bloom
24h 4 1324 124 1143 120
Wiki-talk
36h 4 2787 230 1704 125
40h 5 31 38 17 16
CollegeMsg
50h 5 56 70 25 30
10h 4 254 421 84 421
Higgs
20h 4 529 521 125 521
8day 4 1049 377 1219 377
Stackoverflow
10day 4 1228 390 1338 390

4.5 总体比较
图 5 为算法在 4 个图上的总体运行时间比较图,其中,4 个图的长度限制分别为 4,5,4,4.我们取不同的窗口
大小作为横坐标,来衡量算法的时间表现.其中,2exact 表示 2SCENT 算法不使用布隆过滤器来获得四元组,
2bloom 表示 2SCENT 算法用布隆过滤器获得四元组,同理,exact 和 bloom 对应本文算法获取五元组的方式.由
图可见:在获取小于一定长度的环路时,本文算法的运行时间总是比 2SCENT 算法的运行时间短.且从折线的斜
率变化可得:图越大,2SCENT 算法所增加的时间越大,而本文算法可以使消耗时间的增加保持一个相对较为平
稳的趋势.也就是说,这样的时间差距会随着图的增大变得更为显著.因此,我们的算法对于图的扩大具有良好
的稳定性.

Time (s) Time (s)

(a) Wiki-talk (b) College

Time (s) Time (s)

(c) Higgs (d) Stackoverflow
Fig.5 Comparison with different time windows
图 5 不同时间窗口比较图