블룸필터

시리즈의 일부(on)
확률론적 자료 구조
블룸필터 카운트-민 스케치 몫필터 목록 건너뛰기
랜덤 트리
랜덤 이진 트리 트랩 랜덤 트리를 빠르게 탐색
관련된
랜덤화 알고리즘 HyperLogLog
v t

Bloom 필터는 1970년 Burton Howard Bloom이 고안한 공간 효율적인 확률형 데이터 구조로, 요소가 집합의 멤버인지 여부를 테스트하는 데 사용됩니다.거짓 양의 일치는 가능하지만 거짓 음의 일치는 가능하지 않습니다. 즉, 쿼리는 "가능한 집합" 또는 "분명히 집합이 아닙니다"를 반환합니다.요소를 세트에 추가할 수는 있지만 제거할 수는 없습니다(이는 계수 블룸 필터 변형을 사용하여 해결할 수 있지만). 항목이 더 많이 추가될수록 위양성이 발생할 가능성이 커집니다.

높은 수준의 아이디어는 원소 x≥X를 y=h(x) 값에 매핑하는 것입니다.해시 함수 h를 사용하여 Y를 Y로 한 다음, y'=h(x')∈Y를 확인하여 X에서 x'의 멤버쉽을 테스트하고, 여러 개의 해시 함수 h를 사용하여 이를 수행합니다.

Bloom은 "기존의" 무오류 해싱 기술을 적용할 경우 소스 데이터의 양이 비현실적으로 많은 양의 메모리를 필요로 하는 애플리케이션을 위한 기술을 제안했습니다.그는 500,000개의 단어로 구성된 사전에 대한 하이픈 알고리즘을 예로 들어 설명했는데, 이 중 90%는 간단한 하이픈 규칙을 따르지만, 나머지 10%는 특정 하이픈 패턴을 검색하려면 값비싼 디스크 액세스가 필요합니다.코어 메모리가 충분하면 오류가 없는 해시를 사용하여 불필요한 디스크 액세스를 모두 제거할 수 있습니다. 반면 제한된 코어 메모리를 사용하면 Bloom의 기술은 더 작은 해시 면적을 사용하지만 여전히 대부분의 불필요한 액세스를 제거합니다.예를 들어, 이상적인 무오류 해시에 필요한 크기의 15%만 해시 영역을 사용해도 디스크 ^[1]액세스의 85%가 제거됩니다.

일반적으로 집합 ^[2]내 요소의 크기나 개수에 관계없이 1%의 위양성 확률에 대해 요소당 10비트 미만이 필요합니다.

알고리즘 설명

빈 Bloom 필터는 m비트의 비트 배열로, 모두 0으로 설정됩니다.또한 정의된 다른 해시 함수가 있어야 하며, 각 해시 함수는 m개의 배열 위치 중 하나에 일부 집합 요소를 매핑하거나 해시하여 균일한 랜덤 분포를 생성합니다.일반적으로 k는 원하는 거짓 오류율 δ에 의존하는 작은 상수인 반면 m은 k와 추가할 원소의 수에 비례합니다.

요소를 추가하려면 k개의 배열 위치를 얻기 위해 각 k개의 해시 함수에 요소를 공급합니다.이 모든 위치의 비트를 1로 설정합니다.

요소를 쿼리하려면(집합에 있는지 여부를 검정) k개의 해시 함수 각각에 요소를 공급하여 k개의 배열 위치를 가져옵니다.이 위치에 있는 비트 중 하나가 0이면 요소가 집합에 없는 것이 분명합니다. 만약 그렇다면 삽입할 때 모든 비트가 1로 설정되었을 것입니다.모두 1이면 요소가 집합에 있거나 다른 요소를 삽입하는 동안 비트가 우연히 1로 설정되어 오탐이 발생했습니다.단순 Bloom 필터에서는 두 경우를 구분할 수 있는 방법이 없지만, 보다 발전된 기술로 이 문제를 해결할 수 있습니다.

k개의 서로 다른 독립적인 해시 함수를 설계해야 하는 요구 사항은 큰 k에 대해 금지될 수 있습니다.출력이 넓은 양호한 해시 함수의 경우, 이러한 해시의 서로 다른 비트 필드 간에 상관 관계가 거의 없어야 합니다. 따라서 이러한 유형의 해시는 출력을 여러 비트 필드로 슬라이싱하여 여러 "서로 다른" 해시 함수를 생성하는 데 사용될 수 있습니다.또는 초기 값을 취하는 해시 함수에 다른 초기 값(예: 0, 1, ..., k - 1)을 전달하거나 이러한 값을 키에 추가(또는 추가)할 수 있습니다.큰 mand/ork의 경우, 해시 함수들 간의 독립성은 거짓 양성 ^[3]비율을 무시할 정도로 증가시킴으로써 완화될 수 있습니다.(구체적으로, Dillinger & Manolios (2004b)는 향상된 이중 해싱과 삼중 해싱을 사용하여 k 지수를 도출하는 효과를 보여주는데, 이중 해싱의 변형은 2개 또는 3개의 해싱 값으로 시드된 효과적인 단순 난수 생성기입니다.)

이 단순 Bloom 필터에서 요소를 제거하는 것은 불가능합니다. k비트 중 어떤 것을 삭제해야 하는지 알 수 있는 방법이 없기 때문입니다.k비트 중 하나를 0으로 설정하면 요소를 제거할 수 있지만 해당 비트에 매핑되는 다른 요소도 제거할 수 있습니다.단순한 알고리즘은 제거할 요소의 비트에 영향을 미치는 다른 요소가 추가되었는지 여부를 확인할 수 있는 방법을 제공하지 않으므로 비트 중 하나를 지우면 거짓 음성이 발생할 가능성이 있습니다.

Bloom 필터에서 요소를 한 번 제거하면 제거된 항목이 들어 있는 두 번째 Bloom 필터를 사용하여 시뮬레이션할 수 있습니다.그러나 두 번째 필터의 위양성은 복합 필터의 위음성이 되므로 바람직하지 않을 수 있습니다.이 방법에서는 이전에 제거된 항목을 "제거된" 필터에서 제거해야 하므로 다시 추가할 수 없습니다.

모든 키를 사용할 수 있지만 열거하기에는 비용이 많이 드는 경우가 많습니다(예: 많은 디스크 읽기가 필요함).위양성률이 너무 높아지면 필터가 재생성될 수 있으므로 비교적 드문 이벤트일 수 있습니다.

공간 및 시간상의 이점

Bloom 필터는 잘못된 긍정을 위험에 빠뜨릴 수 있지만 이진 검색 트리, 시도, 해시 테이블 또는 단순 배열 또는 연결된 항목 목록과 같은 집합을 표현하기 위한 다른 데이터 구조에 비해 상당한 공간 이점을 가집니다.대부분의 경우 데이터 항목 자체를 저장해야 하는데, 이는 작은 정수의 경우 작은 비트부터 문자열의 경우와 같은 임의 수의 비트까지 필요합니다(접두사가 동일한 요소 간에 저장을 공유할 수 있으므로 시도는 예외입니다).그러나 Bloom 필터는 데이터 항목을 전혀 저장하지 않으며, 실제 저장을 위해 별도의 솔루션을 제공해야 합니다.연결된 구조는 포인터에 대한 추가 선형 공간 오버헤드를 발생시킵니다.반면 오차가 1%이고 최적 값이 k인 Bloom 필터는 요소의 크기에 관계없이 요소당 약 9.6비트만 필요합니다.이러한 장점은 어레이에서 물려받은 컴팩트함과 확률적 특성에서 일부 기인합니다.1% 위양성률은 요소당 약 4.8비트만 추가하면 10배까지 감소할 수 있습니다.

그러나 잠재적 값의 수가 적고 많은 값이 집합에 포함될 수 있는 경우 Bloom 필터는 각 잠재적 요소에 대해 한 비트만 필요한 결정론적 비트 배열에 의해 쉽게 능가됩니다.해시 테이블이 충돌을 무시하기 시작하고 각 버킷에 항목이 포함되어 있는지 여부만 저장하면 공간과 시간적 이점을 얻을 수 있습니다. 이 경우 = 1의 Bloom 필터가 됩니다.

블룸 필터에는 항목을 추가하거나 항목이 집합에 있는지 확인하는 데 필요한 시간이 고정 상수인 O()k라는 특이한 속성이 있으며, 이는 집합에 있는 항목의 수와 완전히 무관합니다.다른 상수 공간 집합 데이터 구조에는 이 속성이 없지만 스파스 해시 테이블의 평균 액세스 시간은 일부 Bloom 필터보다 실제로 더 빠르게 만들 수 있습니다.그러나 하드웨어 구현에서 Bloom 필터는 k 룩업이 독립적이고 병렬화될 수 있기 때문에 빛을 발합니다.

공간 효율을 이해하려면 일반 블룸 필터를 = 1일 때 특수한 경우와 비교하는 것이 좋습니다. = 1이면 위양성률을 충분히 낮게 유지하려면 작은 비트수를 설정해야 하는데, 이는 배열이 매우 크고 0의 긴 실행을 포함해야 함을 의미합니다.배열의 크기에 대한 정보 내용이 낮습니다.일반화된 Bloom 필터(1보다 큰 k)를 사용하면 여전히 낮은 오탐률을 유지하면서 더 많은 비트를 설정할 수 있습니다. 매개 변수(k 및 m)를 잘 선택하면 비트의 절반 정도가 ^[5]설정되며, 이는 명백하게 무작위이므로 중복성을 최소화하고 정보 내용을 최대화할 수 있습니다.

위양성 확률

해시 함수가 동일한 확률로 각 배열 위치를 선택한다고 가정합니다.m이 배열의 비트 수이라면 요소를 삽입하는 동안 특정 비트가 특정 해시 함수에 의해 1로 설정되지 않을 확률은 다음과 같습니다.

${\displaystyle 1-{\frac {1}{m}}}$

k가 해시 함수의 개수이고 각각이 서로 간에 유의한 상관관계가 없다면, 비트가 해시 함수에 의해 1로 설정되지 않을 확률은 다음과 같습니다.

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}}$

우리는 잘 알려진 정체성을⁻¹ 사용할 수 있습니다.

${\displaystyle \lim _{m\to \infty}\left(1-{\frac {1}{m}}\right)^{m}={\frac {1}{e}}$

결론을 내리자면, 큰 m의 경우,

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m}\right)^{k/m}\message e^{-k/m}}$

만약 우리가 n개의 요소를 삽입했다면, 어떤 비트가 여전히 0일 확률은

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}\message e^{-kn/m};}$

그러므로 그것이 1일 확률은

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}\message 1-e^{-kn/m}}$

이제 집합에 없는 요소의 멤버쉽을 테스트합니다.해시 함수에 의해 계산된 각각의 k 배열 위치는 위와 같은 확률로 1입니다.알고리즘이 요소가 집합 안에 있다고 잘못 주장하는 것을 야기할 수 있는 그들 모두가 1일 확률은 종종 다음과 같이 주어집니다.

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\right \left(1-e^{-kn/m}\right)^{k}}$

이는 설정되는 각 비트의 확률에 대한 독립성을 가정하기 때문에 엄밀하게 정확하지 않습니다.그러나 근접 근사치라고 가정하면 m(배열의 비트 수)이 증가하면 위양성 확률이 감소하고 n(삽입 요소 수)이 증가하면 증가합니다.

독립성을 가정하지 않고 거짓 양성일 확률은

${\displaystyle {\frac {1}{m^{k(n+1)}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{kn \time i}\right\}}$

여기서 {braces}는 두 ^[6]번째 종류의 스털링 수를 나타냅니다.

독립성의 가정 없이 동일한 근사치에 도달하는 대안적 분석은 Mitzenmacher와 Upfal에 의해 ^[7]제공됩니다.Bloom 필터에 n개의 항목을 모두 추가한 후, 0으로 설정된 m비트의 비율을 q라고 합니다. (즉, 여전히 0으로 설정된 비트 수는 qm입니다.)그 다음, k개의 해시 함수가 주어진 배열 위치에 대하여 집합이 아닌 원소의 멤버쉽을 시험할 때, 비트가 1로 설정되어 있을 확률은 $1{\displaystyle \mathrm{}}$-$$ {\$displaystyle 1-q$입니다. 따라서 모든 k개의 해시 함수가 비트가 1로 설정되어 있을 확률은 $({\displaystyle 1}$ ${\displaystyle -{}^{}}$q) ${\displaystyle k^{}}${\$displaystyle ($1 - q$)^{k$입니다. 또한 q의 기대값은 t입니다.주어진 배열 위치가 각 n개의 항목에 대한 k개의 해시 함수에 의해 손상되지 않은 채로 남겨질 확률은 다음과 같습니다.

$=$$^{kn$

독립성 가정 없이 q가 기대 값 주위에 매우 강하게 집중되어 있음을 증명할 수 있습니다.특히 아즈마 강에서..불평등을 해소하면서, 그들은 다음을 증명합니다^[8].

${\displaystyle \Pr(\left q-E[q]\right \geq {\frac {\lambda}{m}})\leq 2\exp(-2\lambda^{2}/kn)}$

이 때문에, 우리는 정확한 위양성의 확률은

${\displaystyle \sum _{t}\Pr(q=t)(1-t)^{k}\prox (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\right \left(1-e^{-kn/m}\right)^{k}$

종전과 같이

최적 해시 함수 수

해시 함수의 수 k는 양의 정수여야 합니다.이 제약 조건을 제쳐두고, 주어진 m과 n에 대하여, 거짓 양의 확률을 최소화하는 k의 값은

${\displaystyle k={\frac {m}{n}}\ln 2.}$

n(삽입 요소의 수)이 주어지고 원하는 거짓 양의 확률 δ(그리고 최적 k 값이 사용된다고 가정)가 주어지면 위의 확률식에서 최적 k 값을 대입하여 필요한 비트 수 m을 계산할 수 있습니다.

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}}\right)^{\frac {m}{n}\ln 2}}$

다음과 같이 단순화할 수 있습니다.

${\displaystyle \ln \varepsilon =-{\frac {m}{n}}\left(\ln 2\right)^{2}}$

결과는 다음과 같습니다.

${\displaystyle m=-{\frac {n\ln \varepsilon}{(\ln 2)^{2}}}}$

따라서 요소당 최적 비트 수는

${\displaystyle {\frac {m}{n}}=-{\frac {\log _{2}\varepsilon}{\ln 2}}\non -1.44\log _{2}\varepsilon}$

대응하는 개수의 해시 함수 k(해시 적분):

${\displaystyle k=-{\frac {\ln \varepsilon}{\ln 2}}=-\log _{2}\varepsilon.}$

이것은 주어진 거짓 양의 확률 ε에 대해 Bloom 필터 m의 길이는 필터링되는 요소의 수 n에 비례하고 필요한 해시 함수의 수는 목표 거짓 양의 확률 ε에만 의존한다는 것을 의미합니다.

$공식$ m = - ${\displaystyle n}$ ${\displaystyle \frac{\ln }{}}$ ⁡${\displaystyle \frac{}{}}$ε ( ${\displaystyle \frac{\ln }{}}$ ⁡ ${\displaystyle \frac{2^{}}{}}$) 2 {\$displaystyle$ m=-{\$frac {n\ln \varepsilon}}{(\ln$ 2$)^{2}}}}$는 세 가지 이유로 근사치입니다.첫째, 우려할 만한 점은 1${\displaystyle }$- ${\displaystyle 1^{}}$ ${\displaystyle m}${\$displaystyle 1-{\frac {1}{m}}}$를${\displaystyle {}^{}}$e - 1 ${\displaystyle {\frac{m}{}}^{}}${\$displaystyle$ e$^{-{\frac {1}{m$로 $근사한다는$ 점이며, 이는 좋은 점근적 근사치(즉, m →∞)입니다.둘째, 더 우려되는 것은 멤버십 테스트 중에 하나의 테스트된 비트가 1로 설정된 이벤트는 다른 테스트된 비트가 1로 설정된 이벤트와는 무관하다고 가정합니다.셋째, 가장 우려되는 것은 k = ${\displaystyle \mathrm{mln}}$≥$$2 {\$displaystyle$ k = ${\frac {m}{$n}}\$ln$ 2$}$이(가) 우연하게도 일체라고 $가정$합니다.

그러나 Goel과 ^[10]Gupta는 근사치를 내지 않고 가정을 요구하지 않는 엄격한 상한을 제공합니다.m비트(> ${\displaystyle$m >$1$}), n개의 요소 및 k개의 해시 함수를 가진 유한 Bloom 필터에 대한 위양성 확률이 최대임을 보여줍니다.

${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5))}{m-1}}\right)^{k}}}: {e^{k}}$

이 바운드는 근사식 $({\displaystyle {1\mathrm{}}^{}}$ ${\displaystyle {-{}^{}}^{}}$ - ${\displaystyle {{\frac{}{}}^{}}^{}}$ m${\displaystyle {{)}^{}}^{}}$ ${\displaystyle {}^{}}${\$displaystyle \left(1$ - e$^{\frac {kn}}}\right)$를 의미하는 것으로 해석할 수 있습니다.$^{k$$}}$은(는) 최대 추가 요소의 반, 최대 한 비트 적은 양의 패널티로 적용할 수 있습니다.

Bloom 필터에서 항목 수 근사화

Swamidass & Baldi(2007)는 Bloom 필터의 항목 수가 다음 공식으로 근사될 수 있음을 보여주었습니다.

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

어디에${\displaystyle n^{*}}$필터의 항목 수에 대한 추정치입니다.m필터의 길이(크기)입니다.k는 해시 함수의 수이며,X는 1로 설정된 비트 수입니다.

집합들의 결합과 교집합

블룸 필터는 항목 집합을 압축적으로 표현하는 방법입니다.두 집합 사이의 교집합 또는 결합의 크기를 계산하는 것이 일반적입니다.블룸 필터를 사용하여 교차점의 크기와 두 세트의 결합을 근사화할 수 있습니다.Swamidass & Baldi(2007)는 길이 m의 Bloom 필터 2개의 경우, 그 수는 각각 다음과 같이 추정될 수 있음을 보여주었습니다.

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {A}{m}}\right]}$

그리고.

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {B}{m}}\right].}$

그들의 조합의 규모는 다음과 같이 추정될 수 있습니다.

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {A\cup B}{m}\right],}$

$여기$서${\displaystyle }$n (${\displaystyle A}$ ∪ ${\displaystyle B}$ )$${\$displaystyle$ n$(A\cup$ B$)}$은 두 Bloom 필터 중 하나에서 하나로 설정된 비트 수입니다.마지막으로 교차점은 다음과 같이 추정할 수 있습니다.

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),}$

세 가지 공식을 함께 사용합니다.

흥미로운 속성

• 충돌 해결을 위해 열린 주소 지정을 사용하는 표준 해시 테이블과 달리 고정된 크기의 Bloom 필터는 임의로 많은 수의 요소를 가진 집합을 나타낼 수 있습니다. 요소를 추가하는 것은 데이터 구조 "채움"으로 인해 실패하지 않습니다.그러나 false positive rate는 필터의 모든 비트가 1로 설정될 때까지 요소가 추가됨에 따라 지속적으로 증가하며, 이때 모든 쿼리에서 양의 결과가 나타납니다.오픈 어드레싱 해싱을 사용하면 절대 오탐이 발생하지 않지만 선형 검색에 접근할 때까지 성능이 지속적으로 저하됩니다.
• 동일한 크기와 해시 함수 집합을 갖는 Bloom 필터의 결합과 교차는 각각 비트 와이즈 OR 및 AND 연산으로 구현할 수 있습니다.Bloom 필터의 Union 작업은 결과적인 Bloom 필터가 두 세트의 Union을 사용하여 처음부터 생성된 Bloom 필터와 동일하다는 점에서 무손실입니다.교차 연산은 더 약한 속성을 만족합니다. 결과 Bloom 필터의 위양성 확률은 구성 Bloom 필터 중 하나에서 최대 위양성 확률이지만 두 집합의 교차를 사용하여 처음부터 생성된 Bloom 필터의 위양성 확률보다 클 수 있습니다.
• 어떤 종류의 중첩된 코드는 물리적 에지 노치 카드로 구현된 블룸 필터로 볼 수 있습니다.예를 들어 1947년 캘빈 무어스가 발명한 자토코딩이 있습니다. 하나의 정보와 관련된 카테고리들의 집합은 카드의 노치들로 표현되며, 각 카테고리에 대해 4개의 노치들로 무작위 패턴을 갖습니다.

예

• 초파리는 냄새의 신기함을 감지하기 위해 블룸 필터의 변형된 버전을 사용합니다. 이전에 경험한 예와 유사한 새로운 냄새, 동일한 ^[11]냄새를 경험한 후 경과된 시간 등의 추가적인 특징이 있습니다.
• 컨텐츠 제공 업체인 Akamai Technologies의 서버는 Bloom 필터를 사용하여 디스크 캐시에 "원 히트 원더"가 저장되는 것을 방지합니다.One-hit-wonder는 사용자가 요청한 웹 개체로, Akamai는 이를 캐싱 인프라의 거의 3/4에 적용했다고 밝혔습니다.Bloom 필터를 사용하여 웹 개체에 대한 두 번째 요청을 감지하고 두 번째 요청에서만 해당 개체를 캐싱하면 디스크 캐시에 원히트 원더가 들어오는 것을 방지하여 디스크 작업량을 크게 줄이고 디스크 캐시 적중률을 ^[12]높일 수 있습니다.
• Google Bigtable, Apache HBase 및 Apache Cassandra 및 PostgreSQL에서는 Bloom 필터를 사용하여 존재하지 않는 행 또는 열에 대한 디스크 조회를 줄입니다^[13].비용이 많이 드는 디스크 조회를 방지하면 데이터베이스 쿼리 작업의 ^[14]성능이 크게 향상됩니다.
• 구글 크롬 웹 브라우저는 이전에 Bloom 필터를 사용하여 악성 URL을 식별했습니다.모든 URL을 로컬 Bloom 필터에 대해 먼저 확인하고 Bloom 필터가 긍정적인 결과를 반환하는 경우에만 수행된 URL의 전체 확인을 수행했습니다(또한 긍정적인 ^[15][16]결과를 반환하는 경우 사용자에게 경고).
• Microsoft Bing(검색 엔진)은 검색 인덱스인 BitFunnel에 다단계 계층형 Bloom 필터를 사용합니다.Bloom 필터는 반전 ^[17]파일을 기반으로 했던 이전 Bing 지수보다 낮은 비용을 제공했습니다.
• Squid Web Proxy Cache는 Bloom 필터를 캐시 요약에 ^[18]사용합니다.
• 비트코인은 블룸 필터 구현에 따른 프라이버시 취약점이 ^[19]발견될 때까지 블룸 필터를 사용하여 지갑 동기화 속도를 높였습니다.
• Venti 아카이브 스토리지 시스템은 Bloom 필터를 사용하여 이전에 저장된 ^[20]데이터를 탐지합니다.
• SPIN 모델 검사기는 Bloom 필터를 사용하여 큰 검증 ^[21]문제에 대해 도달 가능한 상태 공간을 추적합니다.
• Cascading 분석 프레임워크는 Bloom 필터를 사용하여 비대칭 조인 속도를 높입니다. 여기서 조인된 데이터 세트 중 하나가 다른 데이터 세트보다 훨씬 큽니다(데이터베이스 ^[22]문헌에서는 Bloom join이라고도 함).
• Exim 메일 전송 에이전트(MTA)는 속도 제한 ^{[citation needed]}기능에 Bloom 필터를 사용합니다.
• 매체는 블룸 필터를 사용하여 사용자가 이전에 ^{[23][user-generated source?]}읽은 기사를 추천하지 않습니다.
• 이더리움은 블룸 필터를 사용하여 이더리움 블록체인의 로그를 빠르게 찾습니다.
• Grafana Tempo는 Bloom 필터를 사용하여 각 백엔드 블록에 대해 Bloom 필터를 저장하여 쿼리 성능을 향상시킵니다.제공된 검색^[24] 기준을 충족하는 데이터를 포함하는 블록을 결정하기 위해 각 쿼리에 액세스합니다.

대안

