The History of Histograms (abridged)

Summary: A deliberately compressed, personally biased history of histograms, spanning scientific origins, approximation/compression, industrial adoption, and database problems. Treats the historical narrative itself as a histogram, preserving high-interest events under a fixed space budget and evaluating semantic fidelity. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6cdc112dd76a9bd6
Venue: VLDB
Year: 2003
Pagerank: 0.00022981861
Overall Rank: 255 | 98.29%
DOI: 10.1016/B978-012722442-8/50011-2

Incoming Non-self Citations Over Time

Authors

1. Yannis Ioannidis (University of Athens)

BibTeX Citation

@article{ioannidis_vldb03,
        title = {{The History of Histograms (abridged)}},
        author = {Ioannidis, Yannis},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50011-2},
        url = {https://doi.org/10.1016/B978-012722442-8/50011-2},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 51 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,792	Filtered Statistics	2009	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 50 of 55 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076195956
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
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023050233
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
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.0002211981
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
353	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00020222998
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
450	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018032912
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001520859
701	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00014680907
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00014005637
806	Universality of Serial Histograms	1993	VLDB	0.00013792174
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013381261
919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013083677
1,004	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012594522
1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012154948
1,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00011750813
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011686985
1,184	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00011611937
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
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5690887e-05
1,960	StatiX: Making XML Count	2002	SIGMOD	9.3125715e-05
2,162	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.935022e-05
2,181	Probabilistic Optimization of Top N Queries	1999	VLDB	8.9082736e-05
2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5622073e-05
2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.967335e-05
3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.5577589e-05
3,269	Multi-Dimensional Substring Selectivity Estimation	1999	VLDB	7.4756338e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
2	1,687	Global Optimization of Histograms	2001	SIGMOD
3	12,319	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS
4	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
5	6,639	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS
6	11,939	Data-Independent Space Partitionings for Summaries	2021	PODS
7	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
8	9,142	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
9	5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
10	742	Dynamic Multidimensional Histograms	2002	SIGMOD