Является ли фильтр Блума только с одним входным хешем фильтром Блума? - PullRequest
Новая
       30

Является ли фильтр Блума только с одним входным хешем фильтром Блума?

0 голосов
/ 26 ноября 2018

Если я реализую фильтр Блума, в котором используется только один алгоритм хэширования (например, шум), будет ли он по-прежнему считаться фильтром Блума?

Например, если a хеширует до 5, то бит5 фильтра будут установлены.Если b хеширует до 1, то будет установлен бит 1 фильтра и т. Д. ...

Чтобы что-то считалось фильтром Блума, сделайте, чтобы по крайней мере два бита в фильтре имелиустановить?Если установлен только один бит, это называется чем-то другим?

1 Ответ

0 голосов
/ 04 декабря 2018

Это все еще фильтр Блума: один с k=1.В зависимости от количества бит на элемент, он, вероятно, не самый экономящий место.Но есть различные причины, по которым можно выбрать k, который не round(bitsPerKey * log(2)), основные из них:

  • Чтобы иметь возможность лучше сжимать: здесь фильтр Блума с k=1Лучший.См. Также статью «Сжатые фильтры Блума» от Михаэля Миценмахера.
  • Чтобы ускорить поиск и обновление: использование меньшего k быстрее.

Кстати, вы все равно можете выбрать k как наиболее экономящий место, даже если вы используете только одну «хэш-функцию приложения» (например, хэш Murmur с 64 битами).Вы просто выбираете «хэш-функции Блума» как функцию этой «хэш-функции приложения» (64-битный хэш Murmur), например, так (при условии, что int является 32-битным, а long - 64-битным): 

long m = murmur(x)
h(x, i) = (int) (m >> 32) + i * (int) m

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

long m = murmur(x)
int hash = (int) (m >> 32);
int add = (int) m;
for (int i = 0; i < k; i++) {
    ... test / set the bit depending on "hash" ...
    hash += add;
}

Многие библиотеки фильтров Bloom делают это так, например, реализация фильтра Bloom в Guava.

...