HyperLogLog

HyperLogLog

집합의 카디널리티(고유 원소 개수)를 매우 작은 메모리(KB)로 근사 추정하는 확률적 자료구조로, 해시 함수와 조화 평균을 활용하여 1-2% 오차로 수십억 원소를 추정

목적: 카디널리티 추정, 중복 제거, 고유 방문자 수, 메모리 효율

특징: 확률적, 매우 작은 메모리, 병합 가능, 표준 오차 ~1.04/√m

구조: m개 레지스터(버킷), 각 레지스터는 최대 선행 0 개수 저장

동작

• •add(item): ① 해시 계산 → ② 하위 p비트로 레지스터 선택 → ③ 상위 비트의 선행 0 개수+1을 레지스터에 최대값 갱신
• •count(): 조화 평균 계산 → 보정 상수 적용 → 카디널리티 추정

수식: E = α_m × m² / Σ(2^(-M[i])) - 조화 평균 기반

메모리: m개 레지스터 × log₂(log₂(n)) 비트, m=2^14이면 ~12KB로 수십억 원소 추정

시간 복잡도: add·count 모두 O(1)

공간 복잡도: O(m) - 매우 작음, KB 단위

장점: 극소 메모리, 빠른 연산, 병합 가능(여러 HLL 합침), 확장성

단점: 근사값만 제공, 원소 나열 불가, 삭제 불가

적용사례: 웹 분석(고유 방문자), 데이터베이스(DISTINCT COUNT), Redis HyperLogLog, 빅데이터 처리, 네트워크 모니터링

비교: HyperLogLog(근사/KB) vs 해시 셋(정확/GB) vs 비트맵(밀집/MB)

연관: 확률적 자료구조, 카디널리티 추정, 해시 함수, Redis