guava - bloomfilter: возможно ли получить истинно-отрицательное значение для значения, которое ** ранее ** было ложноположительным?

Если я правильно понимаю, когда элемент put внутри фильтра цветения гуавы, mightContain всегда будет возвращать истину. Если фильтр возвращает false на mightContain, значит, значение никогда не помещалось в фильтр. Что мне интересно, так это для значений, которые might являются ложноположительными в данный момент, поскольку по мере того, как вводится больше значений, однажды ложные срабатывания могут позже стать истинно-отрицательными (если они, конечно, не введены) .

Что-то вроде этого:

GuavaBloomFilter<Integer> bf = new GuavaBloomFilter<>(blah, blah);
# if I start checking, none of the values should return tru at the monent
System.out.println(bd.mightContain(5)); // false
System.out.println(bd.mightContain(10)); // false
System.out.println(bd.mightContain(15)); // false
# fine
# let's put in a value now
bf.put(10);
System.out.println(bd.mightContain(5));
System.out.println(bd.mightContain(10)); // true, every time from now on
System.out.println(bd.mightContain(15));

На последних трех проверках при проверке на 10 он всегда возвращает true. Для 5 и 15 он может вернуть true. Предположим, что для 5 мы получаем ложь (никогда не вставляем внутрь), для 15 мы получаем ложное срабатывание.

Итак, продолжаем:

bf.put(5);
System.out.println(bd.mightContain(5)); // true, every single time from now on
System.out.println(bd.mightContain(10)); // true, every time from now on
System.out.println(bd.mightContain(15));

Итак ... теперь, проверяя 5, мы always получим истину. Возможно ли, что из-за изменения состояния внутри фильтра Блума результат проверки 15, который ранее был ложноположительным, мог бы вернуть истинно-отрицательное значение?


java bloom-filter false-positive guava
person eftshift0    schedule 28.02.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Для истинного фильтра Блума биты всегда меняются только от 0 до 1, и никогда не возвращаются, поэтому результат вызова mightContain может всегда переходить только от false к true, и никогда обратно, потому что mightContain возвращает истину, если определенное подмножество всех битов 1, и как только они станут 1, они останутся 1.

Реализация Guava действительно является настоящим фильтром Блума, поскольку метод BloomFilter.put (source) делегирует Strategy.put (source), интерфейс реализован в BloomFilterStrategies (источник). Биты фильтра Блума хранятся в LockFreeBitArray с именем bits, а стратегия вызывает только его методы bitSize, set и get. Из них только set изменяет биты (source), и для их изменения используется только побитовый оператор 'или' |. Это никогда не может изменить 1 обратно на 0.

Таким образом, действительно невозможно, чтобы значение, которое ранее было ложноположительным, впоследствии стало истинно-отрицательным.

person kaya3    schedule 28.02.2020