DBScholar

Back to papers

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

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 50 of 59 citing papers.

Rank Citing Paper Year Venue Pagerank
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030600691
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024218831
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021311793
343 Model-Driven Data Acquisition in Sensor Networks 2004 VLDB 0.00020519525
370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD 0.00019846702
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
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
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016296665
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016296423
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015785583
710 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00014608975
858 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.000134266
870 Spectral Bloom Filters 2003 SIGMOD 0.0001334417
948 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00012914559
1,022 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00012438826
1,183 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011616705
1,607 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.0001008742
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8655879e-05
1,703 Online Dynamic Reordering for Interactive Data Processing 1999 VLDB 9.8315219e-05
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
1,755 Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data 2000 VLDB 9.7206727e-05
2,171 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.9239861e-05
2,256 Dwarf: Shrinking the PetaCube 2002 SIGMOD 8.7438759e-05
2,343 Answering Aggregation Queries in a Secure System Model 2007 VLDB 8.604484e-05
2,415 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.4985276e-05
2,624 Optimal Sampling from Sliding Windows 2009 PODS 8.2095532e-05
2,717 Partial Results in Database Systems 2014 SIGMOD 8.0980367e-05
2,875 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 7.9193665e-05
2,930 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.8415815e-05
3,424 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 7.3117029e-05
3,540 Tighter Estimation using Bottom k Sketches 2008 VLDB 7.2161972e-05
4,313 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.6699869e-05
4,324 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6656407e-05
4,640 Exact and Approximate Aggregation in Constraint Query Languages 1999 PODS 6.4903073e-05
4,870 Estimating arbitrary subset sums with few probes 2005 PODS 6.3737999e-05
5,622 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0614658e-05
5,778 Data Streams with Bounded Deletions 2018 PODS 5.9977531e-05
5,851 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 5.9718136e-05
6,011 Maintaining Bernoulli Samples over Evolving Multisets 2007 PODS 5.9143905e-05
6,252 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.8354449e-05
6,781 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.6836871e-05
6,846 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.6662335e-05
7,513 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 5.5049463e-05
7,955 Distributed Outlier Detection using Compressive Sensing 2015 SIGMOD 5.4185826e-05
7,973 Sketching Unaggregated Data Streams for Subpopulation-Size Queries 2007 PODS 5.4149919e-05
8,283 Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters 2019 VLDB 5.3627138e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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