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
,
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
.
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 a zvyšuje se z do kladného nekonečna.[2]
Kim a kol. (2019) zobrazuje číselné hodnoty v rámci . Li θ je větší než 30, navrhli použít nebo .
Reference
- ^ Tarkoma, Sasu; Rothenberg, Christian Esteve; Lagerspetz, Eemil (2012). „Teorie a praxe Bloomových filtrů pro distribuované systémy“. Průzkumy a návody pro komunikaci IEEE. 14 (1): 131–155. doi:10.1109 / přežít.2011.031611.00024. ISSN 1553-877X.
- ^ Lee, Sunggu; Lee, Youngjoo; Jeong, Yongjo; Kim, Kibeom (červenec 2019). "Analýza počítání Bloomových filtrů použitých pro prahování počtu". Elektronika. 8 (7): 779. doi:10,3390 / elektronika8070779.