Bloom-szűrő

A Bloom-szűrő hatékony valószínűségi alapú adatszerkezet, melyet Burton Howard Bloom írt le 1970-ben, annak ellenőrzésére használják, hogy egy elem egy halmaz eleme-e. Hamis pozitívok előfordulhatnak, de hamis negatívok nem – tehát egy kérés vagy „a halmazban lehet”, vagy „egyértelműen nincs a halmazban” eredményt ad. Hozzáadhatók elemek a halmazhoz, de el nem vehetők (de ez számláló Bloom-szűrővel megoldható). Az elemszámmal nő a hamis pozitív eredmény valószínűsége.

Ez az $x\in X$ elemek leképezését jelenti $y=h(x)\in Y$-ra, majd $x^{\prime }\in X$ vizsgálatát annak vizsgálatával, hogy $y^{\prime }=h(x^{\prime })\in Y$, mindezt több h hasítófüggvénnyel vizsgálva.

Bloom a technikát olyan esetekre javasolta, ha a forrásadat nagy memóriát igényelne „hagyományos” hibamentes hasítási technikákkal. Példaként írt egy Sablon:Szám szavas szótár szótagolási algoritmusáról, ahol a szavak 90%-a egyszerű szabályt követ, de a maradék 10% költséges tárhelyhozzáférést igényel bizonyos szótagolási minták megszerzéséhez. Elegendő magmemóriával egy hibátlan hasítófüggvény használható minden felesleges hozzáférés megszüntetéséhez, de korlátozott memória esetén Bloom technikája kisebb területet igényel, de a legtöbb felesleges hozzáférést megszünteti. Például egy ideális hasításhoz szükséges terület 15%-ával megegyező hasítási terület a hozzáférések 85%-át megszünteti.Sablon:Sfnp

Általánosabban: kevesebb mint 10 bit szükséges 1%-os hamispozitív-valószínűséghez elemszámtól és mérettől függetlenül.Sablon:Sfnp

Az algoritmus leírása

Bloom-szűrő, melynek elemei $\{x,y,z\}$. A színes nyilak az elemekhez rendelt helyeket mutatják a bittömbben. A w elem nem része az $\{x,y,z\}$ halmaznak, mivel egy 0-t tartalmazó helyhez is rendeli a hasítófüggvény. Az ábrán $m=18\wedge k=3$.

Az üres Bloom-szűrő $m$ 0 bitből álló sor. Ezenkívül szükséges $k$ különböző hasítófüggvény, melyek egyes elemeket a tömbbeli helyek valamelyikéhez rendelnek egy elemet, uniform véletlenszerű eloszlást létrehozva. Általában k kis, az $\epsilon$ hibaaránytól függő konstans, míg m k-val és a hozzáadandó elemek számával arányos.

Egy elem hozzáadásához a k hasítófüggvény argumentumaként adandó meg, így k helyet kapva. E helyek bitjei 1-re állítandók.

Egy elem lekérdezéséhez (vagyis annak ellenőrzéséhez, hogy a halmaz eleme-e) megadandó a k hasítófüggvény argumentumaként, így k helyet kapva. Ha bármely helyen a bit 0, az elem nem eleme a halmaznak, ha az volna, beillesztésekor minden bit 1 lenne. Ha mindegyik 1, vagy a halmaz eleme az elem, vagy más elemek hozzáadásakor változtak 1-re a bitek, hamis pozitívot adva. Egyszerű Bloom-szűrőben nincs különbség a két eset közt, de összetettebb módszerek megoldják ezt.

A k eltérő függvény tervezése nehézkes lehet nagy k-ra. Egy jó, széles kimenetű hasítófüggvényhez gyenge korrelációnak kell lennie (ha egyáltalán van) a különböző bitmezők közt, így több „különböző” hasítófüggvény hozható létre a kimenet több bitmezőre való szeletelésével. Egy másik mód k eltérő bemeneti érték (például $0,1,\dots ,k-1$) bevitele egy bemenetű hasítófüggvényhez, vagy ezen értékek kulcshoz adása. Nagy m vagy k esetén a függvények függetlensége a hamispozitív-arány csekély növekedésével enyhíthető. (Különösen Sablon:Harvtxt mutatja meg a k index levezetését javított dupla, illetve tripla hasítással, melyek a dupla hasítás egyszerű véletlenszám-generáló változatai, melyek bemenete a két vagy három hasítási érték.)

Egy elem eltávolítása egyszerű Bloom-szűrőből lehetetlen, mivel nem deríthető ki, hogy a k hozzárendelt bit melyike állítandó 0-ra. Bár a k bit bármelyikének 0-ra állítása elég az elem eltávolításához, ez más elemeket is eltávolít, melyeknek e bitre van leképezésük. Mivel az egyszerű algoritmus nem ad lehetőséget annak meghatározására, hogy más elemek is vannak-e, melyek megváltoztatják az elemhez eltávolítható biteket, bármely bit eltávolítása hamis negatívot okozhat.

Egy elem egyszeri eltávolítása egy Bloom-szűrőből szimulálható másik Bloom-szűrővel, mely az eltávolított elemeket tartalmazza. Azonban a második szűrő hamis pozitívjai az összetett szűrőben nem kívánt hamis negatívok lesznek. Ekkor egy korábban törölt elem visszaadása nem lehetséges, mivel a „törölt” szűrőből kellene törölni.

Gyakran bár minden kulcs elérhető, de felsorolásuk költséges (például sok olvasási műveletet igényel). Ha a hamispozitív-arány túl magas, a szűrő újból létrehozható, de ez általában ritka.

Hely- és időelőnyök

Bloom-szűrő kulcsértékes tároló válaszidejének gyorsítására. Az értékek hosszú elérési idejű meghajtón vannak, a Bloom-szűrős döntések sokkal gyorsabbak. Pozitív jelzés esetén a hamis pozitívok kiszűréséért néhány hozzáférés történik. A válaszidő jobb Bloom-szűrővel, mint anélkül.

A hamis pozitívok kockázata ellenére a Bloom-szűrők jelentős helyelőnnyel rendelkezik más halmazjelölő adatszerkezetekhez képest, amilyenek az önkiegyensúlyozó bináris keresőfák, a trie-k, a hasítótáblák, a tömbök és a bejegyzések kapcsolt listái. Ezek legtöbbjéhez szükséges maguknak az elemeknek a tárolása, mely kevés bittől (kis egészek) tetszőleges számú bitet igénybevehetnek, például sztringek esetén (a trie-k kivételek, mivel azonos prefixumú elemek közt megoszthatnak tárhelyet). Azonban a Bloom-szűrők nem tárolják magukat az adatokat, és önálló megoldás kell a tényleges tárhelyhez. A kapcsolt szerkezeteknek a mutatókhoz lineáris helytöbblet kell. Egy 1%-os hibaarányú, k optimális értékű Bloom-szűrőhöz ezzel szemben elemenként mintegy 9,6 bit kell elemmérettől függetlenül. Ennek oka részben a tömbökhöz hasonló tömörség, részben a valószínűség-alapú természete. Az 1%-os hamispozitív-arány elemenként mintegy 4,8 bittel tizedére csökkenthető.

Azonban ha a lehetséges értékek száma kicsi, és nagy részük a halmaz eleme lehet, a Bloom-szűrőnél a determinisztikus bittömb jobb lehet, mely csak 1 bitet igényel lehetséges elemenként. A hasítótáblák hely- és időelőnnyel is rendelkeznek, ha az ütközéseket figyelmen kívül hagyják, és csak azt tárolják, hogy az egyes helyek tartalmaznak-e elemet, ez esetben gyakorlatilag Bloom-szűrők lettek, ahol $k=1$.Sablon:Sfnp

A Bloom-szűrők érdekessége, hogy egy elem hozzáadásához vagy egy elem halmazba tartozásának ellenőrzéséhez szükséges idő konstans ($O(k)$), az elemszámtól független. Nincs más ilyen konstans adatszerkezet, de a ritka hasítótáblák átlagos elérési ideje kisebb lehet egyes Bloom-szűrőkénél. Hardverben azonban a Bloom-szűrő jobb, mivel a k keresés egymástól független és párhuzamossá tehető.

