Можно ли дедуплировать гиперлоглог так, чтобы при добавлении и удалении элемента получался относительно правильный уникальный счетчик?

Question

Если я хочу получить уникальный счетчик в списке элементов, которые можно добавлять и удалять, есть ли способ сделать это?

Например,

add key1
delete key1
add key1

должно датьуникальный счет 1

, но если у меня есть простой метод 2 hll, один для удаления и один для добавления, он возвращает 0?

Есть ли способ дедупликации ключа в hll?

Answer 1

Вы можете хранить отдельный HyperLogLog для подсчета удаленных элементов и вычитать, чтобы получить окончательный счет.Однако при таком подходе есть предостережения: 1. В зависимости от вашего приложения, удаление может потребоваться учитывать только тогда, когда значение было просмотрено ранее, что на самом деле невозможно узнать.2. Точность будет снижаться в зависимости от схемы добавления и удаления элементов.

Answer 2

Я не вижу, как это сделать с журналом гипер-журнала, но я вижу, как это сделать с менее эффективными оценками кардинальности.

Вот простая оценка кардинальности, которую вы можете найти в http://www.cse.unsw.edu.au/~cs9314/07s1/lectures/Lin_CS9314_References/fm85.pdf. Рассчитать значение хеш-функции каждого элемента.Сохраняйте наименьшие значения хеш-функции m.Используйте размер хеш-значения m для оценки мощности всего набора.(Давайте проигнорируем коллизии хешей.)

Теперь вот адаптация для обработки некоторых удалений.Сохраняйте наименьшие значения хеша 2m.Используйте размер наименьшего числа m, чтобы оценить мощность всего набора.Если хеш-элемент должен быть удален, просто удалите его из набора.Пока ваш набор не уменьшится в размере примерно в 2 раза, это должно работать очень хорошо.

А если вам нужно обрабатывать больше?Добавьте идею «призрачных» элементов.Когда вы удаляете хеш-значение, добавьте «призрачное» хеш-значение, где ожидаемое хеш-значение будет 2m+1.Когда вы удаляете реальное хеш-значение, каждый элемент-призрак имеет случайный шанс быть удаленным, если он соответствует доле реальных элементов, которые были удалены.Если призрак удален, вы вставляете больше.Если вы вставите достаточно, чтобы призрак стал слишком большим, чтобы оказаться в наименьшем 2m, вы позволите ему упасть, как и любое другое значение.

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