Flajolet-Martin Algorithm

Flajolet-Martin Algorithm은 Stream Data에서 서로 다른 데이터의 개수를 세는 알고리즘(Counting Distinct Element) 이다. 이는 Stream Data에서 다음과 같은 질의들에 응답하는데 사용된다 .

 

- How many different words are found among the web pages 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?

 

이 질의들에 응답하기 위한 가장 명백한 방법 (Obvious Solution)은 N개의 데이터들을 특정한 해시 함수를 사용하여 해싱하고, 해시된 결과를 저장하는 해시테이블을 메모리 상에 유지하면 된다.

 

그러나 앞선 여러 알고리즘들의 등장배경과 마찬가지로 만약, 해시테이블의 크기가 너무 커서 이를 메모리 상에 유지하는 것이 어렵다면?

메모리를 절약하기 위해 정확한 갯수를 측정하는 것을 포기하고 근사적으로 서로 다른 원소들의 개수를 추정(Estimate)하는 것이 필요할 것이다. 이를 위해 사용되는 알고리즘이 바로 Flajolet-Martin Algorithm이다.

 

 

Flajolet-Martin Algorithm

알고리즘의 핵심은 해시함수를 통해 들어오는 데이터들을 비트의 집합으로 바꾸고, Least zero bit index R을 구하는 것이다. R을 구한 다음에는 그냥 2^R/(pi*bias)를 통해 # of distinct items를 구하면 된다. (통상적으로 pi*bias = 0.77351의 상수로 정의한다.)

개념 자체가 설명만 들어서는 잘 이해가 가지 않는 내용이니 간단한 예를 통해서 살펴보도록 하겠다. 

 

 

Hash function (3개)

1.  h1(𝑥) = least zero bit index of ((9𝑥 + 7) mod 32)

2.  h2(𝑥) = least zero bit index of ((5𝑥 + 11) mod 32)

3.  h3(𝑥) = least zero bit index of ((3𝑥 + 13) mod 32)

 

예를 들어 Stream에 데이터가 10개가 들어왔다고 하자 {1, 7, 9, 5, 10, 9, 22, 29, 12, 17}

Flajolet-Martin Algorithm을 통해 예측을 해보도록 하겠다. 해쉬 함수가 32로 모듈러 연산을 하기 때문에 비트수는 5개가 된다.

 

먼저 해쉬 함수를 통해 각각의 데이터들을 비트로 표현해보면 

h1(x) 의 경우 데이터 순서대로 다음과 같다.

 

1 -> 10000
7 -> 00110

9 -> 10110

5 -> 00001

10 -> 11000

22 -> 01001

29 -> 01100

12 -> 10011

17 -> 00000

 

이제 여기서 Least Zero Bit을 구하는 과정이 설명만 들어서는 좀 헷갈릴 수 있는데,  오른쪽부터 0이 처음 나타나는 인덱스중의 최댓값을 R로 설정하면 된다. 위의 예에서 0이 처음 나타나는 인덱스를 구하면 각각 0, 0, 0, 1, 0, 1, 0, 2, 0이 되고 이 인덱스의 비트 값을 1로 설정하게 되면 000111 이 된다. 이 경우에 least zero bit R = 3이 된다. (오른쪽에서부터 처음으로 3이 나오는 인덱스 0부터 시작!)

이 경우 R = 3이 되는 것이다. 

 

따라서 Flajolet-Martin Algorithm을 적용하면 8/0.77351 의 서로 다른 원소의 개수가 나오게 된다.

물론 정확도를 높이기 위해서는 여러 개의 해쉬 함수를 사용하여 그것들의 평균을 내면 된다. (R의 평균을 의미하는 것, 위의 3개의 함수를 모두 이용하면 R의 평균이 (2+3+4)/3 = 3이 되어 대략 10개의 서로 다른 원소의 개수가 나온다.)

 

중요한 점은, R을 구하기 위해 해싱을 하는데 이때 사용하는 해쉬 함수는 Uniform Distribution을 가져야 한다. 왜냐하면 데이터가 편향되지 않게 추출되어야 Least Zero Bit Index로부터 서로 다른 원소의 개수를 예측할 수 있기 때문이다.

 

 

Storage Requirement

N개의 데이터가 주어졌을 때, 이를 예측하기 위해서 이를 이진법으로 표현한 비트수만 있으면 되기 때문에, 필요한 공간복잡도는 O(logN)이 된다.