 In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the Random Oracle model. We define a new measure of efficiency for cardinality estimators called the Fisher-Shannon ( \mathsf{Fish ) number H/I. It captures the tension between the limiting Shannon entropy (H) of the sketch and its normalized Fisher information (I), which characterizes (asymptotically) the variance of a statistically efficient estimator. We prove that many variants of the \mathsf{PCSA Flajolet and Martin have \mathsf{Fish H_0/I_0 , where H_0,I_0 are two precisely-defined constants, and that all base-q generalizations of (\textsf{Hyper )\textsf{LogLog are strictly worse than H_0/I_0, but  tend to H_0/I_0 in the limit as q %DIFDELCMD < \to%%% \infty. All other known sketches have even worse \mathsf{Fish-numbers. We introduce a new sketch called \mathsf{Fishmonger} }  that is based on a smoothed, compressed version of \mathsf{PCSA with a different estimation function. \mathsf{Fishmonger has \mathsf{Fish} number H_0/I_0 \approx 1.98. It stores }  ]  O(\log^2\log U) + (  H_0/I_0)b \approx 1.98b bits , and estimates cardinalities of multisets of U%DIFDELCMD < ] %%% with a standard error of ( 1 +o(1)) /\sqrt{b}. \mathsf{Fishmonger's space-error tradeoff improves on state-of-the-art sketches like }\textsf{HyperLogLog , or even compressed representations of it. \mathsf{Fishmonger can be used in a distributed environment (where substreams are sketched separately and composed later). We conjecture that the \mathsf{Fish}-number }  H_0/I_0 is a universal lower bound for any such composable sketch .
Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983. In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the random oracle model. We define a new measure of efficiency for cardinality estimators called the Fisher-Shannon ( Fish ) number H/I. It captures the tension between the limiting Shannon entropy (H) of the sketch and its normalized Fisher information (I), which characterizes the variance of a statistically efficient , asymptotically unbiased estimator. Our results are as follows. We prove that all base-q variants of Flajolet and Martin 's PCSA sketch have Fish-number H_0/I_0 \approx 1.98016 and that every base-q \textsf{ \textsf{ variant of (Hyper)LogLog has Fish-number worse than H_0/I_0, but that they tend to H_0/I_0 in the limit as q %DIFDELCMD < \to%%% -numbers. We introduce a new sketch called \mathsf{Fishmonger} } \rightarrow \infty. Here H_0,I_0 are precisely defined constants. We describe a sketch called Fishmonger that is based on a smoothed, entropy-compressed variant of PCSA with a different has \mathsf{Fish} number H_0/I_0 \approx 1.98. It stores } estimator function. It is proved that with high probability, Fishmonger processes a multiset of U] such that at all times, its space is O(\log^2\log U) + ( 1+o(1))( H_0/I_0)b \approx 1.98b bits %DIFDELCMD < ] %%% and its standard error is 1 /\sqrt{b}. 's space-error tradeoff improves on state-of-the-art sketches like }\textsf{ can be used in a distributed environment (where substreams are sketched separately and composed later). We conjecture that the \mathsf{Fish}-number } We give circumstantial evidence that H_0/I_0 is the optimum Fish-number of mergeable sketches for Cardinality Estimation. We define a class of linearizable sketches and prove that no member of this class can beat H_0/I_0 . The popular mergeable sketches are, in fact, also linearizable .
A
Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983.
R
Random Oracle
random oracle
R
\mathsf{Fish
Fish
D
(asymptotically)
R
estimator.
, asymptotically unbiased estimator. Our results are as follows.
R
many variants of the \mathsf{PCSA
all base-q variants of
R
have \mathsf{Fish
's PCSA sketch have Fish-number
R
, where H_0,I_0 are two precisely-defined constants, and that all
\approx 1.98016 and that every
D
generalizations of (
D
Hyper
D
)
D
LogLog
R
are strictly
variant of (Hyper)LogLog has Fish-number
A
that they
D
\infty. All other known sketches have even worse \mathsf{Fish
A
\rightarrow \infty. Here H_0,I_0 are precisely defined constants. We describe a sketch called Fishmonger
R
compressed version of \mathsf{PCSA
entropy-compressed variant of PCSA
D
estimation function. \mathsf{Fishmonger
A
estimator function. It is proved that with high probability, Fishmonger processes a multiset of
A
U
A
such that at all times, its space is
A
1+o(1))(
D
, and estimates cardinalities of multisets of
D
U
R
with a standard error of (
and its standard error is
D
+o(1))
D
\mathsf{Fishmonger
D
HyperLogLog
D
, or even compressed representations of it. \mathsf{Fishmonger
A
We give circumstantial evidence that H_0/I_0 is the optimum Fish-number of mergeable sketches for Cardinality Estimation. We define a class of linearizable sketches and prove that no member of this class can beat
R
is a universal lower bound for any such composable sketch
. The popular mergeable sketches are, in fact, also linearizable