LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $z$ in $O(n)$ time (and basically $O(1)$ space), and $2^z$ is your estimate for the cardinality. In practice, instead of just counting the number of leading 0's, you'll have a bunch of different counts (e.g. one can't for number of zeros at the end, one count using a hash with different salt, etc.), and then take their harmonic mean to get $\bar{z}$, which leads to a much smoother, more stable, and accurate estimate.

Anyways, that's all well and good. But what if, instead of estimating the cardinality for the set of $n$ objects, you have an endless stream of objects coming in, and you want a running estimate of the cardinality of the set of the last $k$ objects? Basically, you're not just accumulating new objects, but you also have to delete old objects from the count.

Is there a LogLog/HyperLogLog way of solving this problem?

My guess at a solution would be: keep two counts. One count is up until the current total number of objects $n$, while the other count would be up to $n-k$. Then, you'd subtract the two counts to get your count of the last $k$ objects. But I'm not sure if this is correct, or if this estimator is robust/accurate/stable, etc..



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.