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
8969
Venue
VLDB
Year
2001
Pagerank
0.00023174541
Overall Rank
255 | 98.26%
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
337 Model-Driven Data Acquisition in Sensor Networks 2004 VLDB 0.00020783399
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
388 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019410042
432 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00018572055
482 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017772185
689 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00014940023
842 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013671191
1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012440928
1,516 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010520885
1,634 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 0.00010163938
2,013 Space Efficient Mining of Multigraph Streams 2005 PODS 9.3068345e-05
2,128 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1271562e-05
2,302 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.7808696e-05
2,367 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.6855754e-05
2,406 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.6187297e-05
2,898 Approximate Selection with Guarantees using Proxies 2020 VLDB 7.978725e-05
3,044 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.820774e-05
3,150 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.7055991e-05
3,197 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.6439415e-05
3,215 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6324234e-05
3,449 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 7.4074656e-05
3,945 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 7.0055154e-05
4,229 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.8181027e-05
5,068 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 6.3770298e-05
5,193 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.3238562e-05
5,329 SeeDB: Visualizing Database Queries Efficiently 2014 VLDB 6.2634965e-05
5,516 Distributed Set-Expression Cardinality Estimation 2004 VLDB 6.1895841e-05
5,650 Extended Wavelets for Multiple Measures 2003 SIGMOD 6.1337629e-05
5,693 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 6.1189424e-05
5,891 Maintaining Bernoulli Samples over Evolving Multisets 2007 PODS 6.0495154e-05
5,995 Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments 2009 VLDB 6.0155431e-05
6,009 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 6.0113733e-05
6,712 Capturing Data Uncertainty in High-Volume Stream Processing 2009 CIDR 5.7962014e-05
7,256 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.6625146e-05
7,377 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.6297042e-05
7,713 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 5.5610113e-05
7,752 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.5521918e-05
8,183 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.4714466e-05
8,998 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.3355988e-05
9,188 OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates 2024 VLDB 5.3058708e-05
10,515 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 5.093636e-05
12,258 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 5.093636e-05
12,362 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 5.093636e-05
12,669 A Simple and Efficient Estimation Method for Stream Expression Cardinalities 2007 VLDB 5.093636e-05
12,671 Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007 VLDB 5.093636e-05
12,724 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 5.093636e-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.00077458002
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
55 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040746149
75 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00037277061
131 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00030424509
136 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00030123303
149 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00029226907
178 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026881845
213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024723025
235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023783792
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
307 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021792475
327 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00021091539
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
553 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016590619
648 Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure 2001 SIGMOD 0.00015324657
1,166 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011850439
2,608 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.347674e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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