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.5250686e-05
Overall Rank: 4,018 | 72.08%
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.00027398081
1,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
2,752	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1723418e-05
3,220	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.3590708e-05
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
3,621	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9022467e-05
6,697	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	4.9538866e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-05
7,460	Compact Histograms for Hierarchical Identifiers	2006	VLDB	4.7198214e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
10,647	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1905499e-05
12,528	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.1905499e-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.0040465394
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
527	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020862475
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
4,050	What can Hierarchies do for Data Warehouses?	1999	VLDB	6.4952391e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,785	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7658346e-05
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
12,699	Hierarchical Compact Cube for Range-Max Queries	2000	VLDB	4.1905499e-05
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
1,363	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012380611
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
1,116	Global Optimization of Histograms	2001	SIGMOD	0.00013863484
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
3,621	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9022467e-05