The Count-Min sketch is an important and well-studied data summarization
method. It allows one to estimate the count of any item in a stream using a
small, fixed size data sketch. However, the accuracy of the 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. Which
variant should be chosen when the data is unknown? Given an estimate, is its
error sufficiently small to be trustworthy?
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 both new and existing estimators. These error estimates also yield
procedures to choose the sketch tuning parameters optimally, as they can
extrapolate the error to different choices of sketch width and depth.
The key observation is that the 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.

提供了一些回答，包括新的计数估计器、实用的严格误差界限和最佳的草图调优参数。