Fast Algorithms For Hierarchical Range Histogram Construction

Summary: Near-linear-time algorithms for constructing histograms of measure distributions under hierarchical range selections, using dynamic programming and a novel "sparse intervals" concept. First practical, space-for-time tradeoff approach preserving accuracy with empirical validation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h48ee1f23808a17a9
Venue: PODS
Year: 2002
Pagerank: 6.2950911e-05
Overall Rank: 5,031 | 66.28%
DOI: 10.1145/543613.543637

Incoming Non-self Citations Over Time

Authors

1. Sudipto Guha (University of Pennsylvania)
2. Nick Koudas (AT&T)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{guha_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Fast Algorithms For Hierarchical Range Histogram Construction}},
        url = {https://dl.acm.org/doi/10.1145/543613.543637},
        doi = {10.1145/543613.543637},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Guha, Sudipto and Koudas, Nick and Srivastava, Divesh},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011759683
3,168	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5583423e-05
3,660	Extreme Visualization: Squeezing a Billion Records into a Million Pixels	2008	SIGMOD	7.1047369e-05
6,312	Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies	2008	SIGMOD	5.7971119e-05
7,536	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.4844135e-05
7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4588598e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0023948467
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
277	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002235043
3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4165176e-05
3,653	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1149642e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,850	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
2	4,056	Hierarchical Cubes for Range-Sum Queries	1999	VLDB
3	3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
4	171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
5	13,220	Hierarchical Compact Cube for Range-Max Queries	2000	VLDB
6	222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
7	1,110	Range Queries in OLAP Data Cubes	1997	SIGMOD
8	745	Dynamic Multidimensional Histograms	2002	SIGMOD
9	5,552	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
10	3,653	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS