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: 1584
Venue: PODS
Year: 2012
Pagerank: 4.1905499e-05
Overall Rank: 12,116 | 15.80%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

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
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,352	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	4.1905499e-05
3,273	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2899198e-05
2,269	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1507118e-05
10,905	Streaming Algorithms with Few State Changes	2024	PODS	4.1905499e-05
12,174	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1905499e-05
4,912	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	5.8342232e-05
11,841	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1905499e-05
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1905499e-05
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05
5,119	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6774637e-05