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: h6db2e8b36a8b9609
Venue: VLDB
Year: 1993
Pagerank: 0.00013792174
Overall Rank: 806 | 94.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of Wisconsin)

BibTeX Citation

@article{ioannidis_vldb93,
        title = {{Universality of Serial Histograms}},
        author = {Ioannidis, Yannis E.},
        journal = {PVLDB},
        series = {{VLDB} '93},
        volume = {19},
        pages = {256--267},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012154948
1,461	Substring Selectivity Estimation	1999	PODS	0.00010583833
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
2,846	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9453616e-05
2,919	Monarch: Google’s Planet-Scale In-Memory Time Series Database	2020	VLDB	7.8548399e-05
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05
3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4424817e-05
3,644	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1399991e-05
3,967	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8905715e-05
4,932	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.3483816e-05
7,410	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5342768e-05
7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.5103311e-05
7,568	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	5.49478e-05
8,325	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	5.3540828e-05
9,142	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.220581e-05
9,387	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1868213e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05
13,131	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.9793485e-05

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.0023947656
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
422	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018492336
1,641	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00010007832

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,206	Probabilistic Histograms for Probabilistic Data	2009	VLDB
2	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
3	275	Optimal Histograms with Quality Guarantees	1998	VLDB
4	3,644	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS
5	9,841	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD
6	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
7	7,568	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS
8	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
9	1,687	Global Optimization of Histograms	2001	SIGMOD
10	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD