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: 3087
Venue: SIGMOD
Year: 1998
Pagerank: 0.00029226907
Overall Rank: 149 | 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,689	Adaptive Index Structures	2002	VLDB	5.3843737e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-05
8,961	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	5.3438458e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05
10,847	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	5.093636e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05
12,096	Capturing the Laws of (Data) Nature	2015	CIDR	5.093636e-05
12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	5.093636e-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.00077458002
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
467	Random Sampling from B+ trees	1989	VLDB	0.00018002218
704	Dynamic Itemset Counting and Implication Rules for Market Basket Data	1997	SIGMOD	0.00014837704
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
952	Recovering Information from Summary Data	1997	VLDB	0.00013010681
4,458	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.6905953e-05

Semantically Similar Papers

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