카운팅 블룸 필터

카운팅 블룸 필터는 블룸 필터의 일반화된 데이터 구조로, 요소의 시퀀스가 주어졌을 때 주어진 요소의 카운트 번호가 주어진 임계값보다 작은지 여부를 테스트하는 데 사용된다.블룸 필터의 일반화된 형태로서 거짓 양성 일치는 가능하지만 거짓 음성 일치는 가능하지 않다. 즉, 쿼리는 "임계값보다 크거나 같거나" 또는 "임계값보다 훨씬 작음"을 반환한다.

알고리즘 설명

n, k. m은 Counting Bloom 필터의 카운터 수, 즉 Bloom 필터의 m 비트의 확장인 Counting Bloom 필터의 카운터 수처럼 대부분의 파라미터는 Bloom 필터에 있는 m 비트의 확장이다.빈 카운팅 블룸 필터는 모두 0으로 설정된 m 카운터다.Bloom 필터와 마찬가지로 k개의 다른 해시함수가 정의되어야 하며, 각각은 일정한 랜덤 분포를 생성하면서 m 카운터 배열 위치 중 하나에 어떤 설정 요소를 매핑하거나 해시한다.또한 k가 m보다 훨씬 작은 상수로 추가될 원소의 수에 비례하는 것도 비슷하다.

블룸 필터의 주 일반화는 요소 추가다.요소를 추가하려면 각 k 해시 함수에 요소를 공급하여 k 배열 위치를 얻고 이 모든 위치에서 카운터 1을 증가시키십시오.

임계값 threshold(원소의 카운트 번호가 θ보다 작은지 여부를 검정)을 가진 요소를 쿼리하려면 k 카운터 위치를 얻기 위해 k 해시 함수에 각각 공급하십시오.이들 위치의 카운터 중 어느 하나라도 any보다 작으면 요소의 카운트 수가 θ보다 확실히 작다. 만일 더 많고 같았더라면, 해당 카운터는 모두 θ보다 크거나 같았을 것이다.모두 θ보다 크거나 같으면, 카운트가 정말로 to보다 크거나 같거나, 카운터가 우연히 greater보다 크거나 같았거나 같다.계수가 θ보다 작아도 모두 θ보다 크거나 같으면 이 상황은 거짓 양성으로 정의된다.이것도 블룸 필터처럼 최소화해야 한다.

해싱 문제와 이점에 대한 자세한 내용은 블룸 필터를 참조하십시오.

카운팅 블룸 필터는 기본적으로 카운트-min 스케치와 동일한 데이터 구조지만 다르게 사용된다.

거짓 부정의 가능성

블룸 필터 계산의 여러 구현은 특정 입력에 대한 각 k 카운터를 감소시킴으로써 삭제를 허용한다.이렇게 하면 삭제된 입력이 이전에 필터에 삽입되지 않은 경우 쿼리 중에 잘못된 음의 확률이 소개된다.Gou 등에서는 문제를 매우 상세하게 제시하고, 잘못된 부정의 확률을 최소화하는 매개변수 m, k, n에 대해 휴리스틱스를 제공한다.^[1]

잘못된 긍정의 확률

해시함수가 삽입을 균일한 랜덤으로 만드는 블룸 필터의 동일한 가정도 여기서 가정한다.m 솥에는 kn ball이 임의로 삽입된다.Counting Bloom filter counting l의 카운터 중 하나의 확률은

${\$$={kn \선택 l}({\frac {1}{m})^{l}(1-{\frac${1$}{m})^{kn-l$

여기서 b는 이항 분포다.^[2]그런데 Counting Bloom 필터는 해당 k 카운터가 or보다 크거나 같을 때 요소가 or보다 크거나 같음을 결정한다.따라서 Counting Bloom 필터가 요소가 determines보다 크거나 같을 확률은

${\$$^{k}}$.

이는 Counting Bloom 필터에서 거짓 양성이라는 공식적 정의와는 다르다.그러나 Bloom 필터의 가정에 따라, 이상의 확률은 Counting Bloom 필터의 거짓 양성으로 정의된다.θ=1일 경우 이 방정식은 블룸 필터의 거짓 양성이 된다.

최적의 해시함수 수

크지만 고정된 n과 m의 경우 거짓 양수는 k=1에서 정의된 $k{\displaystyle {}_{}}$ ${\displaystyle o_{}}$ p t ${\$ 그리고 $k{\displaystyle {}_{}}$$$${\displaystyle o_{}}$ p ${\displaystyle t_{}}$ ${\$에서 양의$$ 무한대로 증가한다.^[3]

Kim et al. (2019) shows numerical values of ${\displaystyle k_{opt}}$within ${\displaystyle 1\leq \theta \leq 30}$. If θ is bigger than 30, they suggested to use ${\displaystyle k_{opt}=\lfloor {\frac {m}{n}}(0.2037\theta +0.9176)\rfloor }$or ${\displaystyle k_{opt}=}$${\displaystyle \lceil m\frac{}{}}$ ${\displaystyle \frac{n}{}}$(${\displaystyle 0.2037}$ ${\displaystyle \theta }$+ 0${\displaystyle .9176}$) ${\displaystyle \rceil }$ ${\displaystyle k_{opt}=\lceil {\frac {m}{n}}}(0.2037\theta +0.9176)\rceil$ $\}\}.$

참조