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.00022713652
Overall Rank: 267 | 98.21%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Phillip B. Gibbons (AT&T)

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.00020510274
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0001971778
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019446558
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001831946
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017379171
707	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014633741
863	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013390792
1,067	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012187242
1,537	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010324934
1,662	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	9.9502569e-05
2,056	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1092395e-05
2,173	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9197633e-05
2,326	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.628257e-05
2,416	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	8.4946354e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4213787e-05
2,773	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0318294e-05
3,096	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6497893e-05
3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6107287e-05
3,212	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5324957e-05
3,273	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.469873e-05
3,500	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.2506844e-05
3,988	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	6.8694751e-05
4,313	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.667311e-05
5,197	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2316663e-05
5,325	Sampling Algorithms in a Stream Operator	2005	SIGMOD	6.1799938e-05
5,459	SeeDB: Visualizing Database Queries Efficiently	2014	VLDB	6.1211089e-05
5,655	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0478521e-05
5,787	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9933192e-05
5,816	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	5.9817821e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.911598e-05
6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.8831615e-05
6,119	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.8785289e-05
6,850	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	5.6635511e-05
7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5392867e-05
7,515	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	5.5029699e-05
7,875	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	5.4336639e-05
7,921	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4250462e-05
8,351	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.3480813e-05
9,151	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.2181099e-05
9,376	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.1843659e-05
10,710	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.9769913e-05
12,555	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.9769913e-05
12,659	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.9769913e-05
12,965	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB	4.9769913e-05
12,967	Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing	2007	VLDB	4.9769913e-05
13,020	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.9769913e-05

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.00076265429
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040025054
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036817139
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028621958
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026384065
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024210103
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021908194
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021376597
335	The Aqua Approximate Query Answering System	1999	SIGMOD	0.000206533
491	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.0001740646
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016938992
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016297598
666	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014989211
1,182	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011615497
2,654	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.1670397e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,795	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
2	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
3	13,020	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
4	10,710	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB
5	7,368	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,132	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,203	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