Почему фильтры Блума называются «фильтрами»?

Question

Почему фильтры Блума называются «фильтрами». Они ведут себя больше как наборы или, по крайней мере, анонимный набор, который можно запросить на членство. Откуда фильтр?

Answer 1

Фильтры Блума отвечают на запросы о членстве в наборе с односторонней ошибкой: они могут ответить, что ваш элемент не является членом набора или что он может быть членом набора.Это отличается от заданной структуры данных, которая может точно отвечать на запросы членства.В типичном приложении у вас есть заданная структура, которая требует дополнительных затрат, а также фильтр Блума.Вы запрашиваете фильтр Блума, если он говорит "не участник", вы верите этому.Если он говорит «возможно», вы запрашиваете набор.

Answer 2

Фильтры Блума называются фильтрами, поскольку они часто используются в качестве дешевого первого прохода для фильтрации сегментов набора данных, которые не соответствуют запросу.

Самое раннее упоминание в базе данных ACM о бумаге с заголовком «Фильтр Блума»:

Lee L. Gremillion, Проектирование фильтра Блума для дифференциального файла доступ, Связь ACM, v.25 n.9, p.600-604, сентябрь 1982

Самая ранняя ссылка в базе данных на статью с Bloom Filter в ее аннотации:

"Замечание по применению разностных файлов на компьютере дизайн "с 1978 года.

Существуют более ранние статьи, которые перечислены как цитирующие оригинальную статью, но ни одна из них не цитирует ее в своих аннотациях, а полные тексты находятся за стеной оплаты.