Estimating Statistical Aggregates on Probabilistic Data Streams

Summary: Provides one-pass streaming algorithms for aggregates on probabilistic streams: first improved estimator for expected mean, first one-pass median, and the first streaming F0 (distinct count) algorithm. Introduces a general reduction using unbiased estimators to extend deterministic F2 algorithms to probabilistic data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1433
Venue: PODS
Year: 2007
Pagerank: 7.8907087e-05
Overall Rank: 2,988 | 79.51%
DOI: 10.1145/1265530.1265565

Incoming Non-self Citations Over Time

Authors

1. T. S. Jayram (IBM)
2. Andrew McGregor (University of California San Diego)
3. S. Muthukrishan (Google)
4. Erik Vee (IBM; Yahoo)

BibTeX Citation

@inproceedings{jayram_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Estimating Statistical Aggregates on Probabilistic Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265565},
        doi = {10.1145/1265530.1265565},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jayram, T. S. and McGregor, Andrew and Muthukrishan, S. and Vee, Erik},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	8.8664016e-05
2,697	Sketching Probabilistic Data Streams	2007	SIGMOD	8.2451054e-05
3,050	Event Queries on Correlated Probabilistic Streams	2008	SIGMOD	7.8140428e-05
3,483	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.372823e-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
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 8 of 8 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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
2,172	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.0394311e-05
2,697	Sketching Probabilistic Data Streams	2007	SIGMOD	8.2451054e-05
5,241	Load Management and High Availability in the Medusa Distributed Stream Processing System	2004	SIGMOD	6.3019989e-05
5,565	Efficient Allocation Algorithms for OLAP over Imprecise Data	2006	VLDB	6.171506e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,604	Approximate Quantiles and the Order of the Stream	2006	PODS
2	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
3	551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD
4	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
5	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
6	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
7	6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
8	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
9	12,467	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
10	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD