Вероятностный набор без ложных срабатываний?

35

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

Моя мотивация проста: учитывая огромный поток элементов для обработки (с дубликатами), мы бы хотели избежать обработки элементов, которые мы видели раньше. Обрабатывать дубликаты не повредит, это просто трата времени. Тем не менее, если бы мы пренебрегали обработкой элемента, он был бы катастрофическим. С помощью «обратного фильтра Блума» можно хранить элементы, видимые с небольшим объемом памяти, и избегать обработки дубликатов с высокой вероятностью, проверяя членство в наборе.

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

Кто-нибудь видел что-нибудь подобное? :)

Кристофер Монсанто
источник
3
Дополнение интересующего меня множества бесконечно. Как бы я это сохранил?
Кристофер Монсанто
11
Я вижу проблему (современные диски еще недостаточно велики).
Дейв Кларк,
8
Если бы у вас была такая структура данных, вы могли бы использовать ее для «мошенничества», используя ее вместе с обычным фильтром Блума и сохраняя точный набор членов.
Марк Рейтблатт
1
@MarkReitblatt и фильтры, и кэши Bloom являются вероятностными, и любая их комбинация будет вероятностной, то есть не сможет достичь точного тестирования на членство в наборе. :)
awdz9nld

Ответы:

25

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

Дэвид Эппштейн
источник
Спасибо за ответ. Да, это очевидное решение - если это также стандартное решение, похоже, мне не повезло. Ну что ж.
Кристофер Монсанто
2
Это называется кэш с прямым отображением и обычно используется в процессорах. (Любой набор кеша или кэша с потерями соответствует требованиям в различной степени). Частота появления ошибок зависит от распределения хеш-функции (лавины) и количества слотов, доступных в кеше / наборе, - соответственно. :)
awdz9nld
Также обратите внимание, что только дословные ключи могут быть сохранены без введения ложных срабатываний (например, сохранение хешированного ключа)
awdz9nld
20

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

Что хорошо в фильтре Блума, так это то, что вы можете выполнять односторонние тесты на членство элементов (с ложными срабатываниями), используя структуру данных, которая имеет фиксированный размер относительно вероятности ошибки и количества сохраненных элементов. В размерах этих элементов сами по себе не имеют значения. Например, если бы у нас был настроен фильтр Блума для хранения до 1000 элементов с ошибкой менее 3%, то мы могли бы хранить 1000 слегка отличающихся версий всего корпуса Википедии, по одной букве в каждой, и мы все равно получите метрики, которые мы хотим, и структура данных будет очень маленькой (менее килобайта). Конечно, вычисление этих хэшей будет сложной задачей, но принцип все еще остается в силе.

Теперь рассмотрите возможность хранения тех же самых массивных струн в фильтре мрака! Теперь у нас могут быть только ложные негативы. Поэтому, если мы скажем «да, эта версия всего корпуса Википедии находится в этом наборе», то мы должны быть абсолютно правы в этом. Это означает, что хеширование нам не поможет, так как всегда будет какая-то другая строка, которая хэширует с тем же значением. Единственный способ сказать «да» и быть уверенным - это сохранить всю строку или некоторые эквивалентные данные одинаковой длины. Мы всегда можем не хранить его и сказать «нет», но в конечном итоге уровень ошибок нас настигнет. Лучшее, что мы могли бы сделать, - это сжатие, приведение размера структуры к продукту энтропии хранимых данных и желаемой точности.

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

