Optimal Histograms with Quality Guarantees

Summary: Optimal histograms with quality guarantees: compute bucket boundaries to minimize error for a fixed bucket count under broad metrics (incl. V-Optimality); time O(d^2) in distinct values. Also offers fast heuristics with provable space–accuracy tradeoffs and per-selectivity guarantees to isolate outliers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8495
Venue: VLDB
Year: 1998
Pagerank: 0.00027358981
Overall Rank: 326 | 97.74%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
8,090	Probabilistic Histograms for Probabilistic Data	2009	VLDB	4.5888589e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,079	Path Cost Distribution Estimation Using Trajectory Data	2017	VLDB	4.400728e-05
9,240	ZIP: Lazy Imputation during Query Processing	2024	VLDB	4.3690661e-05
9,928	Fainder: A Fast and Accurate Index for Distribution-Aware Dataset Search	2024	VLDB	4.2511622e-05
9,950	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	4.2421586e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
11,434	Data-Independent Space Partitionings for Summaries	2021	PODS	4.1945683e-05
11,727	Vocalizing Large Time Series Efficiently	2018	VLDB	4.1945683e-05
11,821	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1945683e-05
11,915	DocRicher: An Automatic Annotation System for Text Documents Using Social Media	2015	SIGMOD	4.1945683e-05
12,060	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.1945683e-05
12,484	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.1945683e-05
12,519	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
808	Universality of Serial Histograms	1993	VLDB	0.00016432772

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,879	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.2908101e-05
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-05
4,017	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.524501e-05
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211