Bloomov filter

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Bloomov filter, pomenovaný podľa Burtona Howarda Blooma, ktorý ho objavil v roku 1970,[1] je priestorovo efektívna pravdepodobnostná dátová štruktúra, ktorá sa používa na overovanie príslušnosti prvku do množiny. Keďže je táto štruktúra pravdepodobnostná, môžu pri tomto overovaní nastať chyby. Takáto chyba môže znamenať, že o prvku, ktorý v skutočnosti do danej množiny nepatrí, zistíme, že tam patrí, ale nikdy nie naopak. To znamená, že pri zistení, že daný prvok do množiny nepatrí, sa dá na Bloomov filter spoľahnúť na 100%. Pravdepodobnosť chyby je tým väčšia, čím je väčší počet prvkov v danej množine.

Bloomov filter sa používa v rôznych aplikáciách. Napríklad, databázový systém Big Table od spoločnosti Google používa Bloomov filter na redukovanie vyhľadávania na disku. Pred tým, ako vôbec spracuje požiadavku, overí si pomocou Bloomovho filtra, či daný riadok alebo stĺpec databázy existuje (t. j., či patrí do množiny reprezentovanej Bloomovým filtrom). Vďaka charakteru možných chýb pri použití Bloomovho filtra sa nikdy nemôže stať, že by "prehliadol" existujúci záznam. Tým sa výrazne zvyšuje výkon databázovej požiadavky (pri neexistujúcich záznamoch nemusí zakaždým čítať z disku) pri zachovaní stopercentnej spoľahlivosti.[2] Bloomove filtre tiež používa proxy server Squid pre tzv. cache digests [3] a archivačný systém Venti na detekovanie predtým vloženého obsahu.[4]

Popis algoritmu[upraviť | upraviť zdroj]

Príklad Bloomovho filtra reprezentujúceho množinu {x, y, z}. Farebné šípky ukazujú na pozície v bitovom poli kde sú na základe hašovacích funkcií priradené všetky prvky množiny. Množina {x, y, z} neobsahuje prvok w, pretože existuje taká hašovacia funkcia, ktorej hodnota je pre vstup w rovná 0. V tomto príklade je m=18 (veľkosť poľa) a k=3 (počet hašovacích funkcií). Farba šípok určuje vstup hašovacej funkcie (teda prvok univerza), pre každú farbu sú 3 šípky zodpovedajúce trom hašovacím funkciám (k = 3).

Prázdny Bloomov filter (zodpovedajúci prázdnej množine) je bitové pole dĺžky m bitov, pričom všetky hodnoty poľa sú nastavené na 0.

Na prácu s Bloomovým filtrom je potrebné mať definovaných k rôznych hašovacích funkcií, pričom každá z nich (za zachovania požiadavky rovnomerného hašovnia) priradí každému prvku univerza (množina všetkých prvkov, o ktorých potenciálne môžeme chcieť zisťovať ich príslušnosť do množiny) jedno z m pozícií poľa.

Vloženie prvku x do množiny funguje podľa nasledujúceho algoritmu:

  1. Vypočítajme hodnotu každej z k hašovacích funkcií (označme tieto hašovacie funkcie h_1 \ldots h_k) pre argument x.
  2. Takto dostaneme hodnoty h_1(x), h_2(x), \ldots h_k(x), čiže najviac k rôznych hodnôt.
  3. Nastavme hodnoty poľa na pozíciách h_1(x), h_2(x), \ldots h_k(x) na 1.

Dopyt na nejaký prvok x (t. j. otázka, či prvok x patrí do množiny, alebo nie) funguje podľa nasledujúceho algoritmu:

  1. Vypočítajme hodnotu každej z k hašovacích funkcií (označme tieto hašovacie funkcie h_1 \ldots h_k) pre argument x (rovnako ako pri vkladaní).
  2. Takto dostaneme hodnoty h_1(x), h_2(x), \ldots h_k(x), čiže najviac k rôznych hodnôt (rovnako ako pri vkladaní).
  3. Pozrieme sa na hodnoty poľa na pozíciách h_1(x), h_2(x), \ldots h_k(x). Ak je jedna z nich 0, vieme s určitosťou povedať, že prvok x sa v množine nenachádza, keďže ináč by boli všetky tieto hodnoty pri jeho vložení nastavené na 1. Ak sú všetky tieto hodnoty 1, potom síce s určitosťou nemôžme povedať nič, ale aspoň pre menší počet prvkov v množine je relatívne vysoká pravdepodobnosť, že prvok x sa v množine nachádza. Preto je výstupom algoritmu zistenie, že prvok sa v množine nachádza, treba však rátať s možnosťou chyby.

Keďže pri dopytoch na prvky môžu vznikať chyby, Bloomove filtre sa v praxi používajú najmä vtedy, keď chyba tohto druhu nemôže spôsobiť problém. Teda napríklad v takejto modelovej situácii: máme nejakú procedúru, ktorá na základe nejakého vstupu vykoná nejakú procedúru (typicky nejaké časovo náročné výpočty). Výpočet však môže prebehnúť úspešne len v prípade, ak bol vstup ešte pred touto požiadavkou užívateľom vložený do nejakej databázy informácií (teda napr. k rodnému číslu, ktoré budeme považovať za vstup, musíme mať v databáze meno, priezvisko,...). V takom prípade môžme povedať, že vstup bude patriť do množiny, ak o ňom v danej databáze jestvuje záznam, v opačnom prípade do nej nebude patriť. V prípade, že vieme ešte pred spustením výpočtu určiť, že vstup do tejto množiny nepatrí, vieme ušetriť náklady na vykonanie tohto výpočtu. Na to môžme použiť Bloomov filter. Ak nastane chyba, neznamená to veľký problém, pretože fakt, že vstup do množiny nepatrí, vieme zistiť aj po vykonaní výpočtu (akurát to bude stáť istý výpočtový čas). V mnohých prípadoch však chyba nenastane, a čo je podstatné, nikdy nenastane v prípade, že vstup skutočne do množiny patrí. Bloomov filter teda, ako napovedá jeho názov, dokáže odfiltrovať pomerne veľké množstvo vstupov, pre ktoré by sme výpočet spúšťali márne.

Obmedzenia Bloomových filtrov[upraviť | upraviť zdroj]

Asi najpodstatnejším obmedzením Bloomových filtrov je, že z pochopiteľných dôvodov nepodporuje odoberanie prvkov z množiny. Ak by sme sa totiž pokúsili všetkých k hodnôt daných spomínanými hašovacími funkciami pre prvok x nastaviť na 0, mohlo by sa stať, že by sme nechtiac odobrali aj iný prvok - ľubovoľný prvok y, ktorý je prvkom množiny a súčasne hodnota aspoň jednej hašovacej funkcie má pre vstup y rovnakú hodnotu ako niektorá z týchto k hodnôt. Tým by sa ale porušila základná vlastnosť Bloomových filtrov, t. j., že ak prvok patrí do množiny, výsledkom dopytu je vždy kladná odpoveď.

Referencie[upraviť | upraviť zdroj]

  1. Donald Knuth. The Art of Computer Programming, Errata for Volume 3 (2nd ed.).
  2. „Bigtable: A Distributed Storage System for Structured Data“, Seventh Symposium on Operating System Design and Implementation, 2006, http://labs.google.com/papers/bigtable.html .
  3. WESSELS, Duane (January 2004). “10.7 Cache Digests”, Squid: The Definitive Guide, 1st, O'Reilly Media. ISBN 0596001622. “Cache Digests are based on a technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter to represent the cache contents.”
  4. http://plan9.bell-labs.com/magic/man2html/8/venti

Externé odkazy[upraviť | upraviť zdroj]