A general purpose counting filter: making every bit count

https://blog.acolyer.org/2017/08/08/a-general-purpose-counting-filter-making-every-bit-count/amp/

• Approximate Membership Query (AMQ). Example: Bloom filter.

• Определять, принадлежит какой-то элемент данному множеству.

• Не возвращают false negative (т.е. они говорят, что не принадлежат, хотя они принадлежат), но могут возвращать false positive.

• => Суммарно на вопрос “объект в множестве?” отвечают либо “No”, либо “Возможно”

• Расширения: удаление, изменение размеров множеств, вести подсчет кол-ва, etc

• 4 недостатка Bloom фильтров:

  • Невозможность удалить объекты
  • Плохо скалируются за размер RAM
  • Невозможность динамически изменить размер
  • Невозможность определить кол-во вхождений каждого элемента

• В paper придумана новая AMQ структура: Counting Quotient Filter (подсчетный количественный фильтр) = CQF structure

• Все недостатки Bloom фильтра ушли, очень хорошо работает (время, объем памяти)

• В несколько раз быстрее Bloom Filter, cuckoo filter

• Поддержка количества объекта - это огромный плюс

• Обычный QF (долевой фильтр) -> RSQF (rank and reset based quotient filter) -> CQF

• QF: 

  

• храним в h0-вой ячейке h1 (домашняя), либо сдвиг на соседнюю.

• QF использует чуть больше места, чем Bloom, но намного меньше, чем counting bloom.

• QF скорость сравнима с Bloom.

• QF лучше переиспользует cache значения, чем Bloom, поэтому лучше и быстрее работает на SSD

• Производительность значительно падает после 60% наполнения

• RSQF:

  • 2.125 бита медаданных на слот (вместо 3)
  • лучше работает при заполненной таблице (QF max заполненность = 75%, RSQF ~ 95%)
  • структура метаданных позволяет использовать rank и select операции -> быстрее на x86
  • немного другая структура метаданных (occupieds, rundends) , попытка всегда хранить в “домашнем” слоте
  • дополнительные инварианты: сравнение h0(x) <= h0(y) ===> h1(x) хранится левее h1(y)
  • дополнительный runends бит-вектор, хранящий 1 если слот содержит последний remainder в ряду. 

    

    

• RANK(B,i) - возвращает кол-во 1-чек в B до позиции i

• SELECT(B,i) - возвращает индекс первой 1-цы в B

• обе функции будут бегать по occupieds, runends, remainders - плохо с кэшом, поэтому

• добавлен offsets массив, который хранит дистанцию от слота i до runend, который соответствует этому слоту i. Для оптимизации, сохраняют только для каждого 64-го слота (uint8) -> 2.125 бита на слот

• Т.е. делят на блоки по 64 записи, которые хранятся вместе -> все операции хорошо оптимизируются на machine-word операции PDEP, TZCNT

• Counting Quotient Filters

  • добавляют подсчет количества к RSQF
  • variable-size counters (счётчики переменного размера) -> эффективно по размеру для любых распределений (разряженно-плотных)
  • если элемент присутствует более, чем однажды - тогда следующий за remainder слот хранит количество раз этот элемент присутствует.
  • CQF разделяет remainder или счетчик т.к. счетчик увеличивается, и любые изменения -> число.
  • Есть трюки

• Сравнение использование места 

  

  

• CQF лучше почти всегда.

• CQF может быть сделан мультитредовым (шарды, лочатся всегда по два)

• Сравнение по производительности:

  • CQF в несколько раз лучше Bloom FIlter, хотя тот не поддерживает счетчик. И на порядок-два лучше Counting Bloom Filter(CBF)