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: 1209
Venue: PODS
Year: 2000
Pagerank: 7.2946291e-05
Overall Rank: 3,575 | 75.48%
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
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
2,638	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	8.3130624e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.6057671e-05
4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.4600939e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,547	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	5.8444303e-05
7,375	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.6299286e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.6001388e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
12,712	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	5.093636e-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.0024089429
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
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
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
4,427	What can Hierarchies do for Data Warehouses?	1999	VLDB	6.7095871e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,136	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS
2	35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
3	12,883	Hierarchical Compact Cube for Range-Max Queries	2000	VLDB
4	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
5	1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD
6	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
7	1,668	Global Optimization of Histograms	2001	SIGMOD
8	786	Universality of Serial Histograms	1993	VLDB
9	267	Optimal Histograms with Quality Guarantees	1998	VLDB
10	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS