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

Question

Я пытаюсь создать структуру данных для набора фиксированного размера, которые должны поддерживать следующие операции:

1. Запроса ли элемент в наборе (ложные срабатывания в порядке, ложноотрицательные нет)
2. Заменить один элемент множества с другим элементом

в моем случае, размер набора, вероятно, будет очень мало (4-16 элементов), но поиск должен быть как можно быстрее и считаться как несколько бит как pos sible. Кроме того, он должен быть эффективным с точки зрения пространства. Замены (т. Е. Операция 2), вероятно, будут немногочисленными. Я посмотрел на следующие варианты:

1. Блум Фильтры: Это стандартное решение. Тем не менее, трудно удалить элементы и, как таковые, трудно реализовать операцию. 2.
2. Подсчет цветных фильтров: Требование к пространству становится намного выше (~ 3-4 раза) от стандартного фильтра Bloom без уменьшения ложных + ve ставок.
3. Простое хранение списка хэшей всех элементов: Дает лучшие значения ложных + ve, чем подсчет фильтра цветения для аналогичных требований к пространству, но стоит дорого смотреть (в худшем случае все биты будут проверяться).
4. Предыдущая идея с идеальным хешированием для местоположения: У меня нет идеи о быстрых совершенных хэшах для небольших наборов элементов.

Дополнительная информация:

• элементов являются 64-битными числами.

Любые идеи о том, как это решить?

Answer 1

Ну, обратите внимание на следующее:

1. Используя стандартную хэш-таблицу, с функцией спуска хэш (так как это число, есть куча стандартных хэш-функций) с 4 | S | записи потребуются в среднем менее двух поисковых запросов (при условии, что в качестве входных данных указаны несмещенные номера), хотя это может ухудшиться до ужасного худшего случая 4 | S |. Конечно, вы можете связать его следующим образом:
   
   - Если количество найденных ячеек превышает k - прервите и верните true (это приведет к FP с некоторой вероятностью, что вы можете caclculate, и даст более высокую производительность в худшем случае).

2. Что касается подсчета цветковых фильтров - это способ сделать это, ИМО. Обратите внимание, что фильтр цветения (стандарт) требует 154 бит, чтобы вероятность FP составляла 1%, или 100 бит, чтобы иметь вероятность FP 5%. (*)
   Итак, если вам нужно в 4 раза больше этого номера, вы получите 616 бит/400 бит. Обратите внимание, что в большинстве современных машин это достаточно мало, чтобы заполнить несколько блоков CPU-Cache, что означает (в зависимости от машины) - Чтение всех этих битов действительно может занимать менее 10 циклов на некоторых машинах.
   IMO вы не можете ничего сделать, чтобы побить его, не получив гораздо более высокую ставку FP.

(*) Calculated according to:

т = п п (р)/пер (2)

P.S. Если вы можете гарантировать, что каждый элемент удаляется не чаще одного раза, вы можете использовать вариацию фильтра цветения с двойным пространством, а у него немного лучше FP, но также имеет несколько FN, просто используя 2 цветных фильтра: 1 для regular и 1 для deleted. Элемент находится в наборе, если он находится в regular и НЕ в deleted.
Это улучшает скорость FP за счет наличия также FN

Answer 2

Фильтр кукушки - это вариант, который следует учитывать. Процитируем их абстрактную

Кукушка Фильтр: Практически лучше, чем Блум

Мы предлагаем новую структуру данных называют кукушкой фильтр, который может заменить фильтры Блума для испытаний член ПКР приблизительная набор. Фильтры с кукушкой поддерживают , добавляя и удаляя элементы динамически, достигая даже более высокой производительности, чем фильтры Bloom. Для приложений, в которых хранятся многие элементы, и целевые умеренно низкие значения ложных срабатываний, ** фильтры с кукушкой имеют более низкую накладную площадь, чем фильтры Bloom, оптимизированные по пространству. Наши экспериментальные результаты также показывают, что фильтры кукушки исключают предыдущие структуры данных, которые расширяют фильтры Bloom, чтобы поддерживать удаление по существу как во времени, так и в пространстве.

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf