Database Paper Browser

Back to papers

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.1945683e-05
Overall Rank
12,108 | 15.77%
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
Previous Page 1 / 1 Next

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
378 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.0002497492
3,041 Sketching Probabilistic Data Streams 2007 SIGMOD 7.6697078e-05
3,385 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.1580391e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,344 Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets 2009 VLDB 4.1945683e-05
3,271 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.2968732e-05
2,282 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1073603e-05
10,901 Streaming Algorithms with Few State Changes 2024 PODS 4.1945683e-05
12,166 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.1945683e-05
4,905 Randomized Error Removal for Online Spread Estimation in Data Streaming 2021 VLDB 5.8398332e-05
11,833 Streaming Algorithms for Robust Distinct Elements 2016 SIGMOD 4.1945683e-05
10,983 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD 4.1945683e-05
3,385 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.1580391e-05
5,117 Sampling Algorithms in a Stream Operator 2005 SIGMOD 5.6825418e-05