19
правок
Изменения
м
→Вероятностное множество
Фильтр Блума является примером '''вероятностного множества''', структуры данных, способной добавлять элемент в множество и способной также с некоторой вероятностью корректно отвечать на запрос о наличии элемента в множестве. В ответ на некоторый запрос есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве есть, ответ в любом случае будет положительным. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
Google BigTable <ref>[https://cloud.google.com/bigtable {{---}} Google BigTable]</ref> использует фильтры Блума, пример '''вероятностного множества''', для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску.
Проще говоря, вероятностное множество - это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