기존 Bloom 필터는 삽입된 키당 1.${\displaystyle {\mathrm{44}}_{}}$ ${\displaystyle {log}_{}}$ ${\displaystyle 2}$⁡${\displaystyle }$( 1 /${\displaystyle }$ε$$) {\$displaystyle 1.44\log _{2}($1/\$varepsilon$)}비트의 $공간$을 사용합니다. 여기서$$ε ${\displaystyle$ \$varepsilon$}는 Bloom 필터의 위양성률입니다.그러나 Bloom 필터와 동일한 역할을 수행하는 모든 데이터 구조에 엄격하게 필요한 공간은 키당 ${\displaystyle {log}_{}}$ 2 ⁡ (${\displaystyle }$1 /${\displaystyle }$ε$$) ${\displaystyle$ \$log _${$2}(1$/\$varepsilon )}$입니다.따라서 Bloom 필터는 동등한 최적의 데이터 구조보다 44% 더 많은 공간을 사용합니다.대신에, Pagh et al. 은 최적 공간 데이터 구조를 제공합니다.또한 데이터 구조는 Bloom 필터와 달리 거짓 양성률 ${\displaystyle \varepsilon}$이(${\displaystyle \mathrm{가})}$ 낮으면 쿼리당 더 많은 수의 메모리 액세스가 ${\displaystyle \mathrm{발생}}$하는 로그${\displaystyle }$⁡${\displaystyle (}$1 /${\displaystyle }$ε)$${\$displaystyle \log(1/\varepsilon$와 달리 일정한 참조 로컬리티를 갖습니다. 또한 요소를 삭제할 수 있습니다.bloom filters와 다르게 space palenty.Fan 등(2014)의 cuckoo filter에서도 동일한 향상된 특성인 최적 공간 사용, 일정한 참조 로컬리티, 요소 삭제 기능을 제공하고 있으며, 이는 오픈 소스 구현이 가능합니다.

Stern & Dill(1996)은 해시 테이블, 해시 압축에 기반한 확률적 구조를 설명하는데, Dillinger & Manolios(2004b)는 각각이 최적으로 구성될 때 Bloom 필터보다 훨씬 더 정확하다고 식별합니다.그러나 Dillinger와 Manolios는 광범위한 추가에 걸쳐 주어진 Bloom 필터의 합리적인 정확도가 크기를 알 수 없는 상태 공간의 확률적 열거에 매력적이라고 지적합니다.따라서 해시 압축은 추가 횟수를 정확하게 예측할 수 있을 때 매력적이지만 소프트웨어의 속도는 매우 빠르지만 최악의 선형 액세스 시간 때문에 하드웨어에 적합하지 않습니다.

Putze, Sanders & Singler(2007)는 고전적인 Bloom 필터보다 더 빠르거나 더 적은 공간을 사용하는 Bloom 필터의 몇 가지 변형을 연구했습니다.빠른 변형의 기본 아이디어는 각 키와 관련된 k개의 해시 값을 프로세서의 메모리 캐시 블록(일반적으로 64바이트)과 동일한 크기의 1~2개의 블록으로 찾는 것입니다.이렇게 하면 잠재적인 메모리 캐시 누락 횟수를 줄여 성능을 향상시킬 수 있습니다.그러나 제안된 변형은 기존 Bloom 필터보다 약 32% 더 많은 공간을 사용한다는 단점이 있습니다.

공간 효율적인 변형은 각 키에 대해 [${\displaystyle 0,n}$ /${\displaystyle }$ε ]${\displaystyle \left[0, n/\varepsilon \right]}$ 범위의 값을 생성하는 단일 해시 함수를 사용합니다. 여기서 ε$${\$displaystyle \varepsilon }$은(는) 요청된 위양성률입니다.그런 다음 Golomb 코딩(또는 다른 압축 기법)을 사용하여 값의 시퀀스를 정렬하고 압축하여 ${\displaystyle {nlog}_{}}$ 2 ⁡ (${\displaystyle 1}$ ${\displaystyle /}$ε )$${\$displaystyle$n\$log$ _${2}(1/\varepsilon )}$비트에 $가까운$ 공간을 차지합니다.지정된 키에 대해 Bloom 필터를 쿼리하려면 해당 값이 Bloom 필터에 저장되어 있는지 확인하면 됩니다.각 쿼리에 대해 전체 Bloom 필터를 압축 해제하면 이 변형을 완전히 사용할 수 없게 됩니다.이 문제를 해결하기 위해 값의 시퀀스는 별도로 압축된 동일한 크기의 작은 블록으로 나뉩니다.쿼리 시간에는 평균적으로 절반의 블록만 압축 해제하면 됩니다.압축 해제 오버헤드로 인해 이 변형은 기존 Bloom 필터보다 느릴 수 있지만 단일 해시 함수를 계산해야 한다는 사실로 인해 이를 보완할 수 있습니다.

고전적인 블룸 필터의 또 다른 대안은 뻐꾸기 해싱의 공간 효율적인 변형에 기반한 뻐꾸기 필터입니다.이 경우 키와 값 모두를 포함하지 않고 키의 짧은 지문(작은 해시)을 포함하는 해시 테이블이 구성됩니다.키를 찾아보면 일치하는 지문이 있으면 키가 세트에 있을 수 있습니다.cuckoo 필터의 유용한 특성 중 하나는 업데이트 가능하다는 것입니다. 항목은 동적으로 추가되고 해시 테이블이 가득 차서 실패할 가능성이 적습니다.

Graf & Lemire (2020)는 xor 필터라고 불리는 접근법을 설명하는데, 여기서 지문을 특정 유형의 완벽한 해시 테이블에 저장하여 메모리 효율성이 더 높고 ($$ 1${\displaystyle \mathrm{.}{\mathrm{23}}_{}}$ ${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle }$㎠ (${\displaystyle 1}$ ${\displaystyle /}$㎠)$${\$displaystyle$ 1$.23\log$ _${2}(1/\varepsilon }$비트$$) 블룸 또는 뻐꾸기 필터보다 빠릅니다. (시간 절약은 fac에서 나옵니다.검색을 수행하려면 메모리 액세스를 정확히 세 번만 수행해야 하며, 이를 모두 병렬로 실행할 수 있습니다.)그러나 Bloom과 cuckoo 필터보다 필터 생성이 복잡하고 생성 후 세트 수정이 불가능합니다.

확장 및 응용프로그램

Bloom 필터의 종류는 60가지가 넘으며, 현장에 대한 많은 설문조사, 애플리케이션의 지속적인 전환 등이 있습니다(예: Luo 등 참조).일부 변형들은 원래의 제안과 완전히 달라서 원래의 데이터 구조와 그 ^[26]철학을 침해하거나 침해하는 것입니다.Bloom 필터를 무작위 투영, 압축 감지 및 국소성 민감 해싱에 대한 다른 작업과 통합하는 치료는 앞으로 해야 할 일이 남아 있습니다(신경 과학에서 영감을 받은 한 가지 시도에 대해서는 Dasgupta 등^[27] 참조).

캐시 필터링

콘텐츠 제공 네트워크는 웹 캐시를 전 세계에 배치하여 웹 콘텐츠를 더욱 뛰어난 성능과 신뢰성으로 사용자에게 캐시하고 제공합니다.Bloom 필터의 핵심 응용 프로그램은 이러한 웹 캐시에 저장할 웹 개체를 효율적으로 결정하는 데 사용됩니다.일반적인 웹 캐시에서 액세스하는 URL의 거의 3/4이 사용자가 한 번만 액세스하고 다시는 액세스하지 않는 "원 히트 원더"입니다.원 히트 원더를 웹 캐시에 저장하는 것은 디스크 리소스 낭비입니다. 다시는 액세스할 수 없기 때문입니다.Bloom 필터는 원히트 원더를 캐싱하는 것을 방지하기 위해 사용자가 액세스하는 모든 URL을 추적하는 데 사용됩니다.웹 개체는 이전에 한 번 이상 액세스한 경우에만 캐시됩니다. 즉, 두 번째 요청에 따라 개체가 캐시됩니다.Bloom 필터를 이러한 방식으로 사용하면 대부분의 원히트 원더가 디스크 캐시에 기록되지 않으므로 디스크 쓰기 작업량이 크게 줄어듭니다.또한 원 히트 원더를 필터링하면 디스크의 캐시 공간도 절약되므로 캐시 적중률이 ^[12]높아집니다.

유한한 우주에서 거짓 긍정을 피하는 것

Kiss et al. 는 Bloom 필터의 새로운 구조를 설명하였는데, 이 구조는 거짓 음성의 전형적인 비존재 외에도 거짓 양성을 회피하는 것입니다.구성은 집합 요소가 추출되는 유한한 우주에 적용됩니다.그것은 Eppstein, Goodrich 및 Hirschberg의 기존의 비적응적 조합 그룹 테스트 계획에 의존합니다.일반적인 Bloom 필터와 달리 요소는 결정론적이고 빠르고 계산이 간단한 함수를 통해 비트 배열로 해시됩니다.오탐이 완전히 방지되는 최대 세트 크기는 우주 크기의 함수이며 할당된 메모리의 양에 의해 제어됩니다.

또는 초기 Bloom 필터를 표준 방식으로 구성한 다음, 유한하고 다루기 쉬운 도메인으로 모든 false positive를 철저하게 검색한 다음 해당 목록에서 두 번째 Bloom 필터를 구성할 수 있습니다. 두 번째 필터의 false positive는 세 번째 필터를 구성하는 등 유사하게 처리됩니다.우주가 유한하고 위양성의 집합이 각 단계에 따라 엄격하게 줄어들기 때문에 이 절차는 (이 닫힌 유한 도메인에서) 진정한 양과 진정한 음만 생성하는 Bloom 필터의 유한 캐스케이드 결과를 가져옵니다.필터 캐스케이드에서 멤버 자격을 확인하기 위해 초기 필터를 조회하고, 결과가 양성이면 두 번째 필터를 참조하는 등의 작업을 수행합니다.이 구성은 Web PKI를 위해 제안된 인증서 해지 상태 배포 메커니즘인 CRLite에 사용되며 Certificate Transparency를 이용하여 기존 ^[29]인증서 집합을 닫습니다.

블룸 필터 카운팅

계수 필터는 필터를 새로 만들지 않고 Bloom 필터에서 삭제 작업을 구현할 수 있는 방법을 제공합니다.카운팅 필터에서 배열 위치(버킷)는 단일 비트에서 멀티비트 카운터로 확장됩니다.실제로 일반 Bloom 필터는 버킷 크기가 1비트인 카운트 필터로 간주할 수 있습니다.Fan 등은 계수 필터를 도입했습니다. (2000).

삽입 작업은 버킷의 값을 증가시키기 위해 확장되며, 조회 작업은 필요한 버킷이 각각 0이 아님을 확인합니다.그런 다음 삭제 작업은 각 버킷의 값을 감소시키는 작업으로 구성됩니다.

버킷의 산술 오버플로가 문제이며 버킷이 충분히 커야 이 경우가 드물 수 있습니다.그런 경우 Bloom 필터의 속성을 유지하려면 증분 및 감소 작업이 버킷 설정을 가능한 최대 값으로 유지해야 합니다.

카운터의 크기는 보통 3비트 또는 4비트입니다.따라서 Bloom 필터 카운트는 정적 Bloom 필터보다 3~4배 더 많은 공간을 사용합니다.반면에 Pagh, Pagh & Rao(2005) 및 Fan et al.(2014)의 데이터 구조는 삭제를 허용하지만 정적 Bloom 필터보다 적은 공간을 사용합니다.

필터 계산 시 또 다른 문제는 확장성이 제한된다는 것입니다.카운팅 Bloom 필터 테이블을 확장할 수 없기 때문에 필터에 동시에 저장할 최대 키 수를 미리 알아야 합니다.테이블의 설계 용량이 초과되면 더 많은 키를 삽입하면 위양성률이 빠르게 증가합니다.

보노미 외. (2006)은 기능적으로 동등하지만 Bloom 필터를 세는 것보다 대략 절반 정도의 공간을 사용하는 d-left 해싱 기반의 데이터 구조를 소개했습니다.이 데이터 구조에서는 확장성 문제가 발생하지 않습니다.설계 용량이 초과되면 키를 두 배 크기의 새 해시 테이블에 다시 삽입할 수 있습니다.

Putze, Sanders & Singler (2007)의 공간 효율적인 변형은 삽입 및 삭제를 지원함으로써 카운트 필터를 구현하는 데에도 사용될 수 있습니다.

Rottenstreich, Kanizo & Keslassy(2012)는 Bloom 필터와 그 변형을 카운트하는 거짓 양의 확률을 크게 개선하면서도 삭제를 지원하는 변수 증분에 기반한 새로운 일반 방법을 도입했습니다.Bloom 필터를 카운트하는 것과 달리 각 요소 삽입 시 해시 카운터는 단위 증분이 아닌 해시 변수 증분으로 증분됩니다.요소를 쿼리하기 위해서는 카운터의 정확한 값이 고려되며 단지 카운터의 긍정성만 고려되는 것이 아닙니다.카운터 값으로 표시되는 합이 쿼리된 요소에 해당하는 변수 증분으로 구성될 수 없는 경우 쿼리에 대해 음의 답을 반환할 수 있습니다.

Kim et al. (2019)은 Counting Bloom 필터의 위양성이 k=1에서 포인트 ${\displaystyle {\mathrm{정의}}_{}}$된 kot$${\$displaystyle k_{$opt$\}$로 감소하고, ${\displaystyle {\mathrm{kot}}_{}}${\$displaystyle k_{$opt}에서 양의 무한대로 증가하며, ${\displaystyle {\mathrm{kot}}_{}}$ ${\displaystyle k_{$opt}를 카운트 임계값의 함수로 $찾습니다$.

분산집적

블룸 필터는 분산 데이터 구조로 구성되어 집계 함수의 완전 분산 계산을 수행할 수 있습니다.분산형 집계는 이러한 ^[31]목적을 위해 중앙 집중식 계산 엔티티를 수반하지 않고 분산 네트워크의 모든 노드에서 지역적으로 집합 측정을 사용할 수 있게 합니다.

분산 블룸 필터

병렬 Bloom 필터는 병렬 공유 무처리 시스템에 존재하는 다중 처리 요소(PE)를 활용하도록 구현할 수 있습니다.병렬 Bloom 필터의 주요 장애물 중 하나는 일반적으로 시작 시 또는 배치 삽입 시 모든 PE에 균등하게 분포되는 순서 없는 데이터의 구성 및 통신입니다.데이터를 주문하려면 두 가지 접근 방식을 사용하여 각 PE에 저장되는 모든 데이터에 대해 Bloom 필터를 복제하거나 모든 데이터에 대해 Bloom 필터를 동일한 부분으로 분할하여 각 PE에서 해당 ^[32]부분을 저장할 수 있습니다.두 접근 방식 모두 "Single Shot" Bloom 필터를 사용하여 해시를 하나만 계산하여 요소당 플립 비트를 하나씩 생성하여 통신 볼륨을 줄입니다.

Distributed Bloom 필터는 로컬 PE에서 모든 요소를 먼저 해시한 다음 해당 요소를 로컬 해시로 정렬하여 시작합니다.이 작업은 예를 들어 선형 시간으로 수행할 수 있습니다.버킷 정렬 및 로컬 중복 탐지도 허용합니다.정렬은 해시와 할당된 PE를 구분자로 그룹화하여 각 그룹에 대해 Bloom 필터를 생성하는 데 사용됩니다.예를 들어 이러한 Bloom 필터를 인코딩한 후각 블룸 필터를 코딩하는 골롬 코드는 해당 블룸 필터에 삽입되는 해시 값을 담당하는 PE로 패킷으로 전송됩니다.PE p는 $값$ p∗ (${\displaystyle s}$/ ${\displaystyle PE)}${\$displaystyle$ p$*(s$/${\text{)$ 사이의 모든 해시를 담당합니다.$PE}})$ 및$$(${\displaystyle p}$+ ${\displaystyle 1}$) $∗$ (${\displaystyle s}$ /${\displaystyle PE}$ )$${\$displaystyle ($p$$+$1)*(s/${\$text{$$PE$ 여기서 s는 전체 데이터에 대한 Bloom 필터의 총 크기입니다.각 요소는 한 번만 해시되므로 단일 비트만 설정되므로 요소가 Bloom 필터에 삽입되었는지 확인하려면 요소의 해시 값을 담당하는 PE만 작동하면 됩니다.단일 삽입 작업은 모든 PE에서 Bloom 필터를 업데이트해야 하는 Replicating Bloom 필터에 비해 한 PE의 Bloom 필터만 변경해야 하므로 효율적으로 수행할 수도 있습니다.글로벌 Bloom 필터를 각 PE에 별도로 저장하는 대신 모든 PE에 배포하면 Bloom 필터 크기가 훨씬 커져서 용량이 커지고 위양성률이 낮아집니다.
분산 블룸 필터는 가장 '고유'한 요소를 필터링하여 중복 탐지^[33] 알고리즘을 개선하는 데 사용할 수 있습니다.볼륨이 훨씬 큰 요소 자체가 아니라 요소 해시만 통신하고 세트에서 제거하여 이후에 사용되는 중복 탐지 알고리즘에 대한 작업량을 줄임으로써 이를 계산할 수 있습니다.

해시를 통신하는 동안 PE는 수신 패킷 중 하나 이상에 설정된 비트를 검색합니다. 이는 두 요소가 동일한 해시를 가지고 있으므로 중복될 수 있기 때문입니다.이 경우 비트 인덱스가 포함된 메시지가 전송되며, 이는 중복될 수 있는 요소의 해시이기도 하며, 설정된 비트가 포함된 패킷을 전송한 PE로 전송됩니다.한 송신자가 동일한 PE로 여러 인덱스를 전송하는 경우 인덱스를 인코딩하는 것도 유리할 수 있습니다.해시를 반환하지 않은 모든 요소는 이제 중복되지 않으며 나머지 요소에 대해서는 Repartitioning^[34] 알고리즘을 사용할 수 있습니다.먼저 해시 값이 반환된 모든 요소는 해당 해시가 담당하는 PE로 전송됩니다.모든 요소와 해당 요소의 복제는 이제 동일한 PE에 있을 수 있습니다.두 번째 단계에서 각 PE는 시작 요소의 양의 일부에 불과한 수신 요소에 대한 중복 탐지를 위해 순차적 알고리즘을 사용합니다.중복에 대해 오탐률을 허용함으로써 PE가 중복 해시를 포함한 요소를 전혀 전송할 필요가 없고, 대신 중복 해시를 포함한 모든 요소를 단순히 중복으로 표시할 수 있으므로 통신량을 더 줄일 수 있습니다.결과적으로 중복 검출에 대한 위양성률은 사용된 블룸 필터의 위양성률과 같습니다.

가장 '고유한' 요소를 걸러내는 과정도 각각의 필터링 단계에서 해시 함수를 변경해 여러 번 반복할 수 있습니다.단일 필터링 단계만 사용하는 경우 작은 거짓 양성률을 아카이브해야 하지만 첫 번째 단계를 반복하면 더 높은 거짓 양성률을 허용할 수 있지만, 두 번째 단계는 더 높은 거짓 양성률을 허용할 수 있지만 이전 필터링 단계에서 이미 제거된 요소가 더 적을 수 있습니다.두 번 이상의 반복을 사용하면 한 세트의 중복 횟수가 적을 경우 통신량을 더 줄일 수 있지만, 추가적인 문제에 대한 보상은 낮습니다.

Bloom 필터 복제는 가십에 대해 잘 알려진 하이퍼큐브 알고리즘을 사용하여 데이터를 구성합니다. 예를 들어,^[35] 먼저 각 PE가 모든 로컬 요소에 대해 Bloom 필터를 계산하고 저장합니다.각 단계 i에서 PE가 차원 i를 통해 로컬 Bloom 필터를 보내고 차원을 통해 수신한 Bloom 필터를 로컬 Bloom 필터와 병합하는 루프를 반복함으로써 각 Bloom 필터가 모든 반복에서 포함하는 요소를 두 배로 늘릴 수 있습니다.전체 ${\displaystyle \mathrm{로그}}$ ⁡ ${\displaystyle PE}$ $displaystyle \log${\$text {$에 Bloom 필터 송수신 후PE$}}} }$차원의$$ 각 PE에는 모든 요소에 글로벌 Bloom 필터가 포함되어 $있습니다$.

Bloom 필터를 복제하는 것은 Bloom 필터에 포함된 요소의 수보다 쿼리의 수가 훨씬 많을 때 더 효율적입니다. Distributed Bloom 필터와 비교한 중단점은 대략 PE ∗${\displaystyle \text{Elements}}$ / ${\displaystyle {log{}^{}}_{}}$f + ⁡ ${\displaystyle PE}${\$text}$ ${\displaystyle 다음}$입니다.$PE}} * {\text{Elements}} /\log _{f^{\text{+}} {\text{$PE$}}:$ f$$${\displaystyle {}^{}}$+ ${\$ f$^{\text{+}}$을(를) 블룸 필터의 위양성률로 $하는{\displaystyle {}^{}}$ $액세스$입니다.

데이터 동기화

Bloom 필터는 Byers 등과 같이 대략적인 데이터 동기화를 위해 사용할 수 있습니다. (2004).블룸 계수 필터는 두 세트 간의 차이 수를 근사화하는 데 사용될 수 있으며, 이 접근법은 Agarwal & Trachtenberg(2006)에 설명되어 있습니다.

스트리밍 데이터를 위한 블룸 필터

블룸 필터는 스트리밍 데이터의 상황에 맞게 조정할 수 있습니다.예를 들어, Deng & Rafiei(2006)는 Stable Bloom 필터를 제안하였는데, 여기서 새로운 요소의 삽입은 연관된 카운터를 c 값으로 설정하고, 그 후 고정된 양의 카운터만 1씩 감소시키는 카운팅 블룸 필터로 구성되어 있으며, 따라서 메모리는 대부분 최근 요소에 대한 정보를 포함하고 있습니다(직관적으로,N개 카운터의 SBF 내부에 있는 요소의 수명이 ${\displaystyle \frac{\mathrm{cs}}{}}$ {\$displaystyle$ c${\tfrac {s}{N}})$ $정도$라고 가정할 수 있습니다$.$또 다른 해결책은 Aging Bloom 필터로, 각각 사용 가능한 총 메모리의 절반을 차지하는 Bloom 필터 2개로 구성됩니다. 하나의 필터가 가득 차면 두 번째 필터가 지워지고 새로운 요소가 새로 비어 있는 ^[36]필터에 추가됩니다.

그러나^[37] 필터에 상관없이 n개의 삽입 후 거짓 $양$의 ${\displaystyle \mathrm{FP}}${\$displaystyle$FP} 및$$ 거짓 $음$의 ${\displaystyle \mathrm{FN}}$ ${\displaystyle$ FN$}$ 확률의$$ $합$은 $\mathrm{FP}$ $+$ $\mathrm{FN}$ $\ge 1\frac{\mathrm{}}{}$-$\frac{{}^{}}{}$($\frac{{1\mathrm{}}^{}}{}$- $\frac{{1\frac{L}{}}^{}}{}$) $\frac{{}^{}}{\mathrm{}}$1$\frac{{}^{}}{}$- ($\frac{{1\mathrm{}}^{}}{}$- $\frac{{\frac{1}{}}^{}}{}$L) $\frac{{}^{}}{}$ ${\$ FP$+$$FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)$$^{m}}{1-\left(1-{\frac {1}{L}}\right)$$^{n$$}}}:$ 여기서 L은 n > m {\$displaystyle$n >$m$을$($를) 가정할 때 한 모든 요소(알파벳 크기)의 양입니다.이 결과는 L이 충분히 크고 n이 무한대로 가는 경우 ${\displaystyle \mathrm{하한값}}$이${\displaystyle \mathrm{FP}}$ + ${\displaystyle \mathrm{FN}}$=$$1 {\$displaystyle$FP +로 수렴됨을 보여줍니다.$임의$ 필터의 특성 관계인 FN$=1$따라서 충분히 삽입한 후 알파벳이 너무 커서 메모리에 저장할 수 없는 경우(확률적 필터의 맥락에서 가정), 필터가 무작위성보다 더 우수한 성능을 발휘하는 것은 불가능합니다.이 결과는 전체 스트림이 아닌 슬라이딩 윈도우에서만 필터가 작동할 것으로 예상할 수 있습니다.이 경우 위 수식의 지수 n은 w로 대체되며, w가 너무 작지 않으면 1에서 벗어날 수 있는 공식을 제공합니다.

블루미어 필터

Chazelle et al. (2004)는 연관 배열을 구현하여 삽입된 각 요소와 값을 연관시킬 수 있는 Bloom 필터의 일반화를 설계했습니다.Bloom 필터와 마찬가지로, 이러한 구조는 위양성의 작은 확률을 허용함으로써 작은 공간 오버헤드를 달성합니다."Bloomier filters"의 경우, False Positive는 키가 맵에 없을 때 결과를 반환하는 것으로 정의됩니다.맵은 맵에 있는 키의 값을 잘못 반환하지 않습니다.

콤팩트한 근사기

Boldi & Vigna(2005)는 Bloom 필터의 격자 기반 일반화를 제안했습니다.콤팩트 근사기는 각 키에 격자의 요소를 연결합니다(표준 블룸 필터는 부울 2요소 격자의 경우입니다).비트 배열 대신 격자 요소 배열이 있습니다.키와 격자의 요소 사이에 새로운 연관성을 추가할 때, 그것들은 현재의 내용의 최대치를 계산합니다.k격자 요소와 관련된 키 배열 위치.키와 관련된 값을 읽을 때, 키는 키에 있는 값의 최소값을 계산합니다.k키와 연관된 위치.결과 값은 원래 값 이상에서 근사합니다.

평행 분할 블룸 필터

이 구현에서는 각 해시 함수에 대해 별도의 배열을 사용했습니다.이 방법을 사용하면 삽입과 ^[38]문의 모두에 병렬 해시 계산이 가능합니다.

확장 가능한 블룸 필터

알메이다 외. (2007)은 최소의 거짓 양성 확률을 보장하면서 저장된 요소의 수에 동적으로 적응할 수 있는 Bloom 필터의 변형을 제안했습니다.이 기법은 용량이 증가하고 위양성 확률이 더 촘촘한 표준 Bloom 필터 시퀀스를 기반으로 하여 삽입할 요소의 수에 관계없이 최대 위양성 확률을 사전에 설정할 수 있도록 합니다.

공간 블룸 필터

공간 블룸 필터(Spatial Bloom Filters, SBF)는 원래 Palmieri, Calderoni & Maio(2014)에 의해 특히 위치 프라이버시를 위한 암호화 프로토콜의 맥락에서 위치 정보를 저장하도록 설계된 데이터 구조로 제안되었습니다.그러나 SBF의 주요 특징은 여러 세트를 단일 데이터 구조에 저장할 수 있다는 점이며, 이를 통해 다양한 애플리케이션 ^[39]시나리오에 적합합니다.특정 집합에 대한 요소의 구성원 자격을 조회할 수 있으며, 위양성 확률은 집합에 따라 달라집니다. 구성 중 필터에 처음 입력되는 집합은 마지막에 ^[40]입력되는 집합보다 위양성 확률이 높습니다.이 속성을 사용하면 집합의 우선 순위를 지정할 수 있으며, 여기서 "중요한" 요소를 더 포함하는 집합을 보존할 수 있습니다.

레이어드 블룸 필터

레이어드 블룸 필터는 여러 개의 블룸 필터 레이어로 구성됩니다.Layered Bloom 필터를 사용하면 항목이 포함된 레이어 수를 확인하여 항목이 Bloom 필터에 추가된 횟수를 추적할 수 있습니다.레이어형 Bloom 필터를 사용하면 일반적으로 검사 작업을 수행하면 항목이 ^[41]발견된 가장 깊은 레이어 번호가 반환됩니다.

감쇄된 블룸 필터

깊이 D의 감쇠된 Bloom 필터는 D 일반 Bloom 필터 배열로 볼 수 있습니다.네트워크의 서비스 검색 상황에서 각 노드는 정기적이고 감쇠된 Bloom 필터를 로컬에 저장합니다.일반 블룸 필터 또는 로컬 블룸 필터는 노드 자체에서 제공하는 서비스를 나타냅니다.레벨 i의 감쇠 필터는 현재 노드에서 떨어진 i홉인 노드에서 어떤 서비스를 찾을 수 있는지 나타냅니다.i번째 값은 노드 ^[42]i-홉에 대한 로컬 Bloom 필터 조합을 노드에서 분리하여 구성됩니다.

아래 그래프에 나와 있는 작은 네트워크를 예로 들어보겠습니다.ID가 비트 0, 1, 3(패턴 11010)으로 해시되는 서비스 A를 찾고 있다고 가정합니다.n1 노드를 시작점으로 합니다.우선 A 서비스가 n1에서 제공되는지 로컬 필터를 확인하여 확인합니다.패턴이 일치하지 않기 때문에 다음 홉이 될 노드를 결정하기 위해 감쇄된 Bloom 필터를 확인합니다.우리는 n2가 A 서비스를 제공하는 것이 아니라 A 서비스를 제공하는 노드로 가는 경로 위에 놓여 있음을 봅니다.따라서 n2로 이동하여 동일한 절차를 반복합니다.우리는 n3가 서비스를 제공하고, 따라서 목적지가 ^[43]위치하는 것을 빠르게 발견합니다.

여러 계층으로 구성된 감쇄된 Bloom 필터를 사용하면 소스에서 설정한 비트를 더 멀리 ^[42]감쇄(shift out)하여 Bloom 필터의 포화를 방지하면서 한 홉 이상의 거리에서 서비스를 검색할 수 있습니다.

화학구조 탐색

블룸 필터는 종종 대규모 화학 구조 데이터베이스를 검색하는 데 사용됩니다(화학적 유사성 참조).가장 간단한 경우, 필터에 추가된 요소(이 필드에서는 지문이라고 함)는 분자에 존재하는 원자 번호 또는 각 원자의 원자 번호와 결합의 수 및 유형에 기초한 해시입니다.이 케이스는 너무 간단해서 쓸모가 없습니다.또한 고급 필터는 원자 수, 카르복실 그룹과 같은 더 큰 하부 구조 특성, 고리 수와 같은 그래프 특성을 인코딩합니다.해시 기반 지문에서는 서브그래프를 PRNG 시드로 변환하기 위해 원자와 본드 특성에 기반한 해시 함수를 사용하고 Bloom 필터에서 비트를 설정하는 데 사용되는 첫 번째 출력 값을 사용합니다.

분자 지문은 1940년대 후반 천공 카드에서 검색된 화학 구조를 검색하기 위한 방법으로 시작되었습니다.그러나 1990년경이 되어서야 Daylight Chemical Information Systems, Inc.는 미리 계산된 표를 사용하는 대신 비트를 생성하기 위해 해시 기반 방법을 도입했습니다.사전 접근 방식과 달리 해시 방식은 이전에 볼 수 없었던 하위 구조에 비트를 할당할 수 있습니다.1990년대 초에 "지문"이라는 용어는 "구조 키"와 다르게 여겨졌지만, 이후 이 용어는 구조 키, 희소 카운트 지문, 3D 지문을 포함하여 유사성 비교에 사용될 수 있는 대부분의 분자적 특성을 포괄하는 것으로 성장했습니다.Bloom 필터와 달리 Daylight 해시 메서드는 피쳐당 할당된 비트 수를 피쳐 크기의 함수로 사용할 수 있지만 Daylight와 같은 핑거프린트의 대부분 구현에서는 피쳐당 고정된 비트 수를 사용하므로 Bloom 필터가 됩니다.원본 일광 지문은 유사성 및 선별 목적 모두에 사용될 수 있습니다.일반적인 ECFP2와 같은 다른 많은 지문 유형은 스크린으로 사용될 때 거짓 음성을 도입하는 지역 환경 특성을 포함하기 때문에 유사성에는 사용할 수 있지만 스크리닝에는 사용되지 않습니다.동일한 메커니즘으로 구성된 경우에도 필터링에 사용할 수 없기 때문에 Bloom 필터가 아닙니다.

참고 항목

• 카운트-민 스케치
• 피쳐 해싱
• MinHash – 데이터 마이닝 기법
• 몫필터
• 목록 건너뛰기 – 확률적 데이터 구조
• 생물정보학의 블룸 필터
• 뻐꾸기 필터

참고문헌

이 글은 인용문이 불명확합니다. 사용된 참조는 인용 및 각주의 다른 또는 일관된 스타일로 보다 명확해질 수 있습니다. (2023년 8월) (본 템플릿 메시지 삭제 방법 및 시기 알아보기)

인용문

인용작품

외부 링크

• "Bloom Filters 사용하기" Perl을 사용한 Bloom Filter 상세 설명
• Bloom 필터가 작동하는 이유(Michael Nielsen, 2012)
• Bloom Filters — Dalhousie University의 Tutorial, Analysis and Survey (Blustein & El-Maazawi, 2002)
• 위스콘신 대학교 매디슨 웹사이트의 다양한 구성에 대한 위양성률 표
• "More Optimal Bloom Filters", Ely Porat (Nov/2007) Google TechTalk 동영상 on YouTube