확률적 자료구조를 이용한 추측 - hyperloglog

자세한 내용은 네이버 개발자 센터에 있다. : http://d2.naver.com/helloworld/711301

요약.

유니크한 값이 어떤 자료구조 안에 있는지 정확하게 판단하려면 해쉬 셋 등을 만들어 모든 값을 넣어두고, 값을 가져와서 비교한 후 판단할수 있다. 하지만 이러한 방법은 메모리가 엄청 많이 먹게 된다.(모든 자료를 저장해야하므로)

정확한 값을 얻는데 드는 비용이 너무 크다면 비용을 월등하게 줄이는 대신 오차가 조금 있는 방법이 더 유용할 수도 있다. 이게 hyperloglog이다.

위 네이버 링크에 셰익스피어 작품에 나오는 유니크한 단어 수를 셀때, 자바의 hash set과 hyperloglog를 사용할때의 비교이다. (출처 위의 네이버 개발자 도구. 문제있을시 삭제하겠습니다.)

hyperloglog를 사용하면 사용 메모리가 월등하게 줄어드는데 그에 비해 오차는 겨우 3퍼센트 증가한다. 

hyperloglog의 아이디어는 상위 비트에 대한 확률접인 접근으로 시작한다고 한다. 첫번째 비트가 0이나 1일경우 표현할 수 있는 모든 수의 50%를 차지한다. 마찬가지로 00,01,10,11일 경우 각각 모든 수의 25%씩을 차지한다. hyperloglog에서는 이러한 로직에 따라 레지스터의 갯수가 결정된다.

더 자세한 것은 원본 링크를 보자 어려움....