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: 9671
Venue: VLDB
Year: 2008
Pagerank: 6.6195837e-05
Overall Rank: 3,930 | 72.69%
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,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
2,609	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4587236e-05
2,811	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	8.0840418e-05
3,827	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7195959e-05
5,423	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5143276e-05
7,644	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	4.6853638e-05
8,467	Sampling Big Ideas in Query Optimization	2023	PODS	4.4995247e-05
8,924	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	4.4229886e-05
11,417	No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing	2022	VLDB	4.1905499e-05
12,174	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1905499e-05
12,352	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	4.1905499e-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.00036655704
481	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.000221538
737	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017377393
2,094	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5556069e-05
4,506	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.1273675e-05
4,961	Estimating arbitrary subset sums with few probes	2005	PODS	5.7992561e-05
7,181	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	4.8030491e-05
7,545	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	4.7099128e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,116	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1905499e-05
3,516	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.018912e-05
11,306	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	4.1905499e-05
4,239	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3273184e-05
9,244	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3648789e-05
6,243	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.1348218e-05
5,423	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5143276e-05
12,174	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1905499e-05
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