DBScholar

Back to papers

Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports

Summary: Introduces Distinct Sampling: a one-pass, compact sample over distinct values that supports incremental updates and accurate distinct-count estimates for arbitrary ranges or predicates. Enables 0–10% error and 2–4-order-of-magnitude faster event reports, overcoming sampling lower bounds in practice. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h1d9bf512fd2bb8a9
Venue
VLDB
Year
2001
Pagerank
0.00022722971
Overall Rank
267 | 98.21%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gibbons_vldb01,
        title = {{Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports}},
        author = {Gibbons, Phillip B.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        pages = {541--552},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 46 of 46 citing papers.

Rank Citing Paper Year Venue Pagerank
343 Model-Driven Data Acquisition in Sensor Networks 2004 VLDB 0.00020519525
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019444411
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001832766
494 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017387321
707 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014640173
862 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013396995
1,066 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012192801
1,536 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010327422
1,661 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9535453e-05
2,054 Space Efficient Mining of Multigraph Streams 2005 PODS 9.1135465e-05
2,171 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.9239861e-05
2,329 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.6292256e-05
2,415 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.4985276e-05
2,465 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.4253671e-05
2,776 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0309448e-05
3,094 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6533343e-05
3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6141006e-05
3,211 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.536045e-05
3,272 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.4734096e-05
3,500 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 7.2534237e-05
3,988 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.871854e-05
4,324 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6656407e-05
5,196 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 6.2346177e-05
5,318 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1828476e-05
5,454 SeeDB: Visualizing Database Queries Efficiently 2014 VLDB 6.1240062e-05
5,654 Distributed Set-Expression Cardinality Estimation 2004 VLDB 6.0507163e-05
5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9961546e-05
5,815 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.9844993e-05
6,011 Maintaining Bernoulli Samples over Evolving Multisets 2007 PODS 5.9143905e-05
6,106 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8859291e-05
6,118 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.8813101e-05
6,846 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.6662335e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
7,510 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.5055437e-05
7,870 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 5.4362374e-05
7,916 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4276156e-05
8,347 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.350539e-05
9,142 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.220581e-05
9,367 OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates 2024 VLDB 5.1868213e-05
10,700 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9793485e-05
12,549 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9793485e-05
12,653 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.9793485e-05
12,959 A Simple and Efficient Estimation Method for Stream Expression Cardinalities 2007 VLDB 4.9793485e-05
12,961 Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007 VLDB 4.9793485e-05
13,014 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040035279
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029866033
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028633995
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024218831
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023363722
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021384073
336 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00020657819
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016296665
664 Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure 2001 SIGMOD 0.00014995058
1,183 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011616705
2,655 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1706092e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,792 Error-bounded Sampling for Analytics on Big Sparse Data 2014 VLDB
2 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
3 13,014 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS
4 10,700 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
5 7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD
6 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD
7 3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
8 295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS
9 12,197 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS
10 77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB