DBScholar

Back to papers

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
h111c762a5fbf3617
Venue
VLDB
Year
1998
Pagerank
0.00022413521
Overall Rank
275 | 98.16%
DOI
-

Incoming Non-self Citations Over Time

Authors

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 50 of 66 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052121228
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019829769
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019444411
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019104625
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016245271
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011777105
1,461 Substring Selectivity Estimation 1999 PODS 0.00010583833
1,528 A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy 2014 VLDB 0.00010349919
1,580 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010180835
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8655879e-05
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
1,892 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.4166991e-05
2,093 Selectivity Estimation For Boolean Queries 2000 PODS 9.0578876e-05
2,298 Principled Evaluation of Differentially Private Algorithms using DPBench 2016 SIGMOD 8.6731734e-05
2,359 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5813849e-05
2,432 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.4766851e-05
2,688 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.1265396e-05
2,807 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.982663e-05
3,163 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5789852e-05
3,281 Kernel-Based Skyline Cardinality Estimation 2009 SIGMOD 7.4583561e-05
3,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4424817e-05
3,361 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3760492e-05
3,379 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.3568458e-05
3,562 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.2046519e-05
3,644 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1399991e-05
4,117 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7958711e-05
4,462 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5880099e-05
4,932 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3483816e-05
4,933 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 6.3474817e-05
5,004 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.3186165e-05
5,021 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3106761e-05
5,159 NashDB: An End-to-End Economic Method for Elastic Database Fragmentation, Replication, and Provisioning 2018 SIGMOD 6.2482448e-05
5,534 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0923159e-05
5,580 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.0769576e-05
5,652 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0515502e-05
6,032 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.9097667e-05
6,221 Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021 SIGMOD 5.8463347e-05
6,223 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.8457826e-05
6,557 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 5.7498216e-05
6,639 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 5.7259633e-05
6,745 Categorical Skylines for Streaming Data 2008 SIGMOD 5.6908052e-05
6,781 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.6836871e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
7,493 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5103311e-05
7,501 Pythia: Data Dependent Differentially Private Algorithm Selection 2017 SIGMOD 5.5077101e-05
7,512 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.504973e-05
Previous Page 1 / 2 Next

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
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047863192
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026784195
283 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022214789
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
806 Universality of Serial Histograms 1993 VLDB 0.00013792174
Previous Page 1 / 1 Next

Semantically Similar Papers

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