Есть ли фильтр против Блума?

25

Bloom фильтр позволяет эффективно отслеживать ли уже встречались различные значения в процессе обработки. Когда имеется много элементов данных, тогда фильтр Блума может привести к значительной экономии памяти по хеш-таблице. Основная особенность фильтра Блума, который он разделяет с хеш-таблицей, заключается в том, что он всегда говорит «не новый», если элемент не новый, но существует ненулевая вероятность того, что элемент будет помечен как «не новый». «даже когда это новое.

Есть ли «анти-Блум фильтр», который имеет противоположное поведение?

Другими словами: существует ли эффективная структура данных, которая говорит «новый», если элемент новый, но который может также сказать «новый» для некоторых элементов, которые не являются новыми?

Сохранение всех ранее просмотренных элементов (например, в отсортированном связанном списке) удовлетворяет первому требованию, но может занимать много памяти. Я надеюсь, что это также не нужно, учитывая ослабленное второе требование.


Для тех, кто предпочитает более формальный подход, напишите если фильтр Блума считает, что является новым, противном случае, и напишите если действительно новый и противном случае.b(x)=1xb(x)=0n(x)=1xn(x)=0

Тогда ; ; ; , для некоторых .Pr[b(x)=0|n(x)=0]=1Pr[b(x)=0|n(x)=1]=αPr[b(x)=1|n(x)=0]=0Pr[b(x)=1|n(x)=1]=1α0<α<1

Я спрашиваю: существует ли эффективная структура данных, реализующая функцию с некоторыми , такими, что ; ; ; ?b0<β<1Pr[b(x)=0|n(x)=0]=βPr[b(x)=0|n(x)=1]=0P r [ b ( x ) = 1 | n ( x ) = 1 ] = 1Pr[b(x)=1|n(x)=0]=1βPr[b(x)=1|n(x)=1]=1


Изменить: Кажется, этот вопрос уже задавался ранее в StackExchange, так как /programming/635728 и /cstheory/6596 с диапазоном ответов от «не может быть» Выполнение «через» может быть выполнено, за определенную плату «до« это тривиально, путем изменения значения ». Мне пока не ясно, каков «правильный» ответ. Что это ясно, что схема кэширования LRU некоторого вида (например, один предложенный Илмари Karonen) работает довольно хорошо, легко реализовать, и привело к сокращению времени , необходимого для запуска моего кода на 50%.b

Андраш Саламон
источник
По какой-то причине я испытываю желание сказать, что это очень похоже на проблему, которую пытаются решить кэши и алгоритмы размещения кэша. Рассмотрим кэш-память с использованием наименее часто используемой (LFU) замены. Теоретически оптимальный, но невозможный алгоритм замены будет состоять в том, чтобы исключить тот, который вы больше не увидите, как для кешей. Я полагаю, что кэширование основывается на некоторых предположениях о характере распределения, которые могут вообще не выполняться, но стоит подумать, применимо ли это.
Patrick87
Вы можете быть заинтересованы в следующем выступлении: Набор фильтров членства на основе соответствия
Kaveh
@Kaveh: спасибо за указатель, будем смотреть.
Андрас Саламон

Ответы:

12

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

Выберите параметры и ; практические значения могут быть, скажем, и . Пусть будет безопасной криптографической хеш-функцией, создающей (как минимум) битов вывода.k n = 128 k = 16 H n + knkn=128k=16Hn+k

Пусть будет массивом из битных цепочек битов. Этот массив хранит состояние фильтра, используя всего бит. (Не имеет особого значения, как инициализируется этот массив; мы можем просто заполнить его нулями или случайными битами.)2 к н н 2 кa2k nn2k

  • Чтобы добавить новое значение в фильтр, вычислите , где обозначает первые битов, а обозначает следующие битов . Пусть .яxij=H(x)k j n H ( x ) a i = jikjnH(x)ai=j

  • Чтобы проверить, было ли добавлено значение в фильтр, вычислите , как указано выше, и проверьте, является ли . Если да, верните true; в противном случае верните false.я 'xa i = j ij=H(x)ai=j

Утверждение 1. Вероятность ложного срабатывания (= новое значение, ошибочно заявленное как замеченное) составляет . Это может быть сделано сколь угодно малым при скромных затратах в пространстве хранения путем увеличения ; в частности, для эта вероятность по существу незначительна, и на практике она намного меньше вероятности ложного срабатывания из-за аппаратного сбоя. п п 1281/2n+knn128

В частности, после того, как различных значений были проверены и добавлены в фильтр, вероятность появления по меньшей мере одного ложного срабатывания равна . Например, при и число различных значений, необходимых для получения ложного срабатывания с вероятностью 50%, составляет около .( N 2 - N ) / 2 n + k + 1 n = 128 k = 16 2 ( n + k ) / 2 = 2 72N(N2N)/2n+k+1n=128k=162(n+k)/2=272

