Space-Efficient Estimation of Statistics over Sub-Sampled Streams

Summary: Characterizes space-efficient estimation of original-stream statistics (frequency moments, support size, entropy, heavy hitters) when only sub-sampled stream observations are available. Presents algorithms with matching upper and lower bounds that tightly characterize space complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1583
Venue: PODS
Year: 2012
Pagerank: 5.093636e-05
Overall Rank: 12,305 | 15.58%
DOI: 10.1145/2213556.2213594

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Andrew McGregor (University of Massachusetts Amherst)
2. A. Pavan (Iowa State University)
3. Srikanta Tirthapura (Iowa State University)
4. David P. Woodruff (IBM)

BibTeX Citation

@inproceedings{mcgregor_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Space-Efficient Estimation of Statistics over Sub-Sampled Streams}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213594},
        doi = {10.1145/2213556.2213594},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {McGregor, Andrew and Pavan, A. and Tirthapura, Srikanta and Woodruff, David P.},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
2,697	Sketching Probabilistic Data Streams	2007	SIGMOD	8.2451054e-05
2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.8907087e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
2	2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB
3	11,123	Streaming Algorithms with Few State Changes	2024	PODS
4	12,362	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS
5	5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB
6	12,034	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
7	10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
8	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
9	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
10	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD