Количество ложно-положительных срабатываний фильтра Блума.
Описание
Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.
Грубо говоря, фильтр Блума возвращает 2 возможных ответа:
- элемента нет в векторе
- элемент возможно есть в векторе
Блум проанализировал вероятность таких ошибочных ответов, но его анализ является некорректным.
Читать полностью »
