유니크 카운터, 확률 론적 데이터 구조 병합

Question

1 2 3 및 3 4에는 3 및 2 고유 항목이 있습니다.

이제 병합 된 세트의 고유 항목을 계산해 봅시다. 카운터 3 + 2 = 5을 합산하면 잘못 될 것입니다 (uniq(1 2 3 3 4) = 4이어야합니다).

카운터를 사용하는 할 방법이 있습니까? 각 카운터에 대해 상수 메모리 데이터 구조를 나타내는 추가 데이터를 사용하는 것이 좋습니다. 작은 오류도 OK, 95 % 정확도라고 가정 해 봅시다.

아주 작은 메모리 (HyperLogLog)를 사용하는 확률 론적 고유 카운터가 있음을 알고 있습니다. 그러나 두 가지 확률 카운터를 병합하는 방법이 있습니까?

Answer 1

예, HyperLogLog는 실제로 자연스럽게 병합을 허용하며 대부분의 구현에는 병합이 포함됩니다. 요약하면, 두 개의 HyperLogLog 구조 A와 B를 새로운 C에 병합하려면 각 버킷 쌍 C [i] = max (A [i], B [i])의 최대 값을 취하십시오.