http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation

HyperLogLog 라고 하는 알고리즘. 셋이 주어지면 아이템들의 해시값을 구한 뒤 해시값의 맨 앞에서 연속적으로 나타난 0의 최대 갯수를 세고, 이로부터 전체 unique 데이터 갯수를 알아냅니다.

예를들어 해시함수의 출력이 m자리 이진수라고 해보죠. n개 수를 해싱했더니 나온 n개 해시값들중에서 연속된 0이 가장 길게 나온경우는 세자리였다고 해보겠습니다. 연속적으로 0이 3자리 나오는건 약 2^3개의 엘리먼트를 볼때마다이므로 unique item 수를 약 8로 추정합니다. 이 알고리즘의 나머지 부분은 이 정확도를 더 개선시키기위해 더 많은 해시함수를 작용하는 등의 최적화입니다.

정확도는 1 billion 갯수에대해 약 2% 정도의 오차가 있는 정도로 준수하다고 합니다.

Flajolet Martine Algorirhm이라고 해시값의 끝에 몇개의 연속된 0이 나오는지 세서 그 0의 수가 R이면 2^R로 unique item수를 측정할수도 있습니다.

해시값에 영향을 많이 받기때문에 다수의 해시함수를 구하고, 이들을 그룹으로 묶어 각 그룹내에서 측정한 값의 평균을 내놓고, 그 평균들의 median을 구하기도 합니다. (자세한건 mining massive datasets라는 책 참고하세요)

물론 이외에도 bloom filter등을 쓰는 방법도 있겠습니다. 아이템이 주어지면 bloom filter를 사용해 이미 셋에 있는지보고 이미 있다면 패스. 없다면 필터에 추가. 이를 반복하면 됩니다.