Лучший фильтр для MANET

Question

Я знаю про фильтр Блума.

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

Как лучший пример, приведенный Таруном

Мне нужно знать, по крайней мере, на 2/3 лучше и быстрее фильтр, чем фильтр Блума, где требуется меньше памяти?

Мне нужен фильтр или какой-либо метод лучше, чем фильтр Блума, который может быть полезен в мобильной сети ad hoc для хранения IP-адресов устройств и выявления конфликтов адресов.

Answer 1

Не намного лучше, чем Bloom Filter, но вы можете взглянуть на Cuckoo Filters. Однако вам будет сложнее найти реализацию с открытым исходным кодом; вот один в го.

Ссылаясь на оригинальную фильтровальную бумагу Cuckoo:

Фильтры с кукушкой улучшают фильтры Блума тремя способами: (1) поддержка динамического удаления элементов; (2) лучшая производительность поиска; и (3) лучшая эффективность использования пространства для приложений, требующих низкого уровня ложных срабатываний ( < 3%).