Tighter Estimation using Bottom-k Sketches

Summary: Proposes RC and SC estimators for bottom-k sketches, HT-inspired, tighter subpopulation weights with confidence bounds in distributed data. RC handles unknown total weight; SC uses known total weight, yielding strong gains on large subpops and datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9670
Venue: VLDB
Year: 2008
Pagerank: 6.6254568e-05
Overall Rank: 3,928 | 72.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen
2. Haim Kaplan

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
2,607	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4630211e-05
2,805	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	8.0918347e-05
3,824	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7260705e-05
5,415	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5196338e-05
7,645	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	4.6896215e-05
8,470	Sampling Big Ideas in Query Optimization	2023	PODS	4.5038423e-05
8,921	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	4.427232e-05
11,414	No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing	2022	VLDB	4.1945683e-05
12,166	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1945683e-05
12,344	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	4.1945683e-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
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
475	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00022303253
727	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017508726
2,090	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5647927e-05
4,504	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.1327917e-05
4,955	Estimating arbitrary subset sums with few probes	2005	PODS	5.8053317e-05
7,180	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	4.807579e-05
7,547	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	4.7144329e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
11,304	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	4.1945683e-05
4,237	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3333486e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
6,244	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.139669e-05
5,415	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5196338e-05
12,166	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1945683e-05
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