Интересный пример использования фильтров Блума

Сегодня случайно нашел в одной из папок Google Chrome пару интересных файлов:

• Safe Browsing Bloom
• Safe Browsing Bloom Filter 2

Вывод: Хром использует фильтры Блума для предварительной оценки того, является ли веб сейт, на который вы пойдете, вредоносным ;) Хорошая находка!

Поясню, как это работает:

• URL приводится к каноническому виду.
• Вычисляются N его "длинных" хешей (скорее всего, 64 битных).
• Значение каждого хеша умножается на скейл-фактор, таким образом получаются N адресов битов в массиве данных, называемом фильтром Блума.
• Фильтр построен так, что если все эти биты - единички, сайт с большой вероятностью вредоносный (в этом случае происходит его достоверная верификация - видимо, путем запроса к соотв. сервису Google); иначе он гарантированно "безопасный" (гарантировано - = его 100% нет в БД вредоносных сайтов).
• Более подробное описание фильтов Блума - здесь.

Эффективность сего метода заключается в том, что:

• Размер такого фильтра заметно меньше любой другой структуры, которая могла бы дать ответ на подобный вопрос точно. Например, если бы это был set (структура данных), его длина была бы ~ равна суммарной длине URL всех  вредоносных сайтов, входящих в него. А блум-фильтр, дающий ложнопозитивные ответы с вероятностью всего 1% (ложнонегативных он не дает вообще), потребует в среднем 9.6 бита на каждый URL, т.е. порядка 1 байта! Фильтры Хрома в сумме занимают порядка 18Мб - и если они действительно построены для обеспечения такой вероятности ложнопозитивных ответов, это значит, что они содержат информацию о ~ 1 миллионе вредоносных сайтов!
• Такой фильтр позволяет Хрому обращаться к сервисам верификации практически только тогда, когда пользователь действительно идет на вредоносный сайт. Ну не замечательно ли? ;)

P.S. Я сразу обратил внимание на эту пару файлов потому, что у нас в Xtensive.Indexing есть их отличная реализация, а в Xtensive.Core - API для вычисления 64-битных хешей, позволяющий блум-фильтрам получать нужное количество 64-битных хешей (вернее, нужное количество значений уникальных 64-битных хеш-функций) как для встронных, так и для ваших собственных типов (для каждого собственного типа, понятно, потребуется написать Hasher, но это весьма просто, т.к. хешеры уже реализованы для CLR-типов).

P.P.S. Как вы уже поняли, с сегодняшнего дня я буду "разбавлять" свой русский политико-киношный блог переводами постов из своего же английского промо-программистского ;) В ближайших планах - перевод цикла статей об оптимизациях, используемых в ORM-решениях: "Может ли ORM сделать ваше приложение более производительным?".