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: 10100
Venue: VLDB
Year: 2009
Pagerank: 5.6001388e-05
Overall Rank: 7,554 | 48.18%
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,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
5,860	Understanding Cardinality Estimation using Entropy Maximization	2010	PODS	6.0636893e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,206	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.6731116e-05
7,433	Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations	2015	VLDB	5.6197531e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
100	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034385207
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
1,729	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.908788e-05
1,936	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.4557372e-05
2,121	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.1402718e-05
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.2946291e-05
4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.4600939e-05

Semantically Similar Papers

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