Optimal Histograms for Hierarchical Range Queries (Extended Abstract)

Summary: Shows equality-optimized histograms are suboptimal for hierarchical range queries in OLAP and casts histogram design as expected-error minimization under a space budget. Presents polynomial-time DP algorithms for one-sided (V-Optimal runtime), balanced-tree, and general hierarchies with provable optimality and empirical error reductions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h5907a0b4005bd3b0
Venue: PODS
Year: 2000
Pagerank: 7.1399991e-05
Overall Rank: 3,644 | 75.51%
DOI: 10.1145/335168.335223

Incoming Non-self Citations Over Time

Authors

1. Nick Koudas (AT&T)
2. S. Muthukrishnan (AT&T)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{koudas_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Optimal Histograms for Hierarchical Range Queries (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/335168.335223},
        doi = {10.1145/335168.335223},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koudas, Nick and Muthukrishnan, S. and Srivastava, Divesh},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
2,688	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	8.1265396e-05
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05
3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4424817e-05
5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.3186165e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-05
6,557	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	5.7498216e-05
7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.5103311e-05
7,512	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.504973e-05
7,633	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4792473e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05
13,002	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
806	Universality of Serial Histograms	1993	VLDB	0.00013792174
4,529	What can Hierarchies do for Data Warehouses?	1999	VLDB	6.5592604e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,187	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS
2	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
3	13,173	Hierarchical Compact Cube for Range-Max Queries	2000	VLDB
4	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
5	1,106	Range Queries in OLAP Data Cubes	1997	SIGMOD
6	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
7	1,687	Global Optimization of Histograms	2001	SIGMOD
8	806	Universality of Serial Histograms	1993	VLDB
9	275	Optimal Histograms with Quality Guarantees	1998	VLDB
10	5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS