Space Efficient Mining of Multigraph Streams

Summary: Space-efficient streaming algorithms for multigraph degree analysis (frequency moments, heavy hitters, range sums) that correct multiplicity bias from repeated edges. Novel cascaded summaries—nesting sketches, sampling, hashing and distinct counting—yield provable sublinear space bounds and strong empirical accuracy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1360
Venue: PODS
Year: 2005
Pagerank: 0.00011828662
Overall Rank: 1,472 | 89.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode
2. S. Muthukrishnan

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
595	Estimating PageRank on Graph Streams	2008	PODS	0.00019507721
2,266	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1540815e-05
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
2,607	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4630211e-05
3,566	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9629443e-05
4,898	On Sampling from Massive Graph Streams	2017	VLDB	5.8459467e-05
4,905	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	5.8398332e-05
5,031	Event Pattern Matching over Graph Streams	2015	VLDB	5.7499783e-05
5,594	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4192122e-05
5,782	Information Complexity: a Tutorial	2010	PODS	5.3292726e-05
5,968	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2503253e-05
7,334	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	4.7604215e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
323	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027492196
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
1,222	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00013213129
3,050	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.6512619e-05
3,102	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5586568e-05
3,541	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	6.9935367e-05
5,038	Data Stream Query Processing: A Tutorial	2003	VLDB	5.7432219e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
7,031	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	4.8561505e-05
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
4,898	On Sampling from Massive Graph Streams	2017	VLDB	5.8459467e-05
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-05
644	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018748988
4,879	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8575676e-05
4,089	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4587806e-05
2,607	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4630211e-05