Consistent Histograms In The Presence of Distinct Value Counts

Summary: Extends self-tuning histograms beyond cardinalities by incorporating distinct-value counts, using entropy maximization for least-assumption modeling. Introduces an efficient one-pass L2-minimization algorithm that achieves comparable accuracy to EM at far lower computational cost. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h98aef31326cc395d
Venue: VLDB
Year: 2009
Pagerank: 5.4767414e-05
Overall Rank: 7,639 | 48.66%
DOI: 10.14778/1687627.1687723

Incoming Non-self Citations Over Time

Authors

1. Raghav Kaushik (Microsoft)
2. Dan Suciu (University of Washington)

BibTeX Citation

@article{kaushik_vldb09,
        title = {{Consistent Histograms In The Presence of Distinct Value Counts}},
        author = {Kaushik, Raghav and Suciu, Dan},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687723},
        url = {https://doi.org/10.14778/1687627.1687723},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,155	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777046
5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9534254e-05
5,974	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS	5.9279222e-05
7,334	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.5473714e-05
7,567	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.4933119e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034099838
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.0002378554
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022404363
284	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022205848
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
429	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018445263
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017955913
644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015209065
743	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014309723
1,743	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7342409e-05
1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3511556e-05
2,142	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9644817e-05
2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4742372e-05
3,646	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1368554e-05
5,007	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.3156906e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
2	6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD
3	1,743	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB
4	1,687	Global Optimization of Histograms	2001	SIGMOD
5	743	Dynamic Multidimensional Histograms	2002	SIGMOD
6	275	Optimal Histograms with Quality Guarantees	1998	VLDB
7	119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD
8	9,151	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
9	454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD
10	284	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD