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

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

0 голосов
/ 28 февраля 2020

Если я правильно понимаю, если элемент находится внутри put внутри фильтра цветения гуавы, mightContain всегда будет возвращать true. Если фильтр возвращает 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));

При последних 3 проверках при проверке на 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, который ранее был ложно-положительным, может вернуть истинно-отрицательное значение?

1 Ответ

1 голос
/ 28 февраля 2020

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

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

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

...