Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Рандомизированные структуры данных, фильтры Блюма как в Google Chrome
Рандомизированные алгоритмы

Что: Лекция
Когда: Среда, 03 марта 2021, 18:10–19:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

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

Фильтр Блюма в прямом смысле слова могут служить фильтром перед более дорогой проверкой наличия элемента во множестве: например, Google Chrome сначала проверяет наличие URL в фильтре Блюма на компьютере пользователя перед тем, как искать URL в онлайновом списке вредных сайтов. Фильтр Блюма всех вредных сайтов достаточно мал, чтобы храниться на компьютере пользователя, а к серверам Гугла приходится обращаться только в том случае, в которых фильтр может ошибиться, то есть, если фильтр утверждает, что URL -- опасный.