Как построить фильтр Блума с размером, который не помещается в оперативной памяти? - PullRequest
0 голосов
/ 13 мая 2018

Предположим, нам нужно построить фильтр Блума с 10 ^ 12 сегментами на одной машине с 32 ГБ ОЗУ и жестким диском.Предположим, что ключи маленькие и уже на жестком диске.Как мы могли бы построить его эффективным способом?
Я предполагаю разделить фильтр Блума на 4 части (125 ГБ / 4 соответствует 32 ГБ).Затем передайте данные 4 раза, каждый раз хешируя и обновляя соответствующий фрагмент в памяти.Объедините 4 ломтика обратно, чтобы получить полный фильтр Блума.Это правильно?

1 Ответ

0 голосов
/ 22 мая 2018

Зачем вам такой большой фильтр?Вы пытаетесь переоценить его, чтобы обрабатывать неограниченные данные из потокового источника?Если да, вы можете прочитать о фильтре Стабильный Блум и Масштабируемый Блум.Оба лучше адаптированы к такому типу данных, чем классический фильтр Блума.

Чтобы ответить на ваш вопрос, если вы разделите свой фильтр, то, что вы говорите, должно работать.Но убедитесь, что вы правильно работаете с индексами.Например, если битовый вектор из 4 элементов разделен на 2 узла, первый будет отвечать за индексы (0, 1), а второй - за (2, 3).Вы, вероятно, немного усложните это и сохраните где-нибудь отображение того, какой диапазон хранится в каком узле, и соответственно измените как чтение, так и запись.

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

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

...