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: 3920
Venue: SIGMOD
Year: 2007
Pagerank: 8.2451054e-05
Overall Rank: 2,697 | 81.50%
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,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	8.8664016e-05
2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.8907087e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-05
6,049	PODS: A New Model and Processing Algorithms for Uncertain Data Streams	2010	SIGMOD	5.9949334e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05
6,712	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.7962014e-05
8,059	Probabilistic Histograms for Probabilistic Data	2009	VLDB	5.4979799e-05
8,310	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.4556836e-05
10,156	Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity	2026	PODS	5.093636e-05
12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	5.093636e-05
12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	5.093636e-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.00052982574
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
1,274	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011377527
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.8907087e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
2	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
3	6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
4	7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB
5	1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
6	8,059	Probabilistic Histograms for Probabilistic Data	2009	VLDB
7	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
8	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
9	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
10	12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB