Слияния uniq счетчиков, вероятностные структуры данных

Question

Есть два комплекта 1 2 3 и 3 4 с 3 и 2 уникальные предметы.

Теперь давайте вычислим уникальные элементы в объединенном наборе. Если мы просто подытожим счетчики 3 + 2 = 5, это будет неправильно (это должно быть uniq(1 2 3 3 4) = 4).

Есть ли способ сделать это используя только счетчики? Для каждого счетчика нормально использовать некоторые дополнительные постоянную память структура данных, представляющая исходный набор, Небольшие ошибки также в порядке, скажем, точность 95% в порядке.

Я знаю, что есть вероятностные уникальные счетчики, использующие очень мало памяти (HyperLogLog). Но есть ли способ объединить два таких вероятностных счетчика?

Answer 1

Да, HyperLogLog фактически позволяет слить вполне естественно, и большинство реализаций включают слияние. В двух словах, чтобы объединить две структуры A и B HyperLogLog в новую C, возьмите максимум каждой пары ковша C [i] = max (A [i], B [i]).