HyperLogLog

HyperLogLog는 2007년에 발표된 알고리즘이며 Loglog Counting 알고리즘을 발전시켜 개발하였기 때문에 Hyper 접두사를 붙혔다. hyperloglog는 매우 큰 데이터의 오차가 1% 이하의 근사치를 구할 때 사용한다. 메모리를 적게 사용하고 오차가 적은것이 특징이다.

hyperloglog는 원소 개수와 상관없이 고정으로 12kb만 사용하기 때문에 메모리 사용률이 낮다.

hyperloglog의 오차는 1.04 / SQRT(m)이다. m은 register의 개수로 Redis에서는 16384개를 사용하므로 오차는 0.81%이다.

hyperloglog의 저장 속도는 set에 비해 데이터 1백만개 기준 약 1.6배 빠른 특징이 있다.

hyperloglog의 조회 속도는 O(1)이다.

Command

hyperloglog의 명령은 개발자 Philippe Flajolet를 기리기 위해 PF로 시작한다

• PFADD [key] [value]
• PFCOUNT [key]
• PFMERGE [store key] [key1] [key2]

참조

http://redisgate.kr/download/FlFuGaMe07.pdf
https://d2.naver.com/helloworld/711301