Вероятностный набор для очень низкой вероятности

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

Вариант использования — пожарный шланг соответствия Gnip/Twitter, где мы получаем около 1000 событий в секунду (это удаления из всего Twitter). У нас есть таблица, скажем, из 10 миллионов сохраненных твитов (каждый год эта сумма увеличивается), и если элемент появляется в списке пожарных шлангов, я должен его удалить. Я предполагаю, что совпадение будет происходить каждые 100 000 секунд (чтобы вытащить число из воздуха).

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

Есть ли для этого хорошая сублинейная структура данных?


data-structures bloom-filter
person Joe    schedule 20.10.2016    source источник
comment
Вы пробовали использовать хэш-таблицу?   -  person TilmannZ    schedule 20.10.2016
comment
Хеш-таблица будет линейно увеличиваться в размере, чего я пытаюсь избежать.   -  person Joe    schedule 20.10.2016

Ответы (2)


arrow_upward
0
arrow_downward

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

У вас есть 10 миллионов сохраненных твитов, и вы ожидаете, что они будут расти примерно на 10 миллионов в год. Итак, создайте фильтр Блума емкостью в миллиард с вероятностью ложных срабатываний 0,1%. Согласно калькулятору Bloomfilter, это будет стоить вам 1,67 гигабайта.

Поймите, что число "ложных срабатываний" предполагает, что фильтр содержит 1 миллиард ключей. Когда ваш фильтр очень мало заполнен, вероятность ложных срабатываний намного ниже.

Если вы получаете тысячу твитов в секунду, а фильтр Блума имеет процент ложных срабатываний 0,1%, то в худшем случае вы получите в среднем одно ложное срабатывание в секунду. Таким образом, один раз в секунду ваш код должен обращаться к базе данных, чтобы определить, существует ли твит.

Но пройдет много лет, прежде чем вы до этого доберетесь. При наличии всего 10 миллионов существующих записей и скорости роста 10 миллионов в год пройдет 10 лет, прежде чем фильтр будет заполнен хотя бы на 10%. Вероятно, вы могли бы уменьшить размер фильтра до 500 миллионов (860 МБ) и все равно не заметить большого успеха из-за ложных срабатываний.

person Jim Mischel    schedule 20.10.2016
comment
Я не слишком внимательно рассматривал вероятности; похоже, что ванильный фильтр Блума может справиться с этой задачей. Я просто решил проверить, нет ли другой структуры данных, предназначенной для «невероятного» случая. Большое спасибо за ответ, буду пробовать. - person Joe; 20.10.2016

arrow_upward
0
arrow_downward

Фильтр Блума должен подойти, если он помещается в памяти. Если он не помещается полностью в памяти, рассмотрите возможность использования решения, описанного в этом бумага.

В качестве альтернативы, если вы действительно хотите немного повысить производительность, вы можете использовать Cuckoo Filter, но вам будет сложнее найти реализацию с открытым исходным кодом; вот один в Go.

person cabad    schedule 20.10.2016