기본 개념
카운팅 블룸 필터는 요소 시퀀스가 주어졌을 때 주어진 요소의 카운트 수가 주어진 임계값보다 작은지 여부를 테스트하기 위해 구현되는 블룸 필터의 일반화된 데이터 구조로 정의됩니다. 일반화된 형태로 블룸 필터의 경우 위양성 일치 가능성이 있지만 위음성 가능성은 없습니다. 즉, 쿼리가 "임계값보다 높거나 같음" 또는 "임계값보다 확실히 작음"을 반환합니다.
알고리즘 설명
- 블룸 필터를 카운팅하는 데 사용되는 대부분의 매개변수는 n, k와 같이 블룸 필터와 동일하게 정의됩니다. m은 Counting Bloom 필터의 카운터 수로 표시되며, 이는 Bloom 필터의 m 비트 확장입니다.
- 빈 카운팅 블룸 필터는 m 카운터로 설정되며 모두 0으로 초기화됩니다.
- 블룸 필터와 유사하게 k개의 다양한 해시 함수가 정의되어 있어야 하며, 각 해시 함수는 m개의 카운터 배열 위치 중 하나로 일부 세트 요소를 매핑하거나 해시하여 균일한 무작위 분포를 생성합니다. 또한 k는 추가할 요소의 수에 비례하는 m보다 훨씬 작은 상수입니다.
- 블룸 필터의 주요 일반화는 요소를 추가하는 것입니다. 요소를 추가하려면 k개의 해시 함수 각각에 요소를 삽입하여 k개의 배열 위치를 얻고 이 모든 위치에서 카운터를 1 증가시킵니다.
- 임계값이 θ인 요소를 쿼리하려면(요소의 개수가 θ보다 작은지 확인) k개의 해시 함수 각각에 삽입하여 k개의 카운터 위치를 얻습니다.
- 이 위치에 있는 카운터 중 하나가 θ보다 작은 경우 요소의 개수는 θ보다 확실히 작습니다. 더 높고 같으면 해당하는 모든 카운터는 θ보다 높거나 같았을 것입니다.
- 모두 θ보다 높거나 같으면 개수가 실제로 θ보다 높거나 같거나 카운터가 우연히 θ보다 높거나 같은 것입니다.
- 카운트가 θ보다 작더라도 모두 θ보다 크거나 같으면 이 상황을 가양성(false positive)으로 정의합니다. Bloom 필터와 마찬가지로 이것도 최소화해야 합니다.