Когда полезен фильтр Блума?

Question

Я понимаю, что делает фильтры Блума привлекательной структурой данных; однако мне трудно понять, когда вы можете их использовать, поскольку вам все еще приходится выполнять дорогостоящую операцию, которую вы пытаетесь избежать, чтобы быть уверенным в том, что вы не обнаружили ложного срабатывания. Из-за этого они обычно просто не добавляют много накладных расходов? Например, статья в википедии, посвященная фильтрам Блума, предлагает использовать их для синхронизации данных. Я вижу, как было бы здорово в первый раз, когда фильтр Блума пуст, но скажу, что вы ничего не изменили, и вы снова собираетесь синхронизировать свои данные. Теперь каждый просмотр фильтра Блума будет сообщать, что файл уже был скопирован, но разве нам не нужно было бы предварительно выполнить задачу медленного поиска, которую мы пытались избежать, чтобы на самом деле убедиться, что это правильно?

Answer 1

По сути, вы используете фильтры Блума, чтобы избежать долгой и трудной задачи доказательства того, что элемент не существует в структуре данных.Почти всегда сложнее определить, что чего-то не хватает, чем того, что существует, поэтому фильтр помогает компенсировать потери в поисках вещей, которые вы все равно не найдете.Это не всегда работает, но когда это происходит, вы получаете огромную выгоду.

Answer 2

Фильтры Блума очень эффективны в случае запросов членства, то есть, чтобы определить, принадлежит ли элемент к набору. Количество элементов в наборе не влияет на производительность запроса.