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: 8322
Venue: VLDB
Year: 1993
Pagerank: 0.00014053885
Overall Rank: 786 | 94.61%
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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
1,668	Global Optimization of Histograms	2001	SIGMOD	0.00010057026
1,729	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.908788e-05
2,991	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.8880723e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
3,123	Monarch: Google’s Planet-Scale In-Memory Time Series Database	2020	VLDB	7.7354933e-05
3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.6057671e-05
3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.2946291e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	7.04191e-05
4,819	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.4940349e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,443	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	5.6166792e-05
8,155	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	5.4766319e-05
8,494	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.4142129e-05
8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.3355988e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
12,841	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	5.093636e-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.0024089429
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
417	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018819871
1,614	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00010215186

Semantically Similar Papers

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