확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog

이 글은 적은 메모리로 집합의 고유 원소 개수를 추정하는 'HyperLogLog' 알고리즘의 기본 원리를 설명합니다. 웹 페이지의 UV(고유 방문자 수)나 UB(고유 브라우저 수)를 정확히 계산하는 것은 많은 메모리를 요구하거나 실시간 처리가 어렵다는 문제점을 지적합니다.

이에 대한 해결책으로, 통계적 추정과 달리 '확률적 자료구조'를 사용하여 메모리 사용량을 최소화하면서 실시간으로 근삿값을 얻는 '추정' 방식을 소개합니다. HyperLogLog는 이러한 추정 방식 중 고유 원소 개수(Cardinality)를 효율적으로 계산하는 대표적인 예시로 제시됩니다.