Последствия положительных совпадений в фильтрах Блума

Question

Допущения:

• Имена пользователей зарегистрированных пользователей хранятся в наборе
• Я хочу использовать фильтр Блума, чтобы ускорить поиск.
• Блум фильтровать как определенную вероятность ложных срабатываний (0,1%)

Когда новый пользователь хочет зарегистрироваться, в большинстве случаев мой пользовательский интерфейс говорит ему: «Это имя не используется, вы хорошо до go ".

Но что нужно делать бэкенду, если найдено положительное совпадение?

Результат может быть ложноположительным. Разве поиск истинного ответа не увеличит сложность времени и, таким образом, сделает фильтры Блума неэффективными во многих случаях? Сказать пользователю «Имя уже используется, выберите другое имя» может быть не так уж плохо, но как насчет других случаев использования, где вы не можете ошибаться.

Answer 1

Общая модель использования фильтров Блума выглядит следующим образом:

1. Запросите фильтр, чтобы определить, может ли ответ быть да.
2. Если Блум фильтр говорит «нет», ответ определенно «нет».
3. Если фильтр Блума говорит «да», ответ может быть положительным, поэтому запросите более точную структуру данных, чтобы получить окончательное определение.

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

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