Database Paper Browser

Back to papers

Universality of Serial Histograms

Summary: Universality of serial histograms for frequency distribution in relational data. Optimal to minimize extreme-case query-size errors in tree-join queries; zero expected error for all histograms, arguing to optimize for extreme cases, not mean error. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8131
Venue
VLDB
Year
1993
Pagerank
0.00016432772
Overall Rank
808 | 94.39%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
252 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030632263
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022734812
1,120 Global Optimization of Histograms 2001 SIGMOD 0.00013856211
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
1,379 Substring Selectivity Estimation 1999 PODS 0.00012286879
1,695 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010882793
2,748 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1785955e-05
3,286 Monarch: Google’s Planet-Scale In-Memory Time Series Database 2020 VLDB 7.2740159e-05
3,310 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2408955e-05
3,719 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.8204683e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6584217e-05
3,990 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5581983e-05
4,017 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.524501e-05
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8163484e-05
7,581 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7057641e-05
7,827 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6411831e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4275272e-05
9,061 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.4039656e-05
9,187 POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance 2024 VLDB 4.3780059e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
12,648 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.0040449103
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
228 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00032269684
1,398 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00012197586
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,090 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5888589e-05
361 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025775749
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
4,017 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.524501e-05
9,591 Constructing Join Histograms from Histograms with q-error Guarantees 2016 SIGMOD 4.3204659e-05
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8163484e-05
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
1,120 Global Optimization of Histograms 2001 SIGMOD 0.00013856211
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479