Filtr počítání Bloom - Counting Bloom filter

A Filtr počítání Bloom je zobecněný datová struktura z Bloomův filtr, který se používá k testování, zda je počet čísel daného živel je menší než daná prahová hodnota, když je dána sekvence prvků. Jako zobecněná forma Bloomův filtr, falešně pozitivní shody jsou možné, ale falešné negativy nejsou - jinými slovy, dotaz vrací buď „možná větší nebo rovný prahové hodnotě“ nebo „rozhodně menší než prahová hodnota“.

Popis algoritmu

Většina parametrů je definována stejně Bloomův filtr, jako n, k. m je počet čítačů ve filtru Counting Bloom, což je rozšíření o m bity ve filtru Bloom. An prázdný filtr Počítání květu je m čítače, vše nastaveno na 0. Podobně jako Bloomův filtr, musí také existovat k odlišný hashovací funkce definované, z nichž každý mapy nebo hashuje některý nastavený prvek do jednoho z m pozice pole čítače, generující rovnoměrné náhodné rozdělení. Je to také podobné k je konstanta, mnohem menší než m, což je úměrné počtu prvků, které se mají přidat.

Hlavní zobecnění Bloomova filtru je přidání prvku. Na přidat prvek, přivádějte jej ke každému z k hash funkce dostat k pozice pole a přírůstek čítače 1 na všech těchto pozicích.

Na dotaz pro prvek s prahovou hodnotou θ (vyzkoušejte, zda je počet prvků menší než θ), přikrmte jej každému z k hash funkce dostat k pozice počítadla. Pokud je některý z čítačů na těchto pozicích menší než θ, počet prvků je rozhodně menší než θ - kdyby to bylo více a stejné, pak by všechny odpovídající čítače byly větší nebo stejné θ. Pokud jsou všechny větší nebo rovny θ, pak je počet buď opravdu větší, nebo rovno θnebo čítače byly náhodou větší nebo rovny θ. Pokud jsou všechny větší nebo rovno θ, i když je počet menší než θ, tato okolnost je definována jako falešně pozitivní. To by také mělo být minimalizováno jako Bloomův filtr.

O problému s hashováním a výhodách viz Bloomův filtr.

Pravděpodobnost falešných poplachů

Stejné předpoklady v Bloomův filtr, který díky hashovacím funkcím činí vkládání jednotným náhodným, se zde také předpokládá. V m hrnce, kn koule jsou vkládány náhodně. Pravděpodobnost jednoho z čítačů ve filtru Counting Bloom se tedy počítá l je

${ displaystyle b (l, kn, { frac {1} {m}}) = {kn zvolit l} ({ frac {1} {m}}) ^ {l} (1 - { frac { 1} {m}}) ^ {kn-l}}$,

kde b je binomická distribuce.^[1] Mimochodem, filtr Počítání květu určuje, že prvek je větší nebo rovný θ když odpovídající k počitadla jsou větší nebo rovna θ. Proto je pravděpodobnost, že filtr Počítání květu určuje prvek, větší nebo stejná θ je

${ displaystyle p_ {fp} ( theta, k, n, m) = (1- součet limity _ {l < theta} b (l, kn, { frac {1} {m}})) ^ {k}}$.

To se liší od formální definice falešně pozitivní ve filtru Counting Bloom. V návaznosti na předpoklad ve filtru Bloom je však výše pravděpodobnosti definována jako falešně pozitivní filtru Counting Bloom. Li θ= 1, rovnice se stane falešně pozitivním Bloomova filtru.

Optimální počet hashovacích funkcí

Pro velké, ale pevné n a m, falešně pozitivní klesá z k = 1 na definovaný bod ${ displaystyle k_ {opt}}$a zvyšuje se z ${ displaystyle k_ {opt}}$do kladného nekonečna.^[2]

Kim a kol. (2019) zobrazuje číselné hodnoty ${ displaystyle k_ {opt}}$v rámci ${ displaystyle 1 leq theta leq 30}$. Li θ je větší než 30, navrhli použít ${ displaystyle k_ {opt} = lfloor { frac {m} {n}} (0,2037 theta +0,9176) rfloor}$nebo ${ displaystyle k_ {opt} = lceil { frac {m} {n}} (0,2037 theta +0,9176) rceil}$.

Reference