Подсчитайте уникальных пользователей, если пользователь посещает n раз

Я хочу реализовать FreqCapping в рекламной сети. Я хочу обслуживать кампанию для уникальных пользователей только n раз в день. Если n=1, я мог бы реализовать это с помощью BloomFilter в Redis, но обычно n больше 1. Существует ли какая-либо структура данных (даже вероятностная структура данных), которая решает эту проблему? И реализовано ли это в Redis?


redis algorithm bloom-filter
person Aryan    schedule 25.05.2019    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Похоже, вы описываете эскиз Count-min, и в то время как в ядре Redis его нет, RedisBloom есть :)

person Itamar Haber    schedule 27.05.2019

arrow_upward
1
arrow_downward

Если n мало, просто используйте фильтр Блума на '1x' + user, '2x' + user, ..., n + 'x' + 'user'. Как деталь, проверьте их в случайном порядке. Это означает, что когда пользователь был замечен лишь небольшую часть времени, у вас будет меньше поисковых запросов.

Если n велико, рассмотрите возможность выполнения только фиксированного количества случайных поисков. Это меняет производительность, когда вы близки к своему лимиту, иногда отказываясь от заполнения, когда вы близки к своему лимиту. Например, с максимум 4 поисками, на 50% пути к пределу вы делаете правильный выбор более чем в 90% случаев, а на 80% пути к пределу вы по-прежнему делаете правильный выбор примерно в 60% случаев. время. А если n=20, вы сэкономите много времени, когда исчерпаете лимит.

Я уверен, что существует какой-то специальный фильтр Блума, который достигает аналогичных ограничений, когда вы каждый раз проверяете/устанавливаете случайное подмножество хеш-функций (проверяя больше, чем вы установили). Но вы не найдете эту специальную структуру, уже встроенную в Redis.

Вероятностная версия, которую я предлагаю, такова:

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

Смысл рандомизации в том, чтобы уменьшить количество поисковых запросов, которые вам нужны. Если вы каждый раз выполняете один и тот же порядок, то при 10-м посещении у вас будет 9 поисков, прежде чем вы обнаружите, что они не превышают квоту. Но если n равно 20 и вы действуете в случайном порядке, в половине случаев первого поиска будет достаточно. Это уменьшает количество циклов обмена данными, что повышает производительность, что очень важно в рекламных технологиях.

person btilly    schedule 25.05.2019
comment
Отличная идея с использованием нескольких фильтров Блума, но я взял на себя смелость предложить другую экзотическую структуру данных. - person Itamar Haber; 27.05.2019
comment
Это интересная идея (конечно, скетч count-min является альтернативой, но, возможно, ему нужно больше памяти). Чего я не понимаю, так это случайного порядка. Как это поможет? Не могли бы вы описать алгоритм более подробно (с псевдокодом для поиска и добавления)? - person Thomas Mueller; 28.05.2019
comment
@ThomasMueller Я добавил код и краткое объяснение. - person btilly; 28.05.2019