Tighter Estimation using Bottom k Sketches

Summary: Derives unbiased Horvitz–Thompson-based rank- and subset-conditioning estimators plus confidence bounds for predicate-defined weights in bottom-k sketches. RC handles unknown total sketch weight; SC exploits known totals, yielding tighter estimates and bounds. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9861
Venue: VLDB
Year: 2008
Pagerank: 7.376137e-05
Overall Rank: 3,481 | 76.12%
DOI: 10.14778/1453856.1453883

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (AT&T)
2. Haim Kaplan (Tel Aviv University)

BibTeX Citation

@article{cohen_vldb08,
        title = {{Tighter Estimation using Bottom k Sketches}},
        author = {Cohen, Edith and Kaplan, Haim},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {213--224},
        doi = {10.14778/1453856.1453883},
        url = {https://doi.org/10.14778/1453856.1453883},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
2,792	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	8.1191853e-05
3,228	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6215176e-05
5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	6.0155431e-05
7,433	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.6197531e-05
8,379	Sampling Big Ideas in Query Optimization	2023	PODS	5.4378437e-05
9,076	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	5.3251649e-05
10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	5.093636e-05
11,612	No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing	2022	VLDB	5.093636e-05
12,362	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	5.093636e-05
12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	5.093636e-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
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
2,610	Maintaining Time-Decaying Stream Aggregates	2003	PODS	8.347507e-05
4,321	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.7617825e-05
4,761	Estimating arbitrary subset sums with few probes	2005	PODS	6.5196044e-05
7,641	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	5.5766204e-05
7,815	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	5.538404e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB
2	10,162	On Sketching Trimmed Statistics	2026	PODS
3	11,503	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB
4	4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD
5	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
6	5,998	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD
7	5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
8	12,362	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS
9	12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB
10	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD