CODEWITHSUNDEEP
algorithmredisbloom-filter
Aryan
Aryan

Reputation: 2745

Count unique users if user visit n times

I want to implement FreqCapping in an ad network. I want to serve a campaign to unique users only n time in day. If n=1, I could implement this with BloomFilter in redis, but usually n is greater than 1. Is there any data structure (even probabilistic data structure) that aims this issue? And is that implemented in redis?

Upvotes: 1

Views: 426

Answers (2)

btilly
btilly

Reputation: 46455

If n is small, just use a bloom filter on '1x' + user, '2x' + user, ..., n + 'x' + 'user'. As a detail, check them in random order. This means that when the user has been seen only a small portion of the time, you will have fewer lookups.

If n is large, consider only doing a fixed number of random lookups. That trades performance when you're close to your limit with sometimes choosing not to fill when you're close to your limit. For example with a maximum of 4 lookups, at 50% of your way to the limit you make the right choice over 90% of the time, and at 80% of the way to the limit you still make the right choice around 60% of the time. And if n=20, you're saving a lot of time when you've hit the limit.

I am sure that there is some kind of special bloom filter that achieves similar limits where you check/set a random subset of the hash functions every time (checking more than you would set). But you won't find that special structure already pre-built in Redis.

The probabilistic version that I am suggesting is this:

def is_available(user, k=4, n=20):
    tried = []
    for 1..k:
        i = rand(n)
        while i in tried:
            i = rand(n)
        id = user + ":" + str(i)
        if bloomfilter.lookup(id):
            tried.append(i)
        else:
            bloomfilter.add(id)
            return True
    return False

The point of randomization is to reduce how many lookups you need. If you go in the same order each time, then on the 10th visit you'll have 9 lookups before you find that they are not over quota. But if n is 20 and you are proceeding in random order, half the time the first lookup will be enough. This reduces round trips, which improves performance, which matters a lot in adtech.

Upvotes: 1

Itamar Haber
Itamar Haber

Reputation: 50052

It sounds like you're describing the Count-min sketch, and while Redis core doesn't have it, RedisBloom does :)

Upvotes: 3

Related Questions