On Sampling from Massive Graph Streams

Summary: GPS is an order-based reservoir sampling framework for graphs, weighting edge samples to optimize subgraph estimation. Separates sampling from estimation (post- and in-stream) with a Martingale-based unbiased estimator; yields <1% error on subgraph counts while using <0.01% of edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11427
Venue: VLDB
Year: 2017
Pagerank: 5.8459467e-05
Overall Rank: 4,898 | 65.93%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,626	Efficient Biclique Counting in Large Bipartite Graphs	2023	SIGMOD	6.0399035e-05
5,518	Hypergraph Motifs: Concepts, Algorithms, and Discoveries	2020	VLDB	5.4621935e-05
10,276	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	4.1945683e-05
10,623	Efficient and Adaptive Estimation of Local Triadic Coefficients	2025	VLDB	4.1945683e-05
10,871	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
595	Estimating PageRank on Graph Streams	2008	PODS	0.00019507721
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
1,472	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011828662

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
1,472	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011828662
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-05
3,063	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	7.6321424e-05
10,586	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.1945683e-05
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1945683e-05
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
4,879	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8575676e-05
5,046	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7405307e-05