Natural SciencesData ScienceMathematicsData AnalyticsStatisticsUncertainty QuantificationEstimation TheoryInferential StatisticsStatistical InferenceCount Data AnalysisCount-based EstimationCounting Error AnalysisError Distribution AnalysisQuery Turnaround Time
The Count-Min sketch is an important and well-studied data summarization method. It can estimate the count of any item in a stream using a small, fixed size data sketch. However, the accuracy of the Count-Min sketch depends on characteristics of the underlying data. This has led to a number of count estimation procedures which work well in one scenario but perform poorly in others. A practitioner is faced with two basic, unanswered questions. Given an estimate, what is its error? Which estimation procedure should be chosen when the data is unknown? We provide answers to these questions. We derive new count estimators, including a provably optimal estimator, which best or match previous estimators in all scenarios. We also provide practical, tight error bounds at query time for all estimators and methods to tune sketch parameters using these bounds. The key observation is that the full distribution of errors in each counter can be empirically estimated from the sketch itself. By first estimating this distribution, count estimation becomes a statistical estimation and inference problem with a known error distribution. This provides both a principled way to derive new and optimal estimators as well as a way to study the error and properties of existing estimators.
22
Bootstrap Methods: Another Look at the Jackknife
B. Efron · The Annals of Statistics · 1979 · 17.4K citations · Full text
An Introduction to the Bootstrap.
S. T. Buckland, B. Efron, Ryan J. Tibshirani · Biometrics · 1994 · 3.2K citations
Quantitative Analysis of Culture Using Millions of Digitized Books
Jean-Baptiste Michel, Yuan Shen, Aviva Presser Aiden et al. · Science · 2010 · 3.1K citations · Full text
Humanities, Cultures, Linguistics +10