Пункт 2: Вероятность ложного отрицательного (= ранее добавленную стоимость ложно утверждал, что новый) не больше , чем , где - количество различных значений, добавленных в фильтр (или, более конкретно, количество различных значений, добавленных после того, как конкретное тестируемое значение было добавлено в фильтр в последний раз). N1(12k)N1exp(N/2k)<N/2kN


Ps. Чтобы представить «ничтожно малое» в перспективе, 128-битное шифрование обычно считается неразрушимым с известной в настоящее время технологией. Получение ложных срабатываний по этой схеме с так же вероятно, как если бы кто-то правильно угадал ваш секретный 128-битный ключ шифрования с первой попытки . (При и вероятность этого примерно в 65 000 раз ниже).n = 128 k = 16n+k=128n=128k=16

Но если это все еще заставляет вас чувствовать себя иррационально нервным, вы всегда можете переключиться на ; это удвоит ваши требования к хранилищу, но я могу с уверенностью поспорить с вами на любую сумму, которую вы хотели бы назвать, что никто никогда не увидит ложный положительный результат при - при условии, что хеш-функция не нарушена.n = 256n=256n=256

Илмари Каронен
источник
1
Мало того, что вероятность может быть сопоставима с вероятностью неисправности оборудования; это также можно сделать сравнимым с вероятностью того, что кто-то угадает ваш ключ RSA для входа по SSH с первой попытки . ИМО последний передает практичность вашего решения больше, чем первый.
R ..
+1 Очень хорошо - насколько я понимаю, это решает проблему эффективности использования пространства, позволяя (очень небольшая) вероятность ошибочно ответить «не новый», когда элемент фактически новый. Очень практичный и хороший анализ.
Patrick87
1
Утверждение 1 только заявляет, что приличная хеш-функция имеет низкую вероятность коллизий. Это верно на практике уже, если составляет не менее 50 или около того. Для моего приложения и отлично работает с простой 64-битной, не криптографической, но быстрой хэш-функцией. n = 44 k = 20n+kn=44k=20
Андрас Саламон
@ AndrásSalamon: Да, хотя безопасная криптографическая хеш-функция на самом деле обеспечивает чуть более сильную гарантию, а именно: нецелесообразно находить конфликтующие входные данные, даже если вы пытаетесь их преднамеренно искать. При достаточно большом (например, как я предлагал выше), это означает, что сохранение полных данных не требуется, даже если стоимость ложного срабатывания высока и даже если активный злоумышленник пытается его найти. Конечно, если вам не нужна такая надежная гарантия, может быть приемлем более высокий риск столкновения. n = 128nn=128
Ильмари Каронен
1
@Newtopian Причина, по которой я указал криптографическую хеш-функцию, заключается в том, что для них не существует известного способа генерирования коллизий более эффективно, чем с помощью грубой силы (т. Е. Путем тестирования множества входных данных и выбора тех, которые сталкиваются), иначе хэш будет рассматриваться сломан (как, скажем, MD5 в настоящее время есть). Таким образом, для криптографического хэша мы можем с уверенностью предположить, что частота столкновений такая же, как и для идеальной случайной хэш-функции. Использование универсальной хэш-функции или MAC с ключом (со случайным секретным ключом) сделало бы эту гарантию еще сильнее.
Илмари Каронен
8

Нет, невозможно иметь эффективную структуру данных с этими свойствами, если вы хотите гарантировать, что структура данных скажет «новая», если она действительно новая (она никогда и никогда не скажет «не новая», если это на самом деле новый; ложные негативы не допускаются). Любая такая структура данных должна сохранять все данные, чтобы когда-либо отвечать «не новым». См. Pents90 ответ на cstheory для точного обоснования.

Напротив, фильтры Блума могут гарантировать, что структура данных будет говорить «не новая», если она не новая, эффективным способом. В частности, фильтры Bloom могут быть более эффективными, чем хранение всех данных: каждый отдельный элемент может быть довольно длинным, но размер фильтра Bloom масштабируется с учетом количества элементов, а не их общей длины. Любая структура данных для вашей задачи должна масштабироваться с учетом общей длины данных, а не количества элементов данных.

jbapple
источник
Также смотрите принятый ответ, так как вопрос там тот же
Джо
-1 Тебе, вероятно, следует уточнить, что ты имеешь в виду, когда говоришь, что это невозможно. Ясно, что это возможно сделать эффективно, и это также возможно сделать с низким уровнем ошибок, поэтому достижение некоторого баланса в данной реализации должно быть возможным ... в частности, было бы полезно объяснить, что именно подразумевается под «все данные когда-либо», так как это не является строго необходимым для удовлетворения вопроса. Ложные отрицания - ответ «новый», когда ответ должен быть «не новый» - здесь разрешены, поэтому не все данные должны храниться.
Patrick87
1
Этот ответ вполне разумен и, похоже, отвечает на вопрос моего вопроса, но, возможно, не дух.
Андрас Саламон
@DW Спасибо, что нашли время, чтобы обновить ответ. Я склонен оставить это как ответ сейчас, хотя я все еще возражаю против языка, используемого при описании неэффективности фильтров против цветения, в дополнение к мысли, что было бы лучше подробнее остановиться на упомянутых «деталях». .. оставляя -1 на данный момент. Убраны некоторые устаревшие комментарии.
Patrick87
@DW Под «ложноотрицательным» я намереваюсь ответить «новым», когда ответ должен был быть «не новым». (Несколько нелогично, но «не новый» является положительным случаем здесь.) Вам не нужно сохранять «все данные когда-либо», чтобы осуществить это, хотя я склонен полагать, что вам действительно нужно сохранять целые элементы (просто не все элементы - если вы не готовы принять гипотетически значимую вероятность ошибки, как в другом ответе на вопрос здесь.)
Patrick87
6

