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: 1359
Venue: PODS
Year: 2005
Pagerank: 9.3068345e-05
Overall Rank: 2,013 | 86.20%
DOI: 10.1145/1065167.1065201

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T; Center for Discrete Mathematics and Theoretical Computer Science)
2. S. Muthukrishnan (Rutgers University)

BibTeX Citation

@inproceedings{cormode_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Space Efficient Mining of Multigraph Streams}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065201},
        doi = {10.1145/1065167.1065201},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and Muthukrishnan, S.},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,396	Estimating PageRank on Graph Streams	2008	PODS	0.00010921308
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
2,872	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	8.0104819e-05
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
4,503	Event Pattern Matching over Graph Streams	2015	VLDB	6.6597953e-05
4,613	On Sampling from Massive Graph Streams	2017	VLDB	6.6071509e-05
5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	6.2369655e-05
5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0994565e-05
5,802	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	6.0843083e-05
6,677	Information Complexity: a Tutorial	2010	PODS	5.8056405e-05
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-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
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
1,274	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011377527
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05
3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.6439415e-05
3,515	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	7.3540246e-05
5,349	Data Stream Query Processing: A Tutorial	2003	VLDB	6.256154e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB
2	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
3	4,739	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS
4	458	Counting Triangles in Data Streams	2006	PODS
5	4,613	On Sampling from Massive Graph Streams	2017	VLDB
6	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
7	564	Densest Subgraph in Streaming and MapReduce	2012	VLDB
8	4,500	Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage	2018	VLDB
9	4,236	On Dense Pattern Mining in Graph Streams	2010	VLDB
10	2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD