twitter/algebird — pull request #295 by avibryant (2014-04-05 20:51:54+00:00)
Title: HyperLogLogSeries

This data structure can produce a HyperLogLog counter for any window into the past, using a constant factor more space than HyperLogLog.

For each hash bucket, rather than keeping a single max RhoW value, it keeps every RhoW value it has seen, and the max timestamp where it saw that value. This allows it to reconstruct an HLL as it would be had it started at zero at any given point in the past, and seen the same updates this structure has seen.

The usage is like this:

````scala
vall hllSeriesMonoid = new HyperLogLogSeriesMonoid(bits)

val series = examples
.map{case (bytes, timestamp) => hllSeriesMonoid.create(bytes, timestamp)}
.reduce{hllSeriesMonoid.plus(_,_)}

val estimate1 = series.since(timestamp1).toHLL.estimatedSize
val estimate2 = series.since(timestamp2).toHLL.estimatedSize
````