Efficiently count distinct in large range

Question

I have a pubsub channel where an event is fired every time a user logs in, and I want to be able to query the unique users in a date range.

Solutions I thought:

• Put the data in bigquery, and then use APPROX_COUNT_DISTINCT, but it's too expensive
• Same as above, plus a cache. Past data doesn't change, so it's a good approach, but still very expensive because I would need to import the pubsub channel in bigquery
• Precompute daily uniques, and then do something very rough like max(range)^log(days)

I was also thinking about storing a 64 bytes bloom filter and a counter per day, then merge the filters in range and do some estimation on the count, but I couldn't find any paper on it.

Any better idea?

If it can be helpful we're speaking about 2/3 gb of data per day, around 6 months and growing.

Answer 1

I think the Google Scholar keywords you're looking for are "sliding window" and "hyperloglog". I found "Cardinalities estimation under sliding time window by sharing HyperLogLog Counter" and "Sliding HyperLogLog: Estimating cardinality in a data stream".

For a simple version, you can store a HyperLogLog sketch for each day and then merge the sketches to get an estimate, but this scales as $m$, the number of days you query.

Finally, you could store a Merkle tree of merged HLL sketches, making counting take $\lg_2 m$ HLL merges and one HLL estimation.