Как насчет хеш-таблицы? Когда вы видите новый элемент, проверьте хэш-таблицу. Если место элемента пусто, верните «новый» и добавьте элемент. В противном случае проверьте, не занято ли место предмета. Если это так, верните «не новый». Если место занято каким-либо другим элементом, верните «новый» и перезапишите место новым элементом.

Вы определенно всегда правильно получите «Новый», если вы никогда не видели хэш элемента раньше. Вы определенно всегда правильно получите «Не новый», если вы видели только хэш элемента, когда видели тот же элемент. Единственный раз, когда вы получите «Новый», когда правильный ответ «Не новый», - это если вы видите элемент А, затем видите элемент Б, затем снова видите элемент А, и оба хеша A и B одинаковы. Важно отметить, что вы не можете получить «Не новый» неправильно.

Patrick87
источник
1
Я полагаю, что этот вид игнорирует проблему эффективности использования пространства, или, скорее, значительно менее эффективен, чем фильтр Блума, так как фильтру Блума действительно нужно всего лишь немного для каждой корзины, и для этого требуется столько же места для каждой корзины, сколько требуется пространства для представлять предметы. Ну да ладно ... если вселенная не конечна (как в ответе Wandering Logic), я думаю, что вы, вероятно, не сможете приблизиться к эффективности пространства фильтра Блума.
Patrick87
Лично я думаю, что ваш ответ намного лучше, чем мой. Фильтр Блума - это не просто бит на сегмент, если вы хотите, чтобы вероятности были выше 50%. Это также фиксированный размер, и как только вы заполните его более чем наполовину, вероятность ложных срабатываний резко возрастает. Нет удобного способа его расширения, нет удобного способа использовать его в качестве кэша и нет удобного способа удаления элементов. Я возьму хэш-таблицу каждый раз.
Блуждающая логика
@WanderingLogic Использование небольшого счетчика насыщения вместо одного бита позволяет поддерживать удаление (за счет емкости и, конечно, только если счетчик не на максимуме).
Пол А. Клейтон,
4

В случае, когда совокупность элементов конечна, тогда да: просто используйте фильтр Блума, который записывает, какие элементы находятся вне набора, а не в наборе. (То есть используйте фильтр Блума, который представляет собой дополнение интересующего вас набора.)

Место, где это полезно - разрешить ограниченную форму удаления. Вы держите два фильтра Блума. Они начинают пустыми. Когда вы вставляете элементы, вы вставляете их в фильтр Блума А. Если позже вы захотите удалить элемент, вы вставляете этот элемент в фильтр Блума B. Невозможно восстановить его. Чтобы выполнить поиск, вы сначала ищите в фильтре Блума A. Если вы не нашли соответствия, элемент никогда не вставлялся (с вероятностью 1). Если вы нашли совпадение, элемент может (или не может) быть вставлен. В этом случае вы выполняете поиск в фильтре Блума B. Если вы не нашли соответствия, элемент никогда не удалялся. Если вы нашли совпадение в фильтре Блюма, возможно, элемент был вставлен, а затем удален.

Это на самом деле не отвечает на ваш вопрос, но в этом ограниченном случае фильтр Блума B выполняет именно то поведение «фильтра Блума», которое вы ищете.

Исследователи фильтра Real Bloom используют гораздо более эффективные способы представления удаления, см. Страницу публикации Майка Митценмахера .

Блуждающая логика
источник
В этом вопросе мы обрабатываем элементы, и их нет. Нет смысла хранить комплимент, не удаляя элементы из фильтра Блума
Джо,
1
@Joe: я согласен, что проблема вообще неразрешима, поэтому я ограничил свой ответ случаем, когда дополнение было конечным и небольшим.
Блуждающая логика
1

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

Примером могут быть IP-адреса, и вы хотите знать каждый раз, когда появляется сообщение о том, что вы никогда не видели раньше. Но это все еще ограниченный набор, так что вы знаете, чего ожидать.

Фактическое решение простое:

  1. Добавьте все свои предметы в фильтр подсчета цветов.
  2. Когда вы видите новый элемент, он будет иметь значения во всех слотах.1
  3. Увидев реальный новый элемент, вычтите его из фильтра.

Таким образом, у вас могут быть значения «ложных срабатываний», которые на самом деле были старыми, но были признаны новыми. Однако вы никогда не получите «не новое» для нового значения, так как его значение все еще будет во всех слотах, и никто другой не мог бы забрать это.

Томас Але
источник