pents90
источник
оформить заказ somethingsimil.com/2012/05/21/the-opposing-of-a-bloom-filter - что не так в этой реализации /
Yehosef
@ Да, все нормально и может работать для ваших нужд, но вы заметите, что автор говорит о «нескольких идентификаторах, которые полностью идентифицируют событие». Таким образом, то, что реализуется, по-прежнему сохраняет весь объект. Итак, это вариант кеша. Реальная «противоположность фильтра Блума», если бы она существовала, не должна была бы хранить целые объекты.
pents90
Он упомянул несколько идентификаторов, которые идентифицируют событие, а не весь объект. Мне просто нужно сохранить «кеш» для session_id, а не всю запись взаимодействия. Но я слышал, что это не тот же подход, что и у блума или гиперлогога.
Yehosef
В своем «доказательстве» вы предполагаете, что существует неограниченное количество возможных записей. Однако есть случаи, когда набор возможных записей известен заранее. Например, для сборки мусора на странице памяти: вы знаете, какие записи она содержит. Теперь вы создаете «фильтр мрака», который отображает каждую возможную запись в индекс 0..n. Теперь, когда запись удалена, установите бит в этот индекс. Когда все биты установлены, вы можете собрать мусор на странице. «Фильтр мрака» - это MPHF. Чтобы учесть ложные отрицания, измените MPHF так, чтобы некоторые записи отображались в n + 1.
Томас Мюллер
@ThomasMueller Правильно, я предполагаю наихудший / состязательный случай, который является стандартной точкой зрения теории CS. Это правда, что если у вас есть только фиксированный набор из N возможных записей, то существует множество простых решений, для каждого элемента которых требуется только пространство журнала N. У фильтра Блума таких ограничений нет.
pents90
13

Вам просто нужен кеш , но вы думаете об этом странным образом.

Крейг Гидни
источник
1
... хотите уточнить? Конечно, кэш будет работать, но это не идеально, поэтому возникает вопрос об уровне техники в вероятностных структурах данных. Чтобы быть более конкретным: методы кэширования, о которых я знаю, требуют много памяти. Чем больше уровней кэша, тем больше используется хранилище. Можно наложить ограничение на элементы, хранящиеся в кэше, выполнить трюки с шаблонами использования и т. Д., Но это все еще не приближается к соотношению эффективности использования пространства и ложных ответов, которое обеспечивает фильтр Блума.
Кристофер Монсанто
1
(продолжение) При этом я мог бы забыть об очевидной технике кэширования, которая решает все мои проблемы. В таком случае, вы могли бы сделать эту технику явной вместо того, чтобы дать мне ссылку на общую категорию в Википедии?
Кристофер Монсанто
2

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не эксперт в кешировании, так что это может быть наивной идеей, а также может быть известной идеей, о которой я никогда раньше не слышал. Так что извините, если я не смогу сослаться на его ссылку (если он существует); и, пожалуйста, сообщите мне, если есть ссылка для редактирования сообщения и добавления его. (Я подозреваю, что это может иметь ссылку, потому что это так интуитивно понятно).

cc

М. Алагган
источник
0

Я использовал AVL (и иногда красно-черные) деревья с частичными элементами, чтобы действовать как фильтр без ложных негативов. Используйте только первые X байтов элемента при вставке или запросе дерева. Поскольку структура данных не является вероятностной по форме, нет риска ложноположительного результата при столкновении битов. И в отличие от кэширования всего элемента, этот подход дает вам вычисляемое максимальное пространство. Вы можете настроить частоту ложных срабатываний, рассматривая различные длины префикса / глубины дерева по сравнению со стоимостью ложных срабатываний и места.

JRideout
источник
Я также хотел попробовать попытки со строковыми данными, но мои данные, как правило, упакованы в двоичные структуры.
JRideout
0

Я думаю, что можно доказать нижнюю границу, утверждая, что вышеупомянутая структура данных не может существовать. По сути, если структура данных использует m битов, то фиксированный битовый вектор (представление входа) может соответствовать не более (((un) + n eps) \ choose (un)) наборам с помощью аргумента подсчета. Учитывая, что 2 ^ m раз это число должно быть не меньше (u \ выберите n) (все наборы должны быть представлены), мы получаем нижнюю границу, которая в основном очень близка к точному хранению множества S.

Mayank
источник