Sketching Probabilistic Data Streams

Summary: First sublinear-space, sublinear-time algorithms for aggregating probabilistic data streams under possible-worlds semantics. Introduces concise streaming sketches extending conventional sketching to probabilistic streams to approximate distributions of complex aggregates (distinct counts, joins) with randomized guarantees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5f9c0eb2732ea251
Venue: SIGMOD
Year: 2007
Pagerank: 8.0692701e-05
Overall Rank: 2,738 | 81.60%
DOI: 10.1145/1247480.1247513

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Minos Garofalakis (University of California Berkeley; Yahoo)

BibTeX Citation

@inproceedings{cormode_sigmod07,
        title = {{Sketching Probabilistic Data Streams}},
        author = {Cormode, Graham and Garofalakis, Minos},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247513},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247513},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,307	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	8.6661766e-05
3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.723493e-05
3,112	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.6351481e-05
3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4194442e-05
6,177	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.8582407e-05
6,255	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.8326825e-05
6,850	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.6635511e-05
8,193	Probabilistic Histograms for Probabilistic Data	2009	VLDB	5.3789502e-05
8,484	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.330748e-05
10,385	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	4.9769913e-05
12,602	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.9769913e-05
12,764	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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.00052097907
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042926566
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035962466
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035960573
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211
429	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018445263
843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013534623
1,290	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011155963
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0569441e-05
3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.723493e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
2	7,868	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
3	6,255	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
4	7,921	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB
5	1,067	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
6	8,193	Probabilistic Histograms for Probabilistic Data	2009	VLDB
7	7,875	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
8	3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
9	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
10	12,764	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB