Merge uniq counters, probabilistische Datenstrukturen

Question

Es gibt zwei Sätze 1 2 3 und 3 4 mit 3 und 2 Unikate.

Jetzt berechnen wir einzigartige Elemente im zusammengeführten Satz. Wenn wir nur die Zähler 3 + 2 = 5 zusammenfassen, wird es falsch sein (es sollte uniq(1 2 3 3 4) = 4 sein).

Gibt es einen Weg es zu tun mit nur den Zählern? Für jeden Zähler ist es in Ordnung, einige zusätzliche konstanten Speicher Datenstruktur zu verwenden, die das ursprüngliche Set darstellt, kleine Fehler sind auch ok, sagen wir 95% Genauigkeit ist in Ordnung.

Ich weiß, es gibt probabilistische eindeutige Zähler mit sehr wenig Speicher (HyperLogLog). Aber gibt es eine Möglichkeit, zwei solche probabilistischen Zähler zusammenzuführen?

Answer 1

Ja, HyperLogLog ermöglicht tatsächlich das Zusammenführen ganz natürlich, und die meisten Implementierungen umfassen das Zusammenführen. Kurz gesagt, um zwei HyperLogLog-Strukturen A und B zu einem neuen C zusammenzuführen, nehmen Sie das Maximum jedes Bucket-Paares C [i] = max (A [i], B [i]).