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.00022654182
Overall Rank
268 | 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.00020486383
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
381 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019497061
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00018277436
495 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017347522
711 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014589586
861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013374869
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,534 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010309919
1,668 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9190265e-05
2,063 Space Efficient Mining of Multigraph Streams 2005 PODS 9.0815237e-05
2,184 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.8972748e-05
2,337 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.6002736e-05
2,428 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.466877e-05
2,472 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.3988741e-05
2,777 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0101016e-05
3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6394636e-05
3,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.5902303e-05
3,219 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.50928e-05
3,284 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.4455194e-05
3,509 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 7.2279142e-05
4,000 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.8489751e-05
4,330 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6454689e-05
5,222 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 6.2110605e-05
5,341 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1596655e-05
5,476 SeeDB: Visualizing Database Queries Efficiently 2014 VLDB 6.1008903e-05
5,666 Distributed Set-Expression Cardinality Estimation 2004 VLDB 6.0281748e-05
5,800 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9735022e-05
5,815 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.9683874e-05
6,022 Maintaining Bernoulli Samples over Evolving Multisets 2007 PODS 5.8924888e-05
6,122 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8638562e-05
6,133 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 5.859093e-05
6,867 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.644892e-05
7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5212177e-05
7,534 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.4849807e-05
7,889 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 5.4159519e-05
7,935 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4071076e-05
8,363 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.3305234e-05
9,173 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2011875e-05
9,402 OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates 2024 VLDB 5.1672232e-05
10,771 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.9605343e-05
12,598 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9605343e-05
12,702 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.9605343e-05
13,007 A Simple and Efficient Estimation Method for Stream Expression Cardinalities 2007 VLDB 4.9605343e-05
13,009 Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007 VLDB 4.9605343e-05
13,062 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.9605343e-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.00076079812
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00039922419
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029805026
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026316699
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024136952
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023327437
296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021874894
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
337 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00020593498
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017359343
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016251304
667 Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure 2001 SIGMOD 0.00014941252
1,186 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011581468
2,661 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1414177e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,815 Error-bounded Sampling for Analytics on Big Sparse Data 2014 VLDB
2 10,771 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB
3 13,062 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS
4 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
5 7,387 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,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
8 296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS
9 12,246 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS
10 78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB