Reservoir-based sampling over large graph streams to estimate triangle counts and node degrees
Reservoir-based sampling over large graph streams to estimate triangle counts and node degrees
复制标题
对大型图流进行基于水库的采样，以估计三角形计数和节点度
DOI：
10.1016/j.future.2020.02.077
复制
发表时间：
2020-07
影响因子：
7.5
通讯作者：
Xie Yanwen
中科院分区：
文献类型：
--
作者：
Zhang Lingling;Jiang Hong;Wang Fang;Feng Dan;Xie Yanwen
水库采样被广泛采用，通过产生边缘样本来表征大型图流。然而，现有的基于三角形的采样方法主要集中在三角形的计数上，而在分析节点度所反映的拓扑特征方面表现不佳。本文提出了一种新的方法，称为三角形诱导水库采样，或T样本，三角形计数和估计节点度的同时，有效地。T-Sample对图流中的每条边只进行一次处理，同时设计了一种双重采样机制，既可以进行均匀采样，也可以进行非均匀采样。具体来说，T-Sample的均匀采样是用来计数三角形的一个新提出的方法与更小的估计方差比现有的基于采样方法，而它的非均匀采样，确保边缘样本连接。在真实的数据集上的实验结果表明，T-Sample方法能够以更小的估计误差和方差对三角形进行计数，同时以更小的时间和内存开销获得更准确的节点度信息。
Reservoir sampling is widely employed to characterize large graph streams by producing edge samples. However, existing reservoir-based sampling methods mainly focus on counting triangles but perform poorly in analyzing topological characteristics reflected by node degrees. This paper proposes a new method, called triangle-induced reservoir sampling, or T-Sample, to count triangles and estimate node degrees simultaneously and efficiently. While every edge in a graph stream is processed only once by T-Sample, a dual sampling mechanism performing both uniform sampling and non-uniform sampling is carefully designed. Specifically, T-Sample’s uniform sampling is used to count triangles by a newly proposed method with smaller estimation variances than existing reservoir-based sampling methods; whereas, its non-uniform sampling ensures that edge samples are connected. Experimental results driven by real datasets show that T-Sample can count triangles with smaller estimation errors and variances than the state-of-the-art reservoir-based sampling methods while obtaining much more accurate information about node degrees at smaller time and memory costs.
登录
查看更多内容
DOI：
10.1016/b978-0-12-404627-6.00002-6
发表时间：
2013
期刊：
--
影响因子：
--
作者：
D. Marinescu
通讯作者：
D. Marinescu
DOI：
10.1007/978-3-030-10767-3_4
发表时间：
2019
期刊：
Studies in Computational Intelligence
影响因子：
--
作者：
Alireza Rezvanian;Behnaz Moradabadi;Mina Ghavipour;M. D. Khomami;M. Meybodi
通讯作者：
Alireza Rezvanian;Behnaz Moradabadi;Mina Ghavipour;M. D. Khomami;M. Meybodi
DOI：
10.1145/1879141.1879192
发表时间：
2010-02
期刊：
--
影响因子：
--
作者：
Bruno Ribeiro;D. Towsley
通讯作者：
Bruno Ribeiro;D. Towsley
DOI：
10.1007/978-3-642-31235-9_13
发表时间：
2012-06
期刊：
--
影响因子：
--
作者：
Xuesong Lu;S. Bressan
通讯作者：
Xuesong Lu;S. Bressan
DOI：
10.14778/2556549.2556569
发表时间：
2013-09
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
A. Pavan;Kanat Tangwongsan;Srikanta Tirthapura;Kun-Lung Wu
通讯作者：
A. Pavan;Kanat Tangwongsan;Srikanta Tirthapura;Kun-Lung Wu