대량의 데이터에서 대략적으로 unique item 의 수 세기

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를 사용해 이미 셋에 있는지보고 이미 있다면 패스. 없다면 필터에 추가. 이를 반복하면 됩니다.

Similar Posts:

Comments 2

  1. 염재현 wrote:

    재미있는 글 잘 읽었습니다. 위에 n은 약 8로 추정합니다에서 n을 unique한 n으로 바꿔야 말이 되겠네요. 아 그리고 글 전체에 unique 라는 말이 빠졌어요. 제목에는 있는데…

    Posted 22 Dec 2012 at 4:26 pm
  2. mkseo wrote:

    감사합니다. 수정했어요~

    Posted 23 Jan 2013 at 10:30 am

Post a Comment

Your email is never published nor shared.