0
$\begingroup$

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.

New contributor
Mascarpone is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • 1
    $\begingroup$ I suggest you edit the question to include more information about your context. What are the total number of users who could possibly appear in these events? How many logins per day? What would a typical result for such a query be? (100 users? 1000 users? 1 million users?) Do you want/need an exact count or an approximate count? $\endgroup$
    – D.W.
    Aug 2 at 23:46

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks man, I was looking for counting bloom filters and I got a bunch of unrelated papers. Sliding window was the right keyword, you saved me a bunch of work $\endgroup$
    – Mascarpone
    Aug 3 at 11:05

Your Answer

Mascarpone is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.