HyperLogLog는 킬로바이트 단위로 수십억 개의 고유 항목을 세었다

정확한 카디널리티 — 얼마나 많은 고유 사용자, IP 주소 또는 검색 쿼리가 나타났는지 — 는 보통 고유 항목 수에 비례하는 메모리를 필요로 하며, 이는 인터넷 규모에서는 불가능하다. 2007년 INRIA의 Philippe Flajolet과 동료들은 HyperLogLog를 발표했는데, 이는 약 1.5킬로바이트의 메모리로 약 2퍼센트의 정확도로 10억을 넘는 카디널리티를 추정하는 확률적 스케치다.

이 기법은 동전 던지기 직관에 기반한다: 모든 원소를 균등한 난수로 해시하고 선행 0의 최장 연속 길이를 관찰한다. n개의 0 연속은 드물다 — 확률 2^-n — 따라서 그것이 나타나면 집합은 아마 그것을 만들어낼 만큼 충분히 클 것이고, 2^n이 카디널리티의 좋은 추정치가 된다. HyperLogLog는 스트림을 여러 부분집합으로 나누고, 부분집합마다 하나의 레지스터를 두어 그 최장 0 연속 길이를 저장하며, 조화 평균으로 이들을 결합하여 이상치가 추정치를 왜곡하지 않도록 한다.

이 방법은 Flajolet-Martin의 1984년 알고리즘과 LogLog 알고리즘에서 유래했다. 이를 프로덕션에 사용할 수 있게 만든 엔지니어링은 Google의 Heule, Nunkesser, Hall이 쓴 2013년 논문 'HyperLogLog in Practice'에서 나왔으며, 이 논문은 크고 작은 카디널리티에 대한 편향과 희소성 문제를 해결했다.

Redis는 HyperLogLog를 제품 기능으로 만들었다: PFADD, PFCOUNT, PFMERGE 명령은 키당 최대 12 KB의 메모리와 0.81퍼센트의 표준 오차로 최대 2^64개의 고유 원소를 추정하며, 스케치는 병합되므로 원시 스트림을 다시 읽지 않고도 일별 집계를 결합할 수 있다.

해시 선행 0으로부터 개수를 추정

해시는 임의의 데이터를 동일한 카디널리티를 가진 균등한 난수로 바꾼다

최장 선행 0 연속은 집합 크기에 대한 자연스럽고 관찰 가능한 추정치다

레지스터로 나누고 조화 평균을 취하면 잡음이 상쇄된다

스케치는 병합되므로 원시 스트림을 저장하지 않고도 일별 집계를 결합할 수 있다

답이 근사치만 필요할 때는 데이터를 저장하는 것을 멈추고 — 무작위성이 크기를 드러내는 작은 스케치를 저장하며, 한정된 오차를 무한한 규모와 맞바꾸라.

HyperLogLog는 분석과 데이터베이스의 표준 구성 요소가 되었다: Redis는 이를 데이터 타입으로 제공하며, 2013년 Google 논문의 개선 사항이 이를 프로덕션 시스템에서 규모 있게 사용할 수 있게 만든 것이다. 이 스케치의 논리 — 데이터가 아닌 증거의 작은 기록을 유지하는 것 — 는 이후 MinHash와 Count-Min Sketch 같은 구조의 토대도 된다.