Towards estimation error guarantees for distinct values

Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek Narasayya

Type: Article

Publication Date: 2000-01-01

Citations: 236

DOI: https://doi.org/10.1145/335168.335230

Similar Works

Action	Title	Year	Authors
+	Extensive Large-Scale Study of Error in Samping-Based Distinct Value Estimators for Databases	2016	Vinay Deolalikar H Laffitte
+	Extensive Large-Scale Study of Error in Samping-Based Distinct Value Estimators for Databases	2016	Vinay Deolalikar H Laffitte
+ PDF Chat	Learning to be a statistician	2021	Renzhi Wu Bolin Ding Xu Chu Zhewei Wei Xiening Dai Tao Guan Jingren Zhou
+	Detecting random sets by samplings from their values	2021	Zvi Artstein Alon Shapira
+	Detecting random sets by samplings from their values	2021	Zvi Artstein Alon Shapira
+	Worst-Case Analysis for Randomly Collected Data	2019	Justin Y. Chen Gregory Valiant Paul Valiant
+	Distinct Elements in Streams: An Algorithm for the (Text) Book	2023	Sourav Chakraborty N. V. Vinodchandran Kuldeep S. Meel
+	Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions	2018	Daniel Ting
+ PDF Chat	Distinct Counting With a Self-Learning Bitmap	2011	Aiyou Chen Jin Cao L. A. Shepp Tuan Dung Nguyen
+ PDF Chat	Distinct Counting with a Self-Learning Bitmap	2009	Aiyou Chen Jin Cao
+	Estimating Frequency Statistics through Distinct Count Measurements.	2016	Edith Cohen
+ PDF Chat	Sampling-based Estimation of the Number of Distinct Values in Distributed Environment	2022	Jiajun Li Zhewei Wei Bolin Ding Xiening Dai Lu Lu Jingren Zhou
+	Analysis of Knuth's Sampling Algorithm D and D'	2023	Mridul Nandi Soumit Paul
+	Simple and Efficient Cardinality Estimation in Data Streams.	2020	Seth Pettie Dingyu Wang Longhui Yin
+ PDF Chat	Frequency Estimation with One-Sided Error	2022	Piotr Indyk Shyam Narayanan David P. Woodruff
+	How bad is worst-case data if you know where it comes from?	2019	Justin Y. Chen Gregory Valiant Paul Valiant
+	Cardinality estimation using Gumbel distribution	2020	Aleksander Łukasiewicz Przemysław Uznański
+	Improved estimates for the number of non-negative integer matrices with given row and column sums	2024	Maximilian Jerdee Alec Kirkley M. E. J. Newman
+	Consistent and accurate frequency oracles under local differential privacy	2019	Tianhao Wang Milan Lopuhaä-Zwakenberg Zitao Li Boris Škorić Ninghui Li
+ PDF Chat	Deep unsupervised cardinality estimation	2019	Zongheng Yang Eric Liang Amog Kamsetty Chenggang Wu Yan Duan Xi Chen Pieter Abbeel Joseph M. Hellerstein Sanjay Krishnan Ion Stoica

Works That Cite This (46)

Action	Title	Year	Authors
+ PDF Chat	Estimating Sum by Weighted Sampling	2007	Rajeev Motwani Rina Panigrahy‎ Ying Xu
+ PDF Chat	Better Size Estimation for Sparse Matrix Products	2010	Rasmus Resen Amossen Andrea Campagna Rasmus Pagh
+ PDF Chat	Democratizing Data Science through Interactive Curation of ML Pipelines	2019	Zeyuan Shang Emanuel Zgraggen Benedetto Buratti Ferdinand Kossmann Philipp Eichmann Yeounoh Chung Carsten Binnig Eli Upfal Tim Kraska
+	Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem	2007	Sofya Raskhodnikova Dana Ron Amir Shpilka Adam Smith
+ PDF Chat	Chebyshev polynomials, moment matching, and optimal estimation of the unseen	2019	Yihong Wu Pengkun Yang
+	Extrapolating the profile of a finite population	2020	Soham Jana Yury Polyanskiy Yihong Wu
+ PDF Chat	Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting	2007	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	Estimating the unseen	2011	Gregory Valiant Paul Valiant
+	A CLT and tight lower bounds for estimating entropy.	2010	Gregory Valiant Paul Valiant
+	Testing closeness with unequal sized samples	2015	Bhaswar B. Bhattacharya Gregory Valiant

Works Cited by This (9)

Action	Title	Year	Authors
+	Nonparametric estimation of the number of classes in a population	1984	Anne Chao
+	Estimating the Number of Species: A Review	1993	John Bunge Matthew C. Fitzpatrick
+	Robust Estimation of Population Size When Capture Probabilities Vary Among Animals	1979	Kenneth P. Burnham W. Scott Overton
+	Estimation of the size of a closed population when capture probabilities vary among animals	1978	Kenneth P. Burnham W. Scott Overton
+	Estimating the Number of Classes in a Finite Population	1998	Peter J. Haas Lynne Stokes
+ PDF Chat	On the Estimation of the Number of Classes in a Population	1949	Leo A. Goodman
+	Estimating Species Richness Using the Jackknife Procedure	1983	James F. Heltshe Nancy E. Forrester
+	Estimating the Number of Classes via Sample Coverage	1992	Anne Chao Shen‐Ming Lee
+	Estimating the Number of Classes via Sample Coverage	1992	Anne Chao Shen‐Ming Lee