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.00011838607
Overall Rank: 1,466 | 89.82%
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
589	Estimating PageRank on Graph Streams	2008	PODS	0.00019569121
2,271	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1467959e-05
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
2,609	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4587236e-05
3,557	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9711051e-05
4,903	On Sampling from Massive Graph Streams	2017	VLDB	5.8403259e-05
4,912	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	5.8342232e-05
5,017	Event Pattern Matching over Graph Streams	2015	VLDB	5.7505967e-05
5,602	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4153555e-05
5,792	Information Complexity: a Tutorial	2010	PODS	5.3241505e-05
5,975	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2452824e-05
7,329	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	4.7559363e-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.00072660894
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
324	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027465124
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
1,222	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00013205769
3,108	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5547127e-05
3,123	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5270618e-05
3,543	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	6.9884064e-05
5,037	Data Stream Query Processing: A Tutorial	2003	VLDB	5.7390577e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
12,116	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1905499e-05
7,033	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	4.8514885e-05
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
4,903	On Sampling from Massive Graph Streams	2017	VLDB	5.8403259e-05
11,323	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1905499e-05
645	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018727714
4,883	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB	5.8519327e-05
4,092	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4525563e-05
2,609	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4587236e-05