Flajolet-Martin Algorithm

Counting Distinct Elements

 

Flajolet-Martin 알고리즘은 distinct data를 세는 알고리즘입니다. 이 알고리즘은 서로 다른 데이터들을 특정한 해시 함수를 이용하여 해싱한 후 그 결과를 저장하기 위해 해쉬테이블을 메모리 상에 유지하면 됩니다. 하지만 해시테이블이 너무 커서 메모리 상에 유지할 수 없다면 메모리를 절약하기 위해 서로 다른 원소들의 개수를 그저 추정해야하는데, 이 때 Flajolet-Martin 알고리즘을 사용합니다.

 

Application

 

Flajolet-Martin 알고리즘은 다음과 같은 상황에 적용할 수 있습니다.

 

- How many different words are found among the Web pages being crawled at a site ?

- How many different Web pages does each customer request in a week?

- How many distinct products have we sold in the last week?

 

 

Flajolet-Maritn Algorithm

 

Flajolet-Martin 알고리즘의 과정은 다음과 같습니다.

 

1) uniform distribution을 가진 해시함수를 선택하고, 해시함수를 통해 들어오는 N개의 데이터들을 logN bits로 변경합니다.

2) 비트로 변경된 데이터들의 Tail length를 구하고, maximum tatil length인 R을 계속해서 업데이트합니다.

3) distinct element는 2^R개로 추정합니다.

 

 

* Tail length

 

여기서 Tail length는 간단히 말해서 데이터를 해싱하여 나온 값을 binary한 값으로 변경한 후, 오른쪽에서 훑어가며 첫번째 1이 나올 때까지의 0의 개수를 세면 됩니다. 간단히 에를 들어 설명해 보겠습니다

 

H(a) = 12 라면 12는 1100(2)으로 표현할 수 있습니다. 그렇다면 오른쪽에서부터 1이 나올 때까지의 0의 개수는 2이므로 R(a) = 2가 됩니다.

 

 

Why It Works

 

h(a)가 적어도 r의 0으로 끝날 확률은 2^(-r)이 됩니다. 그렇다면 m개의 서로 다른 원소들 중에서 tail length가 r이 아닐 확률은

1- 2^(-r)이 됩니다. 하지만 각각의 원소들은 독립적인 이벤트이므로  m 승을 해주면 r개의 0으로 끝나지 않을 확률은 (1 - 2^(-r))^m