City: Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Wednesday, 03 March 2021, 14:10–15:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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

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

Video

Attached files