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: 8686
Venue: VLDB
Year: 1998
Pagerank: 0.00022798161
Overall Rank: 267 | 98.17%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (AT&T)
2. Nick Koudas (University of Toronto)
3. S. Muthukrishnan (Bell Labs)
4. Viswanath Poosala (Bell Labs)
5. Ken Sevcik (University of Toronto)
6. Torsten Suel (Bell Labs)

BibTeX Citation

@article{jagadish_vldb98,
        title = {{Optimal Histograms with Quality Guarantees}},
        author = {Jagadish, H. V. and Koudas, Nick and Muthukrishnan, S. and Poosala, Viswanath and Sevcik, Ken and Suel, Torsten},
        journal = {PVLDB},
        series = {{VLDB} '98},
        pages = {275--286},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.6001388e-05
8,059	Probabilistic Histograms for Probabilistic Data	2009	VLDB	5.4979799e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,230	Path Cost Distribution Estimation Using Trajectory Data	2017	VLDB	5.3017894e-05
9,285	ZIP: Lazy Imputation during Query Processing	2024	VLDB	5.292293e-05
10,080	Fainder: A Fast and Accurate Index for Distribution-Aware Dataset Search	2024	VLDB	5.158939e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,632	Data-Independent Space Partitionings for Summaries	2021	PODS	5.093636e-05
11,932	Vocalizing Large Time Series Efficiently	2018	VLDB	5.093636e-05
12,024	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	5.093636e-05
12,114	DocRicher: An Automatic Annotation System for Text Documents Using Social Media	2015	SIGMOD	5.093636e-05
12,258	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	5.093636e-05
12,677	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	5.093636e-05
12,712	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	5.093636e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
786	Universality of Serial Histograms	1993	VLDB	0.00014053885

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
2	786	Universality of Serial Histograms	1993	VLDB
3	168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
4	118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD
5	35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
6	8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
7	3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS
8	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
9	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
10	1,668	Global Optimization of Histograms	2001	SIGMOD