Является ли это эффективным / подходящим использованием фильтра Блума?

У меня есть API, из которого приходят данные, но многие из них избыточны (можно определить по идентификатору). У меня есть фильтр Блума, созданный с несколькими миллионами записей для начала.

Я использую эту библиотеку для обработки реализации. Из моего чтения в Интернете:

Фильтр Блума — это компактная структура данных для вероятностного представления набора переменных, позволяющая убедиться, что элементы в наборе обязательно присутствуют или определенно отсутствуют в наборе. Источник

Если у меня есть такой псевдокод

newData #some dataset
for row in newData:
    #filter.add() returns True if in set, we want only not in set
    if not filter.add(row.id):
        #do some stuff with fresh data

Эта функция будет вызываться каждый раз, когда поступает набор данных, что составляет около 200 новых записей в секунду.

Является ли это эффективным способом использования фильтра Блума?


python bloom-filter computer-science
person George L    schedule 16.01.2016    source источник
comment
Джордж - каковы ваши критерии эффективности? Вы действительно имеете в виду уместность/правильность?   -  person Edmon    schedule 16.01.2016
comment
Я подозреваю, что ошибки, создаваемые фильтром Блума, будут неправильными для вашего приложения. Он может неправильно сказать, что данный идентификатор был замечен ранее, когда его не было. Я думаю, вы бы предпочли другой тип ошибки (ложно сказать, что значение не было замечено, когда оно было), так как это не заставит вас пропустить значение, которое вы не должны (только обработать несколько дополнительных значений, которые вы могли бы пропустили).   -  person Blckknght    schedule 16.01.2016

Ответы (1)


arrow_upward
0
arrow_downward

Фильтр Блума может для любого заданного элемента дать два ответа. Он может сказать: «Я совершенно уверен, что никогда раньше не видел этот элемент» или «Я думаю, что видел этот элемент раньше». В последнем случае может случиться так, что фильтр Блума неверен (то есть он говорит «Я думаю, что видел это раньше», хотя на самом деле это не так).

То есть вопрос, на который он отвечает, не «я никогда этого раньше не видел», а «я думаю, что видел это раньше» (элемент, который он видел, не может получить ответ «никогда не видел», но может быть случаи, когда он отвечает «вероятно, видел» для элементов, которые он не видел).

Это означает, что единственный ответ, на который вы можете положиться на 100%, это «никогда не видел», но вас, вероятно, интересует другой случай, поэтому вы никогда не пропустите обработку нового элемента, и это не гарантия того, что фильтр Блума дает тебе.

Если обработка стоит дорого, вы можете использовать фильтр Блума в качестве шлюза для более дорогого поиска в кэше.

Псевдокод:

if not bloom.seen(element):
  # we have never seen this
  bloom.add(element)
  value = process(element)
  more_expensive_cache.set(element, value)
  return value
else:
  value, seen = more_expensive_cache.lookup(element)
  if not seen:
    value = process(element)
    more_expensive_cache.set(element, value)
  return value
person Vatine    schedule 19.01.2016