Bloomův filtr

Bloomův filtr, pojmenovaný podle Burtona Howarda Blooma, který ho objevil v roce 1970, je prostorově efektivní pravděpodobnostní datová struktura, která se používá na ověřování příslušnosti prvků do množiny. Protože je tato struktura pravděpodobnostní, mohou při tomto ověřování nastat chyby. Při této chybě se o prvku, který ve skutečnosti do dané množiny nepatří, dozvíme, že tam patří, ale nikdy ne naopak. To znamená, že při odpovědi, že daný prvek do množiny nepatří, se dá na Bloomův filtr spolehnout na 100%. Pravděpodobnost chyby roste s větším počtem prvků v dané množině (při pevné velikosti reprezentace).

Bloomův filtr se používá v různých aplikacích. Například, databázový systém Big Table od společnosti Google používá Bloomův filtr na redukování vyhledávání na disku. Před tím, než vůbec zpracuje požadavek, ověří si pomocí Bloomova filtru, zda daný řádek anebo sloupec databáze existuje (tj. zda patří do množiny reprezentované Bloomovým filtrem). Kvůli charakteru možných chyb při použití Bloomova filtru se nikdy nemůže stát, že by "přehlédnul" existující záznam. Tím se výrazně zvyšuje výkon databázového systému (při neexistujících záznamech nemusí pokaždé číst z disku) při zachování stoprocentní spolehlivosti. Bloomovy filtry používá také proxy server Squid pro tzv. cache digests a archivační systém Venti na detekování předtím vloženého obsahu.

Popis algoritmu

Příklad Bloomova filtru reprezentujícího množinu {x, y, z}. Barevné šipky ukazují na pozice v bitové poli, kde jsou na základě hašovacích funkcí přiřazeny všechny prvky množiny. Množina {x, y, z} neobsahuje prvek w, protože existuje taková hašovací funkce, které hodnota je pro vstup w rovná 0. V tomto příklade je m=18 (velikost pole) a k=3 (počet hašovacích funkcí). Barva šipek určuje vstup hašovací funkce (teda prvek univerza), pro každou barvu jsou 3 šipky odpovídající třem hašovacím funkcím (k = 3).

Prázdný Bloomův filtr (odpovídající prázdné množině) je bitové pole délky m bitů, přičemž všechny hodnoty pole jsou nastaveny na 0.

Na práci s Bloomovým filtrem je potřebné mít definovaných k různých hašovacích funkcí, přičemž každá z nich (při zachování požadavku rovnoměrného hašování) přiřadí každému prvku univerza (množina všech prvků, o kterých potenciálně můžeme chtít zjišťovat jejich příslušnost do množiny) jednu z m pozic pole.

Vložení prvku x do reprezentované množiny funguje podle následujícího algoritmu:

1. Vypočítejme hodnotu každé z k hašovacích funkcí (označme tyto hašovací funkce $h_{1}\ldots h_{k}$) pro argument x.
2. Takto dostaneme hodnoty $h_{1}(x),h_{2}(x),\ldots h_{k}(x)$, teda nejvíc k různých hodnot.
3. Nastavme hodnoty pole na pozicích $h_{1}(x),h_{2}(x),\ldots h_{k}(x)$ na 1.

Dotaz na nějaký prvek x (tj. otázka, zda prvek x patří do množiny anebo nepatří) funguje podle následujícího algoritmu:

1. Vypočítejme hodnotu každé z k hašovacích funkcí (označme tyto hašovací funkce $h_{1}\ldots h_{k}$) pro argument x (stejně jako při vkládání).
2. Takto dostaneme hodnoty $h_{1}(x),h_{2}(x),\ldots h_{k}(x)$, teda nejvíc k různých hodnot (stejně jako při vkládání).
3. Podíváme se na hodnoty pole na pozicích $h_{1}(x),h_{2}(x),\ldots h_{k}(x)$. Pokud je aspoň jedna z nich 0, můžeme s určitostí říct, že prvek x se v množině nenachází, protože jinak by byly všechny tyto hodnoty při jeho vložení nastaveny na 1. Pokud jsou všechny tyto hodnoty 1, potom sice s určitostí nelze říct nic, ale aspoň pro menší počet prvků v množině je relativně vysoká pravděpodobnost, že prvek x se v množině nachází. Proto je výstupem algoritmu zjištění, že prvek se v množině nachází, je potřeba ale počítat s možností chyby.

Protože při dotazech na prvky mohou vznikat chyby, Bloomovy filtry se v praxi používají obzvlášť tehdy, když chyba tohoto druhu nemůže způsobit problém. Teda například v této modelové situaci: máme nějakou proceduru, která na základě nějakého vstupu vykoná nějakou proceduru (typicky nějaké časově náročné výpočty). Výpočet ale může proběhnout úspěšně jen v případě, pokud byl vstup ještě před tímto požadavkem uživatelem vložen do nějaké databáze informací (teda např. k rodnému číslu, které budeme považovat za vstup, musíme mít v databázi jméno, příjmení,...). V takovém případě lze říct, že vstup bude patřit do množiny, pokud o něm v dané databázi existuje záznam, v opačném případě do ní nebude patřit. V případě, že dokážeme ještě před spuštěním výpočtu určit, že vstup do této množiny nepatří, umíme ušetřit náklady na vykonání tohoto výpočtu. Na to lze použít Bloomův filtr. Pokud nastane chyba, neznamená to velký problém, protože fakt, že vstup do množiny nepatří, dokážeme zjistit i po vykonání výpočtu (pouze to bude stát nějaký výpočtový čas). V mnoha případech však chyba nenastane, a co je podstatné, nikdy nenastane v případě, že vstup skutečně do množiny patří. Bloomův filtr tedy, jak napovídá jeho název, dokáže odfiltrovat poměrně velké množství vstupů, pro které bychom výpočet spouštěli marně.

Omezení Bloomových filtrů

Asi nejpodstatnějším omezením Bloomových filtrů je, že z pochopitelných důvodů nepodporují odebírání prvků z množiny. Pokud bychom se totiž pokusili všech k hodnot daných vzpomínanými hašovacími funkcemi pro prvek x nastavit na 0, mohlo by se stát, že bychom nedopatřením odebrali také jiný prvek - libovolný prvek y, který je prvkem množiny a současně hodnota aspoň jedné hašovací funkce má pro vstup y stejnou hodnotu jako některá z těchto k hodnot. Tím by se ale porušila základní vlastnost Bloomových filtrů, že pokud prvek patří do množiny, výsledkem dotazu je vždy kladná odpověď.

Reference

V tomto článku byl použit překlad textu z článku Bloomov filter na slovenské Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu Bloomův filtr na Wikimedia Commons
• Originální článek (anglicky)
• Implementace Bloomova filtru Archivováno 17. 2. 2012 na Wayback Machine. v jazyce C (anglicky)
• Implementace Bloomova filtru v jazyce Java (anglicky)
• Less Hashing, Same Performance: Building a Better Bloom Filter - článek o optimalizaci Bloomových filtrů (anglicky)