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: hd4000b630203971b
Venue: VLDB
Year: 2008
Pagerank: 7.2161972e-05
Overall Rank: 3,540 | 76.21%
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,186	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.8916948e-05
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
2,852	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	7.9412916e-05
3,090	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6584982e-05
6,118	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.8813101e-05
7,561	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.4958573e-05
8,553	Sampling Big Ideas in Query Optimization	2023	PODS	5.3158971e-05
9,251	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	5.2056825e-05
10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9793485e-05
11,920	No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing	2022	VLDB	4.9793485e-05
12,653	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.9793485e-05
12,828	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	4.9793485e-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
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001832766
707	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014640173
2,659	Maintaining Time-Decaying Stream Aggregates	2003	PODS	8.161764e-05
4,408	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.6122752e-05
4,870	Estimating arbitrary subset sums with few probes	2005	PODS	6.3737999e-05
7,792	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	5.4516538e-05
7,973	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	5.4149919e-05

Semantically Similar Papers

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