Helyhatékonysága megértéséhez fontos az általános Bloom-szűrő összehasonlítása a $k=1$ speciális esettel. Ha $k=1$, a hamis pozitívok arányának alacsonyan tartásához kevés bitnek kell 1-nek lennie, így a tömbnek nagynak kell lennie, hosszú 0-sorokkal. A tömb méretéhez viszonyított információtartalma alacsony. Az általános Bloom-szűrő ($k>1$ sokkal több 1 bitet enged alacsony hamispozitív-arány mellett. Megfelelő k és m esetén a bitek körülbelül fele 1 lesz, melyek nagyjából véletlenszerűek lesznek, minimalizálva a redundanciát és maximalizálva az információtartalmat.

Hamispozitív-arány

A $p$ hamispozitív-arány az $n$ elemszám és az m szűrőméret függvényében, optimális $k=\frac{m}{n}\ln 2$ hasítófüggvény feltételezésével.

Ha egy hasítófüggvény minden tömbbeli helyet azonos valószínűséggel választ ki, és m bites a tömb, annak valószínűsége, hogy egy bitet elem beillesztésekor nem változtat 1-re egy hasítófüggvény, $1-\frac{1}{m}$.

Ha k a hasítófüggvények száma, és egyikük közt sincs korreláció, annak valószínűsége, hogy egy bitet egy hasítófüggvény se állít 1-re: ${(1-\frac{1}{m})}^k.$

Felhasználva az $e^{-1}$-gyel kapcsolatos azonosságot: $\underset{m\to \mathrm{\infty }}{\lim }{(1-\frac{1}{m})}^m=\frac{1}{e}$, így nagy m esetén ${(1-\frac{1}{m})}^k={\left({(1-\frac{1}{m})}^m\right)}^{k/m}\approx e^{-\frac{k}{m}}.$

n elem esetén a 0 bit valószínűsége:

${(1-\frac{1}{m})}^{kn}\approx e^{-kn/m};$

tehát az 1 bité:

$1-{(1-\frac{1}{m})}^{kn}\approx 1-e^{-kn/m}.$

Egy, a halmazban nem lévő elem ellenőrzésekor a hasítófüggvénnyel számítótt k pozíció a fenti valószínűséggel 1. Annak valószínűsége hogy mindegyik 1, így az algoritmus hibásan állítja, hogy az elem a halmazban van, gyakran szerepel így:

$\epsilon ={(1-{[1-\frac{1}{m}]}^{kn})}^k\approx {(1-e^{-kn/m})}^k.$

Ez nem feltétlenül igaz, mert feltételezi az egyes bitek állapotának valószínűségének függetlenségét. Azonban feltéve, hogy ez közelítőleg igaz, a hamis pozitívok valószínűsége csökken m növekedésével, és nő n-ével (az elemszáméval).

A hamis pozitív tényleges valószínűsége függetlenség feltételezése nélkül:

$\frac{1}{m^{k(n+1)}}\sum _{i=1}^m{i}^{k}i!(\genfrac{}{}{0ex}{}{m}{i})\left\{\genfrac{}{}{0ex}{}{kn}{i}\right\}$

ahol a kapcsos zárójelek másodfajú Stirling-számokat jelölnek.

Egy ugyane közelítést adó elemzést adott meg Mitzenmacher és Upfal. Miután mind az n elem bekerült a szűrőbe, legyen q az m bitből a 0-k aránya (tehát a 0 bitek száma qm). Ekkor egy halmazon kívüli elem ellenőrzésekor a k hasítófüggvény bármelyike által adott pozíció esetén annak valószínűsége, hogy a talált bit 1, $1-q$. Így annak valószínűsége, hogy mind a k hasítófüggvény által talált bit 1, $(1-q{)}^k$. Továbbá q várt értéke annak valószínűsége, hogy egy adott helyt érintetlenül hagyott mind a k hasítófüggvény mind az n elemre, mely:

$E[q]={(1-\frac{1}{m})}^{kn}$.

Bebizonyítható a függetlenség feltételezése nélkül, hogy a q a várt értékhez nagy valószínűséggel nagyon közel van. Az Azuma–Hoeffding-egyenlőtlenségből bebizonyították, hogy:

$P(|q-E[q]|\ge \frac{\lambda }{m})\le 2\exp (-\frac{2{\lambda }^2}{kn})$

Innen kijelenthető, hogy a pontos hamispozitív-valószínűség:

$\sum _{t}P(q=t)(1-t{)}^k\approx (1-E[q]{)}^k={(1-{[1-\frac{1}{m}]}^{kn})}^k\approx {(1-e^{-kn/m})}^k.$

Optimális hasítófüggvényszám

A hasítófüggvények száma, k, pozitív egész kell, hogy legyen. Ettől eltekintve adott m és n esetén a legkevesebb hamis pozitívot adó k $k=\frac{m}{n}\ln 2.$

A szükséges bitszám, m adott n (elemszám), a kívánt hamispozitív-valószínűség, ε és optimális k esetén k fenti valószínűségbe helyettesítésével adható meg:

$\epsilon ={(1-e^{-(\frac{m}{n}\ln 2)\frac{n}{m}})}^{\frac{m}{n}\ln 2}$

vagyis:

$\ln \epsilon =-\frac{m}{n}{(\ln 2)}^2.$

Innen:

$m=-\frac{n\ln \epsilon }{(\ln 2{)}^2}$

Tehát az optimális bitszám:

$\frac{m}{n}=-\frac{{\log }_2\epsilon }{\ln 2}\approx -1,44{\log }_2\epsilon$

ahol a megfelelő k hasítófüggvényszám eltekintve attól, hogy egésznek kell lennie:

$k=-\frac{\ln \epsilon }{\ln 2}=-{\log }_2\epsilon .$

Tehát adott ε hamispozitív-valószínűség esetén a Bloom-szűrő hossza, m arányos a szűrt elemek számával, n-nel, a szükséges hasítófüggvények száma csak ε-tól függ.

Az $m=-\frac{n\ln \epsilon }{(\ln 2{)}^2}$ képlet 3 okból közelít. Először: az $1-\frac{1}{m}$-et $e^{-\frac{1}{m}}$-ként közelíti, mely jó aszimptotikus közelítés (egyre jobban közeledik, ahogy m →∞). Másodszor, feltételezi, hogy az, hogy a tesztelt bit 1, független attól, hogy bármely más bit 1. Végül feltételezi, hogy $k=\frac{m}{n}\ln 2$ egész.

Goel és Gupta azonban közelítések és feltételezések nélküli felső határt adtak, és bemutatták, hogy egy véges, m bites, n elemes és k hasítófüggvényes Bloom-szűrő hamispozitív-valószínűsége ($m>1$) legfeljebb $\epsilon \le {(1-e^{-\frac{k(n+0.5)}{m-1}})}^k.$

Ez azt jelenti, hogy a közelítő ${(1-e^{-\frac{km}{n}})}^k$ képlet legfeljebb fél elemmel többet és legfeljebb 1-gyel kevesebb bitet jelent.

Egy Bloom-szűrő elemszámának közelítése

Sablon:Harvtxt szerint egy Bloom-szűrő elemszáma az alábbi képlettel közelíthető:

$n^{*}=-\frac{m}{k}\ln [1-\frac{X}{m}],$

ahol $n^{*}$ a szűrő elemszámának becslése, m a szűrő hossza, k a hasítófüggvények száma, X az 1 bitek száma.

Halmazok uniója és metszete

A Bloom-szűrők halmazok kompakt megadására alkalmas. Gyakran használják két halmaz uniójának vagy metszetének elemszámának becslésére. Sablon:Harvtxt kimutatta, hogy két m hosszú Bloom-szűrő esetén elemszámuk közelítőleg $n(A^{*})=-\frac{m}{k}\ln [1-\frac{|A|}{m}]$ és $n(B^{*})=-\frac{m}{k}\ln [1-\frac{|B|}{m}].$

Uniójuk mérete közelítőleg $n(A^{*}\cup B^{*})=-\frac{m}{k}\ln [1-\frac{|A\cup B|}{m}],$ ahol $n(A\cup B)$ azon bitek száma, mely legalább az egyik szűrőben 1. Metszetük mérete közelítőleg $n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),$ a három képletet együtt használva.

Jellemzők

• Szemben egy hagyományos hasítótáblával, mely nyílt címzést használ ütközésfeloldáshoz, egy fix méretű Bloom-szűrő tetszőleges mennyiségű elemű halmazt jelölhet, azonban a hamispozitív-arány addig növekszik, míg a szűrőben minden bit 1 nem lesz, ahol már minden lekérdezés pozitív eredményt ad. Nyílt címzésű hasítással sosincs hamis pozitív, de a teljesítmény csökken, míg el nem éri a lineáris keresését.
• Azonos méretű és hasítófüggvény-halmazú Bloom-szűrők uniója és metszete bitenkénti „vagy” és „és” műveletekkel kapható meg. Az unióművelet veszteségmentes abban az értelemben, hogy az eredmény ugyanaz, mint a két halmaz uniójából képzett Bloom-szűrő. A metszetművelet eredményének hamispozitív-aránya nem nagyobb egyik kiinduló szűrőénél sem, de a két halmaz metszetéből készített szűrőénél nagyobb lehet.
• Bizonyos hasítókódok tekinthetők bevágott kártyák Bloom-szűrőiként. Ilyen például a Zatocoding, melyet Calvin Mooers hozott létre 1947-ben, ahol a kategóriahalmazt bevágások jelölik a kártyán, minden kategóriának véletlenszerű 4 bevágásos mintával.

Példák

• Az ecetmuslicák módosított Bloom-szűrőket használnak új szagok érzékelésére, további funkciókkal, melyek képesek a korábbiakhoz való hasonlóságát és az azonos szag korábbi érzete óta eltelt időt érzékelni.
• Egy tartalomszolgáltató, az Akamai Technologies szerverei Bloom-szűrőket használnak az egyszer keresett objektumok gyorsítótárban való tárolása ellen. Ezekről az Akamai kiderítette, hogy gyorsítótárának mintegy háromnegyedét adták. Egy Bloom-szűrő használata egy objektum második kérésének észlelésére, és csupán ekkori gyorsítótárazására megakadályozza az egyszer keresett objektumok gyorsítótárazását, csökkentve a tárhely terhelését.Sablon:Sfnp
• A Google Bigtable, az Apache HBase, az Apache Cassandra és a PostgreSQL Bloom-szűrőket használ nem létező sorok vagy oszlopok keresésének elkerüléséért, javítva az adatbázis-lekérdezések teljesítményét.
• A Google Chrome korábban Bloom-szűrőket használt káros URL-ek azonosítására. Ezeket eleinte egy helyi szűrőn ellenőrizték, és ennek pozitív eredménye esetén történt meg a teljes ellenőrzés (és a felhasználót ennek pozitív eredménye esetén figyelmeztette).
• A Microsoft Bing többszintű hierarchikus Bloom-szűrőket használ indexelőjéhez, a BitFunnelhez. A Bloom-szűrők alacsonyabb költséget jelentettek a korábbi, inverz fájlokon alapuló indexelésnél.
• A Squid Web Proxy gyorsítótára Bloom-szűrőket használ az összefoglalókhoz.Sablon:Sfnp
• A Bitcoin Bloom-szűrőket használt a pénztárca-szinkronizációhoz az ezzel kapcsolatos sebezhetőségek felfedezése előtt.
• A Venti archiválórendszer Bloom-szűrőket használ korábban tárolt adatok észlelésére.
• A SPIN model checker Bloom-szűrőket használ az elérhető állapottér követéséhez nagy ellenőrzési problémáknál.
• A Cascading analitikai keretrendszer Bloom-szűrőket használ aszimmetrikus összevonásokhoz, ahol az egyik adathalmaz sokkal nagyobb a másiknál.Sablon:Sfnp
• Az Exim levelezőprogram Bloom-szűrőket használ sűrűségkorlátozáshoz.
• A Medium Bloom-szűrőket használ korábban olvasott cikkek ajánlásának elkerülésére.
• Az Ethereum Bloom-szűrőket használ az Ethereum-blokklánc naplóihoz.
• A Grafana Tempo Bloom-szűrőket használ a lekérdezésteljesítmény javításához minden cellában való tárolásukkal. Ezekhez minden lekérdezéskor hozzáfér, hogy meghatározza a megadott kritériumoknak megfelelő adatokat.

Alternatívák

A Bloom-szűrőknek kulcsonként $1,44{\log }_2\frac{1}{\epsilon }$ bit kell, ahol $\epsilon$ a hamispozitív-arány. A feltétlenül szükséges hely ${\log }_2\frac{1}{\epsilon }$ bit,Sablon:Sfnp így a Bloom-szűrők helyigénye 44%-kal több egy megfelelő optimális adatszerkezetnél. Pagh és társai optimális helyigényű adatszerkezetet mutattak be, állandó, hamispozitív-aránytól független referenciahellyel, szemben a Bloom-szűrőkkel, ahol az alacsonyabb hamispozitív-arány több memória-hozzáférést jelent. Továbbá lehetséges benne a helyveszteség nélküli elemtörlés. Ugyanezek jellemzők a kakukkszűrőre Sablon:Harvtxt, melynek nyílt forrású változata elérhető.

Sablon:Harvtxt valószínűségi alapú szerkezetet ír le hasítótáblákon, hasítástömörítésen alapulva, melyet Sablon:Harvtxt sokkal pontosabbnak ír le egy Bloom-szűrőnél, ha minden optimálisan van beállítva. Dillinger és Manolios azonban rámutatnak, hogy adott Bloom-szűrő megfelelő pontossága széles körben vonzóvá teszi ismeretlen állapotterek valószínűségi elemzésekor. A hasítástömörítés így pontosan becsülhető összeadáskor használatos, azonban bár gyors a szoftver, de nem optimális a hardvernek a legrosszabb esetben lineáris hozzáférési idő miatt.

Sablon:Harvtxt bizonyos Bloom-szűrő-változatokat tanulmányoztak, melyek gyorsabbak vagy helyhatékonyabbak a hagyományos Bloom-szűrőknél. A gyors változat alapötlete, hogy a kulcsokhoz rendelt k értéket egy vagy két gyorsítótárblokknyi (általában 64 bájt) egységbe helyezi, feltehetően annak elkerülésével, hogy ne találjon meg a rendszer valamit a gyorsítótárban, javítja a teljesítményt. Ezek azonban a Bloom-szűrőnél 32%-kal több helyet használnak.

A helyhatékony változat egy minden kulcshoz a $[0;\frac{n}{\epsilon }]$ tartományban lévő értéket rendelő hasítófüggvényen alapul, ahol $\epsilon$ a kívánt hamispozitív-arány. A sorozatot ezután rendezi, majd Golomb-kódolással (vagy más tömörítési módszerrel) tömöríti, hogy nagyjából $n{\log }_2\frac{1}{\epsilon }$ bitet foglaljon. Egy kulcshoz való lekérdezéshez elég ellenőrizni, hogy a megfelelő érték benne van-e a szűrőben. Az egész szűrő kicsomagolása minden lekérdezéshez e változatot fölössé tenné, így az értéksort azonos méretű kis részekre bontja, melyek tömörítése külön történik. Lekérdezéskor átlagosan fél blokk csomagolandó ki. A kicsomagolási idő miatt e változat lassabb lehet a hagyományos Bloom-szűrőnél, azonban csak egy hasítófüggvény számítandó ki.

Egy újabb alternatíva a kakukkszűrő, mely a kakukkhasítás helyhatékony változatait használja. Ekkor hasítótábla jön létre, melyben nem maguk a kulcsok vagy az értékek vannak, hanem a kulcsok kis ujjlenyomatai (a hasítófüggvény értékei). Ha a kulcs keresésekor megvan a megfelelő ujjlenyomat, a kulcs valószínűleg a halmaz eleme. A kakukkszűrők frissíthetők – dinamikusan hozzáadhatók (kivéve, ha a tábla teli) és eltávolíthatók kulcsok.

Sablon:Harvtxt egy xor szűrőt mutat be, ahol az ujjlenyomatok egy tökéletes hasításhoz hasonló táblában vannak, memóriahatékonyabb ($1,23{\log }_2\frac{1}{\epsilon }$ bit kulcsonként) és gyorsabb szűrőt adva a Bloom- és a kakukkszűrőknél. A gyorsulás oka, hogy egy kereséshez 3-szor kell hozzáférni a memóriához, melyek párhuzamosan haladhatnak. Azonban a szűrőkészítés összetettebb, és a halmaz létrejötte után nem módosítható.

Kiterjesztések és alkalmazások

Több mint 60 Bloom-filter-változat van, továbbá sok tanulmány a területről, és sok alkalmazási mód (például Luo et al.). E változatok némelyike eléggé eltér az eredetitől, hogy az eredeti szerkezet és filozófia módosulatainak vagy sértéseinek tekintsék. A Bloom-szűrőket egyesítő kezelés, valamint a véletlen projekciók, tömörítő érzékelés és a helyszenzitív hasítás sincs befejezve (egy idegtudományi kísérlethez vö. Dasgupta, et al.).

Gyorsítótárszűrés

Az egytalálatos lapok gyorsítótárazását elkerülő Bloom-szűrő mintegy felezte a szükséges írási műveletek számát, csökkentve a meghajtók terhelését és feltehetően növelve teljesítményüket.Sablon:Sfnp

A tartalomszolgáltatók gyorsítótárakat használnak a tartalmak hatékonyabb, gyorsabb szolgáltatására. A Bloom-szűrők fontos alkalmazása annak hatékony meghatározása, mely webobjektumok tárolandók el a gyorsítótárakban. Egy gyorsítótárban szereplő URL-ek mintegy háromnegyedét a felhasználók csak egyszer érik el, így tárolásuk felesleges, mivel nem történik újabb hozzáférés. Ezek gyorsítótárazásának elkerülésére Bloom-szűrőt használnak. Egy webobjektumot gyorsítótárazása így akkor történik meg, ha már legalább egyszer hozzáfértek, vagyis az objektum a második kéréskor kerül a gyorsítótárba. A Bloom-szűrők használata így jelentősen csökkenti az írási műveletek számát, mivel a legtöbb egyszer felkeresett hely nem kerül be a gyorsítótárba. Továbbá a csak egyszer felkeresett lapok szűrése helyet szabadít fel a gyorsítótárban, növelve annak teljesítményét.Sablon:Sfnp

Hamis pozitívok elkerülése véges univerzumban

Kiss et al. olyan Bloom-szűrőt írtak le, melyek elkerülik a hamis pozitívokat a hamis negatívok nemléte mellett. Ez véges univerzumra használható, melyből a halmaz elemeit választjuk. Eppstein, Goodrich és Hirschberg nem adaptív kombinatorikai csoporttesztelési sémáján alapul. Szemben a Bloom-szűrővel, az elemeket determinisztikus, gyors és könnyen számítható függvények hasítják. A maximális hamispozitív-mentes halmazméret függ az univerzummérettől és a felhasznált memóriától.

Egy másik lehetőség egy kezdeti Bloom-szűrő hagyományos módú felépítése véges és felsorolható doménen, ahol minden hamis pozitív megtalálható, majd e listából egy második Bloom-szűrő felépíthető; a második szűrő hamis pozitívjai egy harmadik szűrővel találhatók meg így, stb. Mivel az univerzum véges, és a hamis pozitívok halmaza csökken minden lépésben, ez véges Bloom-szűrő-láncot eredményez, mely a véges doménen csak valós pozitívokat és valós negatívokat ad. A szűrőláncban annak ellenőrzése, hogy valami egy halmaz eleme-e, az első szűrő lekérdezése után pozitív eredmény esetén a második szűrő lekérdezése történik, stb. Ezt használja a CRLite, mely a Web PKI tanúsítvány-visszavonásokat elosztó módszere, és a tanúsítványátláthatóságot használja fel az érvényes tanúsítványok halmazának lezárására.

Számláló Bloom-szűrők

A számláló szűrők egy törlést Bloom-szűrőn lehetővé tevő mód a szűrő létrehozása nélkül. Benne a tömbbeli helyek több bites számlálóként működnek. A hagyományos Bloom-szűrők tekinthetők 1 bites számlálójú számláló szűrőkként. A Sablon:Harvtxt tanulmány vezette be őket.

Az elemhozzáadás 1-gyel növeli a számlálók értékeit, a keresés megtekinti, hogy a kívánt számlálók egyike se 0, a törlés csökkenti a megfelelő számlálók értékét 1-gyel.

A számlálók túlcsordulása lehet itt probléma, így azoknak elég nagynak kell lenniük, hogy ritka legyen az eset. Ekkor azonban az 1 hozzáadásának és elvételének a számlálót a legnagyobb értéken kell hagyniuk a Bloom-szűrő tulajdonságainak megmaradásához.

A számlálók mérete általában 3 vagy 4 bit, így a számláló Bloom-szűrők 3–4-szer annyi helyet használnak a statikusaknál. Ezzel szemben a Sablon:Harvtxt és Sablon:Harvtxt adatszerkezeteiben lehetséges törlés, de kevesebb helyet használnak a Bloom-szűrőnél.

További gond a korlátozott méretezhetőség. Mivel a tábla nem bővíthető, az egyidejűleg tárolt kulcsok maximális száma előre ismerendő. A megadott kapacitás túllépésekor a hamis pozitívok aránya a kulcsok hozzáadásával gyorsan nő.

Sablon:Harvtxt d-balra hasításon alapuló adatszerkezetet vezetett be, mely hasonlóan működik a számláló Bloom-szűrőkhöz, de csak mintegy feleannyi helyet használ, és jobban méretezhető. A megadott méret túllépésekor a kulcsok kétszer akkora hasítótáblába helyezhetők át.

Sablon:Harvtxt helyhatékony változata is használható számláló szűrők támogatására hozzáadással és törléssel.

Sablon:Harvtxt általános módszert vezetett be változó növekedésekkel, mely jelentősen javítja a hamispozitív-arányt a számláló Bloom-szűrők és változataik esetén, a törlés támogatásával. Szemben a számláló Bloom-szűrőkkel, minden számláló hasított változóval nő az 1 helyett. Egy elem lekérdezésekor a pontos számlálóértékek vannak figyelembe véve. Ha a számláló értéke nem éri el az elemhez tartozó értéket, az elem nincs a halmazban.

Kim et al. (2019) kimutatta, hogy a számláló Bloom-szűrők hamispozitív-aránya 1-től $k_{\text{opt}}$ hasítófüggvényig csökken, ettől kezdve végtelenig nő, és $k_{\text{opt}}$ a számlálási határtól függ.

Elosztott összegzés

A Bloom-szűrők elosztott adatszerkezetekben is elrendezhetők teljesen elosztott összegzőfüggvényekhez. Ez az összesített méréseket helyileg elérhetővé teszi a hálózat minden pontján központi egység igénye nélkül.Sablon:Sfnp

Elosztott Bloom-szűrők

Elosztott egypróbás Bloom-szűrőő duplikátumészleléshez hamispozitív-aránnyal: 6 elem 3 PE közt van elosztva, 4 hosszú bittömbökkel. Az első lépésben az 1. PE 2-szer kapja meg a 2-es hasítási értéket, és visszaküldi a 2.-nek vagy a 3.-nak, attól függően, melyik küldte később. A PE, mely megkapja a 2-es értéket megkeresi az azzal az értékkel rendelkező elemet, és lehetséges duplikátumként észleli.

A párhuzamos Bloom-szűrők a több feldolgozóelem előnyeit tudják kihasználni a párhuzamos „semmi nincs megosztva” eszközökön. Fő akadály a rendezetlen adat szervezése és közlése, mely általában egyenlően oszlik el a PE-k közt kezdetben vagy behelyezésekkor. Az adat rendezéséhez két megközelítés használható, vagy minden adathoz tartozó (replikáló) Bloom-szűrőt, vagy minden adatról szóló Bloom-szűrőt, melyeknek egy-egy egyenlő részét tartalmazza egy PE. Mindkét esetben „egypróbás” szűrőt használnak, mely 1 hasítófüggvényt számít, elemenként egy 1 bittel, csökkentve a közölt adat terjedelmét.

Az elosztott szűrők létrehozásakor először a helyi PE-n történik minden elem hasítása, majd helyben történik a hasítási értékek szerinti rendezés. Ez például vödörrendezéssel megoldható lineáris időben, és lehetővé teszi a lokális duplikátumészlelést. A rendezés az értékeket a megfelelő PE-vel való csoportosításhoz való, így csoportonként létrejön egy szűrő. A szűrők kódolása után történik minden szűrő elküldése a hasítási értékekért felelő PE-hez. A p. PE felel a $p(\frac{s}{|\text{PE}|})$ és a $(p+1)(\frac{s}{|\text{PE}|})$ közti értékekért, ahol s a szűrő teljes mérete. Mivel minden elem hasítása egyszer történik meg, így 1 bit értéke lesz 1, az elem szűrőbe kerülésének ellenőrzéséhez csak az elem hasítási értékéért felelő PE-t kell vizsgálni. Az egyszeri beillesztések azért is végezhetők hatékonyan, mert csak egy PE szűrőjén kell változtatni, szemben a replikáló Bloom-szűrőkhöz, ahol minden PE szűrője frissül. A teljes szűrő PE-k közti elosztása nagyobb szűrőméretet tesz lehetővé, így nagyobb kapacitást és kevesebb hamis pozitívot is lehetővé téve. Az elosztott szűrők felhasználhatók duplikátumészlelő algoritmusok javítására a „legegyedibb” elemek kiszűrésével. Ezek kiszámíthatók csak a hasítási értékek közlésével, szemben az elemekével, melyek sokkal nagyobbak, és eltávolításuk csökkenti a duplikátumészlelés terhelését.

A hasítási értékek közlésekor a PE-k egynél több csomagban azonos biteket keresnek, ami azt jelenti, hogy két elem hasítási értéke azonos, így duplikátumok lehetnek. Ekkor a bit helyét tartalmazó üzenetet, mely a lehetséges duplikátum hasítási értéke, küldi el a PE-knek, melyek e bitet tartalmazó csomagot küldték. Ha több helyet küld egy küldő egy PE-nek, előnyös lehet a helyek kódoolása is. Azon elemek, melyek hasítási értéke nem érkezett meg, nem duplikátumok, így nem történik további kiértékelésük, a többi elemeknél újraosztó algoritmus használható. Először azon elemek, melyek hasítási értéke visszaérkezett, visszakerülnek a PE-hez, mely a hasítási értékét adta. Minden elem és duplikátuma így egy PE-re kerül. Ezután minden PE szakaszos duplikátumészlelést végez a visszakapott elemeken, melyek a kezdetieknek csak egy része. Egy adott hamispozitív-arány megengedésével a közölt információ tovább csökkenhet, mivel a PE-knek nem kell két hasítási értékkel rendelkező elemeket küldeni, helyette az ismétlődő hasítási értékek egyszerűen ismétlésnek jelölhetők, így a hamispozitív-arány az ismétlésészlelésnél a használt szűrőével egyezik meg.

A „legegyedibb” elemek szűrése többször is megismételhető a hasítófüggvény változtatásával minden lépésben. Egy lépés esetén kis hamispozitív-arányt kell elérni, azonban ha a lépések ismétlődnek, az első lépés hamispozitív-aránya nagyobb lehet, míg a későbbieknek is lehet nagyobb, de ezek kevesebb elemen működnek, mivel sokat a korábbiak eltávolítottak. Bár 2-nél több ismétlés tovább csökkentheti a közölt információkat kevés ismétlődés esetén, a haszon általában csekély.

A replikáló Bloom-szűrők adataikat hiperkocka-algoritmussal rendezik. Először minden PE kiszámítja és eltárolja a hozzá tartozó elemek szűrőjét. Egy ciklus ismétlésével, ahol az i. lépésben elküldik a PE-k a saját i dimenziós szűrőjüket, és egyesítik a megkapott szűrőt a saját szűrővel, megkétszerezhető a szűrők elemszáma minden ismétlésben. Miután elküldték és megkapták a PE-k mind a $\log |\text{PE}|$ dimenzióban, minden PE a globális Bloom-szűrőt tartalmazza.

A replikáló Bloom-szűrők hatékonyak, ha a lekérdezésszám sokkal nagyobb az elemszámnál, nagyjából $\frac{|\text{PE}||\text{Elemek}|}{{\log }_{f^{+}}|\text{PE}|}$ elérésnél azonos a hatékonyságuk az elosztott szűrőkkel, ahol $f^{+}$ a hamispozitív-arány.

Adatszinkronizáció

A Bloom-szűrők használhatók közeli adatszinkronizációhoz.. Számláló Bloom-szűrők használhatók két halmaz különbségeinek számítására.

Bloom-szűrők adatfolyamokhoz

A Bloom-szűrők használhatók adatfolyamokhoz is. Például Sablon:Harvtxt javasolt stabil Bloom-szűrőket, számláló Bloom-szűrővel, ahol egy új elem hozzáadása a megfelelő számokat c értékre állítja, és csak egy fix s számláló csökken 1-gyel, így a memória nagyrészt új elemekből áll (egy N számlálós SBF-ben egy elem élettartama nagyjából $\frac{cs}{N}$). Egy másik megoldás az öregedő Bloom-szűrő, mely két szűrőből áll, melyek a memória felét töltik ki: ha egyikük teli, a másik kiürül, és ezen üres szűrőhöz kerülnek új elemek.

Azonban kiderült, hogy szűrőtől függetlenül n elem esetén a hamis pozitívok (FP) és a hamis negatívok (FP) valószínűségének arányának alsó határa:

$FP+FN\ge 1-\frac{1-{(1-\frac{1}{L})}^m}{1-{(1-\frac{1}{L})}^n}$,

ahol L a lehetséges elemek száma (az ábécéméret), m a memóriaméret (bitben), feltéve, hogy $n>m$. Tehát elegendően nagy L esetén $\underset{n\to \mathrm{\infty }}{\lim }FP+FN=1$, ami egy véletlen szűrőnek felel meg. Tehát elég elem hozzáadása után a memóriában tároláshoz túl nagy ábécé esetén (ami a valószínűségi alapú szűrők esetén gyakori feltételezés) lehetetlen egy szűrőnek jobban teljesítenie a véletlenségnél. Ez csökkenthető úgy, ha egy szűrő csak az adatfolyam egy részén működik, ez esetben az n kitevő w-re módosul, mely 1-től eltérő eredményt ad, ha w nem túl kicsi.

Bloomier-szűrők

Sablon:Harvtxt a Bloom-szűrők általánosítását írta le, melyekben asszociálható egy érték a behelyezett elemekkel, asszociatív tömböt létrehozva. Hasonlóan a Bloom-szűrőkhöz, ezek a kis helytöbbletet kis hamispozitív-aránnyal érik el. Ez esetben a hamis pozitív eredmény kiadása a leképezésben nem szereplő kulcs esetén. A leképezés hibás értéket nem ad vissza benne szereplő kulcs esetén.

Kompakt közelítők

Sablon:Harvtxt egy hálóalapú általánosítást javasolt. A kompakt közelítő minden kulcshoz egy hálóelemet rendel (a Bloom-szűrők ez esetben kételemű Boole-hálók). Bittömb helyett hálóelemtömbjük van. Kulcs és hálóelem közti hozzárendelés hozzáadásakor kiszámítják a hálóelemhez rendelt k tömbhely jelenlegi tartalmainak maximumát. Kulcshoz rendelt érték olvasásakor kiszámítják a kulcshoz rendelt k helyhez tartozó érték minimumát. Az eredmény az eredeti értéket felülről becsüli.

Párhuzamos particionált Bloom-szűrők

Önálló tömböt használ a hasítófüggvényeknek, lehetővé téve a lekérdezésekhez és a hozzáadásokhoz is párhuzamos hasítófüggvény-számításokat.

