New Sampling-Based Summary Statistics for Improving Approximate Query Answers

Summary: Introduces concise samples and counting samples—two sampling-based summary statistics for fast approximate answers. Demonstrates fast incremental maintenance across distributions, outperforming standard sample views in view-size efficiency; enables hot-list query speedups under continuous insertions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h837f62fcedf48c82
Venue: SIGMOD
Year: 1998
Pagerank: 0.00028633995
Overall Rank: 153 | 98.98%
DOI: 10.1145/276304.276334

Incoming Non-self Citations Over Time

Authors

1. Phillip B. Gibbons (AT&T)
2. Yossi Matias (Tel Aviv University)

BibTeX Citation

@inproceedings{gibbons_sigmod98,
        title = {{New Sampling-Based Summary Statistics for Improving Approximate Query Answers}},
        author = {Gibbons, Phillip B. and Matias, Yossi},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276334},
        url = {https://dl.acm.org/doi/10.1145/276304.276334},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 59 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,553	Sampling Big Ideas in Query Optimization	2023	PODS	5.3158971e-05
8,856	Adaptive Index Structures	2002	VLDB	5.2635701e-05
9,125	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	5.2239819e-05
10,316	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0377739e-05
11,089	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9793485e-05
11,253	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05
12,389	Capturing the Laws of (Data) Nature	2015	CIDR	4.9793485e-05
12,828	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
477	Random Sampling from B+ trees	1989	VLDB	0.00017632787
721	Dynamic Itemset Counting and Implication Rules for Market Basket Data	1997	SIGMOD	0.0001452081
806	Universality of Serial Histograms	1993	VLDB	0.00013792174
967	Recovering Information from Summary Data	1997	VLDB	0.00012794553
4,546	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5436884e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
2	138	Join Synopses for Approximate Query Answering	1999	SIGMOD
3	2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
4	175	Simple Random Sampling from Relational Databases	1986	VLDB
5	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
6	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
7	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
8	8,283	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB
9	7,557	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
10	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB