We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf
But yes, our theorems can be reworked to estimate the confidence/error rate; that's what Knuth did: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
> But yes, our theorems can be reworked to estimate the confidence/error rate
I think that’s useful for practical implications. Also, for practical use, how does one decide the tradeoff between delta and epsilon? Perhaps it’s covered elsewhere, but I have a hard time intuiting their relationship.
So delta refers to the confidence, i.e., how often are you willing to be wrong, and epsilon is tolerance with respect to the actual count.
We have found that in general, setting delta=0.1 and espilon=0.8 works fine for most practical applications.
I suspect due to the details of the proof. This condition looks likely to me for very small set cardinality making the algorithm inappropriate for all-weather. See page 3 of the paper where Algorithm 2 is introduced. They show that in the failure condition, the likelihood of the algorithm returning a value outside of the epsilon bounds is higher.
> Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not.
m sizes the threshold, if it is too small, the error bounds guaranteed by the algorithm will be larger than expected, and vice versa if m is too large.
> And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
Papers typically do not spend words on basics and those are standard concepts.
> Perhaps there should be a method for estimating the confidence/error rate.
You can't resize the stream easily because p implicitly depends on m via the thresh cardinality condition and if you were to change m then your p updates would not correspond. As a result you may not be able to rely on the error bounds. Note though that stream doesn't mean infinite or very large: take it to mean one item at a time. The point of this algorithm is to bound space complexity to something small. Have a look at thresh and note that log2(1e50) is just 166: if you did have a very large stream of indeterminate length you could also just pick a very large m.
First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.
Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size of the stream the probability changes. But the algorithm is described as if it had a single output, which is not the case(?).
And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
Anyway, here's my take in Golang: https://github.com/betamos/distinct
I factored out the threshold parts into a helper instead, which makes a lot more sense than accidentally allocating too much memory.
Perhaps there should be a method for estimating the confidence/error rate. Nobody knows the size of a stream upfront, so it would make more sense to update these values as you go. Brain is not strong enough to implement it, but feel free to send a PR.