하이퍼로그로그 (HyperLogLog)
쉽게 풀면
방문자가 몇 명인지 세려면 보통은 이미 본 사람 명단을 들고 있어야 합니다. 이 방법은 명단 대신 해시값의 앞부분에 0이 연달아 몇 개 나왔는지만 기억합니다. 0이 아주 많이 연달아 나오는 값을 보았다면 그만큼 많은 서로 다른 값을 관찰했으리라 추론하는 원리로, 수십억 개의 원소도 몇 킬로바이트로 세어 냅니다.
왜 중요한가
고유 방문자 수나 고유 검색어 수처럼 중복을 제외한 개수를 세는 일은 데이터 분석에서 매우 흔한데, 정확히 세려면 메모리가 원소 수에 비례해 늘어납니다. 이 자료구조는 1~2% 오차를 허용하는 대신 메모리를 상수로 고정해 주고, 여러 집계 결과를 손쉽게 합칠 수 있어 분산 시스템과 궁합이 좋습니다. 주요 데이터베이스와 캐시 시스템에 기본 기능으로 탑재되어 있습니다.
논문에서는 이렇게 쓰입니다
중복을 뺀 사용자 수를 아주 작은 메모리로 충분히 정확하게 셌다는 뜻입니다.
조금 더 깊게 보면
각 원소의 해시값 앞쪽 비트로 버킷을 정하고 나머지 비트에서 처음 1이 나오는 위치를 그 버킷의 최댓값으로 기록합니다. 버킷별 값들의 조화 평균에 보정 상수를 곱해 기수를 추정하며, 조화 평균 덕분에 이상치의 영향이 줄어듭니다. 표준 오차는 버킷 수 m에 대해 대략 1.04/√m이고, 기수가 아주 작거나 아주 클 때를 위한 보정식이 함께 쓰이며, 버킷별 최댓값만 취하면 여러 스케치를 합칠 수 있습니다.
주의할 점
카운트-민 스케치가 각 항목이 몇 번 나왔는지를 추정한다면, 하이퍼로그로그는 서로 다른 항목이 몇 종류인지만 추정하고 개별 항목의 정보는 복원할 수 없습니다. 교집합의 크기를 직접 구할 수 없어 포함-배제로 계산하면 오차가 크게 증폭된다는 점도 실무에서 자주 문제가 됩니다.