Bloomov filter je jednoduchá, pamäťovo efektívna dátová štruktúra určená na rýchle testovanie, či sa určitý prvok najpravdepodobnejšie nachádza v množine. Neposkytuje presnú odpoveď v každom prípade, ale vracia buď „určite nie je v množine“, alebo „pravdepodobne je v množine“. Tento behavior je dôsledkom použitia viacerých hashovacích funkcií a bitového poľa, v ktorom sa nastavujú bity pre pridávané prvky.
Základný princíp a vlastnosti
Bloomov filter reprezentuje množinu ako pole bitov a súbor k rôznych hashovacích funkcií. Pri vložení nového prvku sa vypočítajú jeho k hash hodnôt; každá určí pozíciu v bitovom poli a príslušný bit sa nastaví na 1. Pri overovaní členstva sa skontrolujú rovnaké pozície — ak je aspoň jeden bit 0, prvok určite nie je v množine. Ak sú všetky bity 1, filter odpovie, že prvok pravdepodobne patrí do množiny. Táto vlastnosť robí Bloomov filter pravdepodobnostnou štruktúrou a umožňuje vznik falošne pozitívnych výsledkov (pozitívny odhad pre prvok, ktorý v skutočnosti v množine nie je) — falošné negatívy však nenastávajú.
Hlavné charakteristiky
- Veľkosť: uložené v kompaktnom bitovom poli, ktoré šetrí pamäť oproti explicitnému ukladaniu prvkov.
- Rýchlosť: operácie vloženia a dotazu sú veľmi rýchle a zvyčajne konštantné.
- Chyby: parameter k (počet hashov) a veľkosť poľa určujú mieru falošných pozitív; s pribúdajúcimi prvkami sa pravdepodobnosť falošných pozitív zvyšuje.
- Limitácie: štandardný Bloomov filter nepodporuje spoľahlivé vymazávanie prvkov bez modifikácií.
Krátka história
Bloomov filter navrhol v roku 1970 Edward Bloom pri riešení praktického problému s efektívnym testovaním slov pri deleniach riadkov a spojovníkoch. Jeho motivácia bola znížiť počet pomalých prístupov na disk pri vyhľadávaní pravidiel; zamiesto presného, ale pamäťovo náročného ukladania všetkých vzorov, použil kompaktné, chybové (probabilistické) riešenie, ktoré eliminovalo veľkú časť zbytočných operácií. Viac kontextu o pôvode problému je dostupné cez pôvodnú prácu.
Použitia a príklady
Bloomove filtre sa široko používajú tam, kde je potrebné rýchlo odmietnuť neprítomné položky pri nízkej spotrebe pamäte. Bežné oblasti nasadenia zahŕňajú:
- cache a filtračné mechanizmy: zabránenie nepotrebným dotazom na pomalé úložiská, ak je zrejmé, že položka nie je prítomná;
- databázy a indexovanie: rýchle testy pred drahými operáciami načítania;
- siete a distribuované systémy: zníženie prenosu pri synchronizácii alebo filtrovaní duplicitných položiek;
- kontrola spamov, zdieľanie súborov a ďalšie aplikácie, kde sa akceptuje malá miera falošných pozitív.
Varianty a praktické poznámky
Aby sa odstránila nemožnosť mazania, vznikol counting Bloom filter, ktorý namiesto bitov používa malé čítače a umožňuje deaktivovať položky pomocou dekrementácie. Iné rozšírenia riešia adaptívne zmeny veľkosti, redukciu kolízií alebo kombinujú Bloomove filtre do viacúrovňových schém. Pri navrhovaní systému s Bloomovým filtrom treba zvoliť vhodný pomer veľkosti poľa k počtu očakávaných prvkov a optimálny počet hashovacích funkcií — tieto parametre určujú kompromis medzi pamäťou a mierou falošných pozitív. Ako orientačné vodítko sa často uvádza, že pre dosiahnutie asi 1 % pravdepodobnosti falošných pozitív stačí rádovo niekoľko bitov na prvok (napríklad menej než desať bitov na prvok) — toto číslo však závisí od konkrétnych požiadaviek a nastavení implementácie a preto ho treba brať ako približný údaj (bity na prvok).
Bloomov filter je v praxi cenný tam, kde dominuje potreba rýchlosti a úspory pamäte a kde sú falošné pozitíva prijateľné. Pri kritických aplikáciách, kde je potrebná absolútna istota pre každú položku, sa namiesto neho volia deterministické riešenia.
Pre viac technických detailov, implementačných príkladov a variantov možno sledovať zdroje a návody dostupné online: dátová štruktúra (základ), prvok (vysvetlenie), hashovacie funkcie (výber), pravdepodobnostné modely, falošné pozitíva (riešenia), história návrhu a odhad bitov na prvok.