Méretezhető Bloom-szűrők

Sablon:Harvtxt olyan Bloom-szűrő-változatot javasolt, mely az elemszámhoz képes igazodni minimális hamispozitív-valószínűséggel. Ez hagyományos Bloom-szűrők sorozatain alapul növekvő kapacitással és kisebb hamispozitív-valószínűségekkel, így egy maximális valószínűség állítható előre be elemszámtól függetlenül.

Térbeli Bloom-szűrők

A térbeli Bloom-szűrőket eredetileg Sablon:Harvtxt javasolta helyadatokat tároló adatstruktúraként, különösen helyadatvédelemhez szükséges kriptográfiai protokollok esetén. Több halmazt tudnak egy adatstruktúrában tárolni, lehetővé téve számos esetben használatukat.Sablon:Sfnp Lekérdezhető egy elemről, hogy része-e egy halmaznak, és a hamispozitív-arány a halmaztól függ: a szűrőkbe kerülő első halmazokéi magasabbak, mint a későbbiekéi.Sablon:Sfnp Ez lehetővé teszi a halmazok fontossági sorrendjének felállítását, ahol a fontosabb elemeket tartalmazó halmazok megőrizhetők.

Réteges Bloom-szűrők

A réteges Bloom-szűrők több Bloom-szűrő-rétegből állnak. Képesek követni, hányszor van hozzáadva egy elem az azt tartalmazó rétegek számával. Egy ellenőrző művelet jellemzően a legmélyebb réteget adja vissza, ahol az elem volt.Sablon:Sfnp

Csillapított Bloom-szűrők

Csillapított Bloom-szűrő példája: „11010” minta keresése n₁ csomóponttól.

Egy D mélységű csillapított Bloom-szűrő tekinthető D egyszerű szűrő tömbjének. A hálózati szolgáltatások tekintetében minden csomópont egyszerű és csillapított szűrőket egyaránt tartalmaz. Az egyszerű szűrő megmutatja, mely szolgáltatásokhoz lehet a csomópontból hozzáférni, az i. szintű csillapított szűrő pedig hogy milyenek érhetők el az i élre lévő csomóponttól. Az i. érték az i élre lévő csomópontok helyi szűrőinek uniója.Sablon:Sfnp

A képen lévő kis hálózat példáján egy A szolgáltatás keresése van, melynek azonosítójának kódja a 0, 1 és 3 értékek (11010 minta). Legyen n₁ a kezdőpont. Először a szűrő ellenőrzi, hogy A-t kínálja-e n₁ a helyi szűrője ellenőrzésével. Mivel nem egyeznek a minták, a csillapított szűrővel kiválasztjuk n₂-t. Ez se kínálja A-t, de van olyan szomszédja, mely igen. Így kiderül, hogy n₃ kínálja A-t, így az a cél.Sablon:Sfnp

Többrétegű csillapított Bloom-szűrőkkel 1-nél több élre lévő szolgáltatások is találhatók a szűrő telítése nélkül a távolabbi források bitjeinek csillapításával.Sablon:Sfnp

Kémiaiszerkezet-keresés

A nagy kémiai adatbázisok kereséséhez gyakran használnak Bloom-szűrőket. A legegyszerűbb esetben a szűrőhöz adott elemek (az ujjlenyomat) a molekulában lévő atomok rendszámai, vagy egy, az atomok rendszámán és kötéseik számán és típusán alapuló hasítási érték. Ez eset a hasznossághoz túl egyszerű. Az összetettebb szűrők atomszámokat, nagyobb szerkezeti jellemzőket, például karboxilcsoportokat és gráftulajdonságokat, például gyűrűszámot is figyelembe vesznek. A hasításalapú ujjlenyomatokban atomi és kötéstulajdonságokon alapuló hasítófüggvényt használnak egy részgráf véletlenszerűszám-generátori bemenetté alakításában és a szűrő bitjeit beállító első kimeneti értékekhez.

Az 1940-es évek végén kezdtek molekuláris ujjlenyomatokat használni lyukkártyán keresett kémiai szerkezetekhez. Azonban csak 1990 körül vezetett be a Daylight Chemical Information Systems, Inc. a bitgeneráláshoz hasítófüggvény-alapú módszert előszámított tábla helyett. Szemben a szótári megközelítéssel, a hasítómódszer korábban nem látott szerkezeti részekhez rendelhetett biteket. Az 1990-es évek elején az „ujjlenyomat” fogalma eltért a „szerkezeti jellemzőktől”, de ez kibővült: már tartalmazza az összehasonlításhoz használható legtöbb molekuláris jellemzőt, például a szerkezeti jellemzőket vagy a 3D-s ujjlenyomatokat. Szemben a Bloom-szűrőkkel, e módszerben lehetséges a jellemzőnként hozzárendelt bitek számának méretfüggősége, míg a legtöbb Daylight-szerű ujjlenyomat fix számú bitet használ jellemzőnként, így ezek Bloom-szűrőként működnek. Az eredeti Daylight-ujjlenyomatok hasonlóság-ellenőrzési és vizsgálati célokra is használhatók. Számos más ujjlenyomattípus, például az ECFP2, hasonlóság-ellenőrzésre használható, vizsgálatra nem, mivel helyi környezeti jellemzőket is tartalmaznak, melyek vizsgálatkor hamis negatívokat ad. Még ha azonos módon is készültek, nem Bloom-szűrők, mert nem használhatók szűrésre.

Források

• Sablon:Cite book
• Sablon:Cite conference
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite report
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference. Nyílt forrású megvalósítás a GitHubon.
• Sablon:Cite conference. Előzetes változat jelent meg a SIGCOMM '98-on.
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite conference
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite journal. A prototípus GitHubon elérhető.
• Sablon:Cite book
• Sablon:Cite conference
• Sablon:Cite conference
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite book