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
8132
Venue
VLDB
Year
1993
Pagerank
0.00016440976
Overall Rank
801 | 94.44%
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
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
250 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030640525
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022796106
1,116 Global Optimization of Histograms 2001 SIGMOD 0.00013863484
1,240 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013090678
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
1,691 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010890775
2,752 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1723418e-05
3,288 Monarch: Google’s Planet-Scale In-Memory Time Series Database 2020 VLDB 7.2680967e-05
3,292 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2598265e-05
3,720 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.8139746e-05
3,896 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6526869e-05
3,992 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5519369e-05
4,018 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.5250686e-05
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8128138e-05
7,573 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7034681e-05
7,833 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6367487e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4232868e-05
9,059 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.3997447e-05
9,191 POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance 2024 VLDB 4.3738237e-05
10,647 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1905499e-05
12,657 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.1905499e-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.0040465394
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
226 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.0003243274
1,399 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00012197728
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,092 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5847443e-05
360 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025768448
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
4,018 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.5250686e-05
9,580 Constructing Join Histograms from Histograms with q-error Guarantees 2016 SIGMOD 4.318902e-05
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8128138e-05
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
1,116 Global Optimization of Histograms 2001 SIGMOD 0.00013863484
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497