기본 개념
카운팅 블룸 필터(Counting Bloom Filter)는 기존 블룸 필터(Bloom Filter)를 확장한 일반화된 자료구조로, 일련의 원소들이 주어졌을 때 특정 원소의 출현 횟수가 주어진 임계값(threshold)보다 작은지를 판별하기 위해 사용됩니다.
블룸 필터의 일반화 형태이기 때문에 거짓 양성(false positive), 즉 실제로는 임계값 미만인데도 그 이상으로 판단할 가능성은 존재합니다. 반면 거짓 음성(false negative)은 절대 발생하지 않습니다. 다시 말해, 질의 결과는 항상 "임계값 이상일 가능성이 있다" 또는 "임계값보다 확실히 작다" 둘 중 하나로 반환됩니다.
알고리즘 상세 설명
- 카운팅 블룸 필터에서 사용되는 대부분의 매개변수는 기존 블룸 필터와 동일하게 정의됩니다. 예를 들어 원소의 개수를 나타내는 n, 해시 함수의 개수를 나타내는 k가 그렇습니다. 다만 m은 카운팅 블룸 필터에 포함된 카운터(counter)의 개수를 의미하며, 블룸 필터에서의 m비트 배열을 확장한 개념입니다.
- 빈(empty) 카운팅 블룸 필터는 모두 0으로 초기화된 m개의 카운터로 구성됩니다.
- 블룸 필터와 마찬가지로 k개의 서로 다른 해시 함수가 정의되어야 하며, 각 해시 함수는 집합의 원소를 m개의 카운터 배열 위치 중 하나에 균일한 무작위 분포로 매핑하는 역할을 담당합니다. 또한 k는 상수로서 m보다 훨씬 작아야 하며, m은 추가될 원소의 수에 비례합니다.
- 블룸 필터의 핵심적인 일반화 부분은 원소의 삽입 과정입니다. 원소를 삽입할 때는 해당 원소를 k개의 해시 함수에 각각 입력하여 k개의 배열 위치를 얻고, 그 위치들에 있는 카운터 값을 각각 1씩 증가시킵니다.
- 임계값 θ를 기준으로 원소를 질의할 때(해당 원소의 출현 횟수가 θ보다 작은지 확인), 역시 k개의 해시 함수에 원소를 입력하여 k개의 카운터 위치를 얻습니다.
- 이 위치들 중 하나라도 카운터 값이 θ보다 작다면, 해당 원소의 출현 횟수는 확실하게 θ보다 작습니다. 만약 실제 횟수가 θ 이상이라면, 대응되는 모든 카운터가 θ 이상이었어야 하기 때문입니다.
- 반면 모든 카운터 값이 θ 이상이라면, 두 가지 경우가 있습니다. 실제 출현 횟수가 정말 θ 이상인 경우이거나, 우연히 카운터들이 모두 θ 이상이 된 경우입니다.
- 실제 출현 횟수가 θ 미만인데도 모든 카운터가 θ 이상으로 나타나는 상황을 거짓 양성(false positive)이라고 정의합니다. 기존 블룸 필터와 마찬가지로, 이러한 거짓 양성의 발생 확률은 최소화되어야 합니다.