19
правок
Изменения
Нет описания правки
<tex dpi = "180">k = \ln 2 \frac {m}{n} \approx 0.6931 \frac {m}{n}</tex>
== Вероятностное множество ==
Фильтр Блума является примером '''вероятностного множества''', структуры данных, способной добавлять элемент в множество и способной также с некоторой вероятностью корректно отвечать на запрос о наличии элемента в множестве. В ответ на некоторый запрос есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве есть, ответ в любом случае будет положительным. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
Google BigTable использует фильтры Блума, пример '''вероятностного множества''', для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску.
Проще говоря, вероятностное множество - это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
* Элемент точно не принадлежит множеству,
* Элемент возможно принадлежит множеству.
== Свойства ==
