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: 1210
Venue: PODS
Year: 2000
Pagerank: 6.524501e-05
Overall Rank: 4,017 | 72.06%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
3,313	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.2381634e-05
3,619	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9084829e-05
6,694	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	4.9586454e-05
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-05
7,459	Compact Histograms for Hierarchical Identifiers	2006	VLDB	4.7243492e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
12,519	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.1945683e-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.0040449103
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
4,043	What can Hierarchies do for Data Warehouses?	1999	VLDB	6.5015013e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,781	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7723513e-05
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
12,690	Hierarchical Compact Cube for Range-Max Queries	2000	VLDB	4.1945683e-05
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
1,359	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.0001238588
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
3,619	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9084829e-05