# Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?

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..