Альтернативы Bloom Filter

Question

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

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

Я также посмотрел фильтр Cuckoo, но его требования к памяти не соответствуют моим требованиям. Мои требования заключаются в следующем:

1. Используется при макс 6 битов на элемент
2. использовать не более 7-8 хэш-функции.

Может ли кто-нибудь предложить мне вероятностную структуру данных, отличную от упомянутой выше, которая может помочь в достижении моих требований?

Answer 1

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

Вы сказали

Я хочу, чтобы выполнить проверку принадлежности на 80 миллиардов записей лишь позволяет около 100 столкновений произойдет то, только 100 записей может быть дали ложный положительный результат.

Записи, которые находятся в карте может, по определению, не может быть ложных срабатываний. Это true положительные.

Вопрос: «100 ложных срабатываний взяты за количество записей , которые вы намерены проверить?» Если ответ также, как ни странно, 80 миллиардов, то вы просите ложную положительную ставку около 100/80 000 000 000 = 1/800 000 000, что меньше 2^-29.

Минимальное пространство для любой приблизительной структуры данных членства, такой как фильтры Блума или фильтры кукушки, равно n lg 1/ε бит, где n - количество элементов в структуре, lg - логарифмическая база 2, а ε - ложная положительная ставка. Другими словами, вам нужно больше, чем 29 бит на элемент, чтобы достичь ложной положительной скорости, равной 100 на 80 миллиардов. 6 бит на элемент вы получите 1,56% ложноположительной скорости в лучшем случае. Это 1,25 млрд. На 80 млрд. Или 100 на 6400.

Насколько я знаю, нет известных практических структур данных, которые приближаются к достижению этого. Фильтры цветка, например, не используются, потому что они используют более 1g/1 бит на элемент. Фильтры кукушки не потому, что они используют по крайней мере два дополнительных бита метаданных для каждого элемента и имеют скорость бит за элемент, которая масштабируется с помощью lg n.