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

Summary: Distinct sampling: single-pass, tailored sampling over distinct values yields accurate estimates from small samples, breaking prior negative results. Incrementally maintained under updates, it supports range queries and yields 0-10% error with 2-4x speedups in high-volume reporting. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8779
Venue: VLDB
Year: 2001
Pagerank: 0.00027981848
Overall Rank: 316 | 97.81%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Phillip B. Gibbons

Incoming Citations (Sorted by Pagerank)

Showing 46 of 46 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
449	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00022914472
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022205608
481	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.000221538
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
737	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00017377393
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.0001091276
2,005	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	9.8168893e-05
2,120	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	9.5017579e-05
2,269	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1507118e-05
2,841	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.0396876e-05
2,934	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8628636e-05
3,108	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5547127e-05
3,123	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5270618e-05
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05
3,553	Approximate Selection with Guarantees using Proxies	2020	VLDB	6.9763548e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
3,868	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	6.6786821e-05
4,022	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	6.5185189e-05
4,347	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2588401e-05
4,716	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9692227e-05
5,119	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6774637e-05
5,263	SeeDB: Visualizing Database Queries Efficiently	2014	VLDB	5.5959099e-05
5,423	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.5143276e-05
5,684	Distributed Set-Expression Cardinality Estimation	2004	VLDB	5.3731479e-05
5,794	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.323907e-05
5,907	Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA	2014	SIGMOD	5.2741214e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
6,837	Capturing Data Uncertainty in High-Volume Stream Processing	2009	CIDR	4.9063121e-05
7,340	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7526052e-05
7,414	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	4.7312542e-05
7,697	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	4.6701245e-05
7,839	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	4.6338068e-05
8,345	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5361313e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
9,039	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	4.3997447e-05
10,227	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.1905499e-05
12,068	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.1905499e-05
12,174	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1905499e-05
12,484	A Simple and Efficient Estimation Method for Stream Expression Cardinalities	2007	VLDB	4.1905499e-05
12,487	Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing	2007	VLDB	4.1905499e-05
12,540	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1905499e-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
14	Online Aggregation	1997	SIGMOD	0.0010813443
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
133	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00043220055
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
291	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00028778973
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
649	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00018652362
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
1,331	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00012553948
2,813	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0816314e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,583	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.4973431e-05
5,258	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB	5.5973455e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
12,540	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1905499e-05
10,227	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	4.1905499e-05
7,340	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7526052e-05
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997