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 ${\displaystyle x\in X}$ elemek leképezését jelenti ${\displaystyle y=h(x)\in Y}$-ra, majd ${\displaystyle x'\in X}$ vizsgálatát annak vizsgálatával, hogy ${\displaystyle y'=h(x')\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 500 000 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.^[1]

Á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.^[2]

Az algoritmus leírása

Az üres Bloom-szűrő ${\displaystyle m}$ 0 bitből álló sor. Ezenkívül szükséges ${\displaystyle 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 ${\displaystyle \varepsilon }$ 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 ${\displaystyle 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ő.^[3] (Különösen (Dillinger & Manolios 2004b) 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

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 ${\displaystyle k=1}$.^[4]

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 (${\displaystyle 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 ${\displaystyle k=1}$ speciális esettel. Ha ${\displaystyle 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ő (${\displaystyle 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,^[5] melyek nagyjából véletlenszerűek lesznek, minimalizálva a redundanciát és maximalizálva az információtartalmat.

Hamispozitív-arány

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, ${\displaystyle 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: ${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

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

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

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

tehát az 1 bité:

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{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:

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{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:

${\displaystyle {\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}}$

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

Egy ugyane közelítést adó elemzést adott meg Mitzenmacher és Upfal.^[7] 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, ${\displaystyle 1-q}$. Így annak valószínűsége, hogy mind a k hasítófüggvény által talált bit 1, ${\displaystyle (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:

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{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:^[8]

${\displaystyle P(\left|q-E[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-{\frac {2\lambda ^{2}}{kn}})}$

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

${\displaystyle \sum _{t}P(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{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 ${\displaystyle 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:

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}}$

vagyis:

${\displaystyle \ln \varepsilon =-{\frac {m}{n}}\left(\ln 2\right)^{2}.}$

Innen:

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

Tehát az optimális bitszám:

${\displaystyle {\frac {m}{n}}=-{\frac {\log _{2}\varepsilon }{\ln 2}}\approx -1.44\log _{2}\varepsilon }$

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

${\displaystyle k=-{\frac {\ln \varepsilon }{\ln 2}}=-\log _{2}\varepsilon .}$

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, s a szükséges hasítófüggvények száma csak ε-tól függ.^[9]

Az ${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$ képlet 3 okból közelít. Először: az ${\displaystyle 1-{\frac {1}{m}}}$-et ${\displaystyle 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 ${\displaystyle k={m \over n}\ln 2}$ egész.

Goel és Gupta^[10] 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 (${\displaystyle m>1}$) legfeljebb ${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

Ez azt jelenti, hogy a közelítő ${\displaystyle \left(1-e^{-{km \over n}}\right)^{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

(Swamidass & Baldi 2007) szerint egy Bloom-szűrő elemszáma az alábbi képlettel közelíthető:

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

ahol ${\displaystyle 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. (Swamidass & Baldi 2007) kimutatta, hogy két m hosszú Bloom-szűrő esetén elemszámuk közelítőleg ${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$ és ${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

Uniójuk mérete közelítőleg ${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],}$ ahol ${\displaystyle 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 ${\displaystyle 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ázattal, 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.^[11]
• 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.^[12]
• A Google Bigtable, az Apache HBase, az Apache Cassandra és a PostgreSQL^[13] 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.^[14]
• 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).^[15][16]
• 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.^[17]
• A Squid Web Proxy gyorsítótára Bloom-szűrőket használ az összefoglalókhoz.^[18]
• 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.^[19][20]
• A Venti archiválórendszer Bloom-szűrőket használ korábban tárolt adatok észlelésére.^[21]
• 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.^[22]
• A Cascading analitikai keretrendszer Bloom-szűrőket használ aszimmetrikus összevonásokhoz, ahol az egyik adathalmaz sokkal nagyobb a másiknál.^[23]
• Az Exim levelezőprogram Bloom-szűrőket használ sűrűségkorlátozáshoz.^[24]
• A Medium Bloom-szűrőket használ korábban olvasott cikkek ajánlásának elkerülésére.^[25]
• 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.^[26]

Alternatívák

A Bloom-szűrőknek kulcsonként ${\displaystyle 1{,}44\log _{2}{\frac {1}{\varepsilon }}}$ bit kell, ahol ${\displaystyle \varepsilon }$ a hamispozitív-arány. A feltétlenül szükséges hely ${\displaystyle \log _{2}{\frac {1}{\varepsilon }}}$ bit,^[27] í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 (Fan et al. 2014), melynek nyílt forrású változata elérhető.

(Stern & Dill 1996) valószínűségi alapú szerkezetet ír le hasítótáblákon, hasítástömörítésen alapulva, melyet (Dillinger & Manolios 2004b) 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.

(Putze, Sanders & Singler 2007) 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 ${\displaystyle \left[0;{\frac {n}{\varepsilon }}\right]}$ tartományban lévő értéket rendelő hasítófüggvényen alapul, ahol ${\displaystyle \varepsilon }$ 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 ${\displaystyle n\log _{2}{\frac {1}{\varepsilon }}}$ 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.

(Graf & Lemire 2020) 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 (${\displaystyle 1{,}23\log _{2}{\frac {1}{\varepsilon }}}$ 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.).^[28] 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.^[28] 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.).^[29]

Gyorsítótárszűrés

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.^[12]

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

Kiss et al.^[30] 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.^[31]

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 (Fan et al. 2000) 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 (Pagh, Pagh & Rao 2005) és (Fan et al. 2014) 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ő.

(Bonomi et al. 2006) 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ázatba helyezhetők át.

(Putze, Sanders & Singler 2007) helyhatékony változata is használható számláló szűrők támogatására hozzáadással és törléssel.

(Rottenstreich, Kanizo & Keslassy 2012) á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 ${\displaystyle k_{\text{opt}}}$ hasítófüggvényig csökken, ettől kezdve végtelenig nő, és ${\displaystyle k_{\text{opt}}}$ a számlálási határtól függ.^[32]

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.^[33]

Elosztott Bloom-szűrők

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.^[34] 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 ${\displaystyle p({\frac {s}{|{\text{PE}}|}})}$ és a ${\displaystyle (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^[35] 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ó.^[36] 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.^[37] 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 ${\displaystyle \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 ${\displaystyle {\frac {|{\text{PE}}||{\text{Elemek}}|}{\log _{f^{+}}|{\text{PE}}|}}}$ elérésnél azonos a hatékonyságuk az elosztott szűrőkkel, ahol ${\displaystyle f^{+}}$ a hamispozitív-arány.

Adatszinkronizáció

A Bloom-szűrők használhatók közeli adatszinkronizációhoz ((Byers et al. 2004)). Számláló Bloom-szűrők használhatók két halmaz különbségeinek számítására ((Agarwal & Trachtenberg 2006)).

Bloom-szűrők adatfolyamokhoz

A Bloom-szűrők használhatók adatfolyamokhoz is. Például (Deng & Rafiei 2006) 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 ${\displaystyle {\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.^[38]

Azonban kiderült,^[39] 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:

${\textstyle \scriptstyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$,

ahol L a lehetséges elemek száma (az ábécéméret), m a memóriaméret (bitben), feltéve, hogy ${\displaystyle n>m}$. Tehát elegendően nagy L esetén ${\displaystyle \lim _{n\to \infty }\scriptstyle 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

(Chazelle et al. 2004) 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

(Boldi & Vigna 2005) 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.^[40]

Méretezhető Bloom-szűrők

(Almeida et al. 2007) 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 (Palmieri, Calderoni & Maio 2014) 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.^[41] 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.^[42] 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.^[43]

Csillapított Bloom-szűrők

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.^[44]

A képen lévő kis hálózat példáján egy A szolgáltatás keresése van, melynaek 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.^[45]

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.^[44]

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áblázat 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.

Jegyzetek

Fordítás

Ez a szócikk részben vagy egészben a Bloom filter című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Approximating the number of differences between remote sets, 2006 IEEE Information Theory Workshop, 217. o.. DOI: 10.1109/ITW.2006.1633815 (2006. június 3.). ISBN 978-1-4244-0035-5 
• (2007) „15th international Conference on Networks (ICON-2007)”.. doi:10.1109/ICON.2007.4444089. 
• (2007) „Scalable Bloom Filters”. Information Processing Letters 101 (6), 255–261. o. DOI:10.1016/j.ipl.2006.10.007.  
• Apache Software Foundation. The Apache HBase Reference Guide, Revision 0.94.27 (2012) 
• Bloom, Burton H. (1970). „Space/Time Trade-offs in Hash Coding with Allowable Errors”. Communications of the ACM 13 (7), 422–426. o. DOI:10.1145/362686.362692.  
• (2002) „Bloom Filters — A Tutorial, Analysis, and Survey”, 1–31. o, Kiadó: Dalhousie University Faculty of Computer Science.  
• (2005) „Mutable strings in Java: design, implementation and lightweight text-search algorithms”. Science of Computer Programming 54 (1), 3–23. o. DOI:10.1016/j.scico.2004.05.003.  
• Algorithms – ESA 2006, 14th Annual European Symposium, Lecture Notes in Computer Science, 684–695. o.. DOI: 10.1007/11841036_61 (2006). ISBN 978-3-540-38875-3 
• (2005) „Network Applications of Bloom Filters: A Survey”. Internet Mathematics 1 (4), 485–509. o. DOI:10.1080/15427951.2004.10129096.  
• (2004) „Informed content delivery across adaptive overlay networks”. IEEE/ACM Transactions on Networking 12 (5), 767. o. DOI:10.1109/TNET.2004.836103.  
• (2015) „Location privacy without mutual trust: The spatial Bloom filter”. Computer Communications 68, 4–16. o. DOI:10.1016/j.comcom.2015.06.011. ISSN 0140-3664.  
• (2018) „Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols”. IEEE Transactions on Information Forensics and Security 13, 1710–1721. o. DOI:10.1109/TIFS.2018.2799486. ISSN 1556-6013.  
• (2006) „Seventh Symposium on Operating System Design and Implementation”.. 
• (2008) „Algorithms: ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings”. 5193, Springer. doi:10.1007/978-3-540-87744-8_22. 
• (2004) „Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms”.: 30–39. [2007. január 6-i dátummal az eredetiből archiválva]. Hozzáférés: 2023. augusztus 3. 
• (2003) „Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data”.: 241–252. [2021. március 10-i dátummal az eredetiből archiválva]. doi:10.1145/872757.872787. Hozzáférés: 2023. augusztus 3. 
• (2006) „Proceedings of the ACM SIGMOD Conference”.: 25–36. 
• (2006) „Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems”.. [2007. február 2-i dátummal az eredetiből archiválva]. doi:10.1145/1185347.1185356. Hozzáférés: 2023. augusztus 3. 
• (2008) „Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Track A: Algorithms, Automata, Complexity, and Games”. 5125, Springer. doi:10.1007/978-3-540-70575-8_32. 
• (2004a) „Proceedings of the 11th International Spin Workshop on Model Checking Software”., Springer-Verlag, Lecture Notes in Computer Science 2989. 
• (2004b) „Proceedings of the 5th International Conference on Formal Methods in Computer-Aided Design”., Springer-Verlag, Lecture Notes in Computer Science 3312. 
• (2006) „CoNEXT 06 – 2nd Conference on Future Networking Technologies”.. [2009. május 17-i dátummal az eredetiből archiválva]. Hozzáférés: 2023. augusztus 3. 
• (2007) „Algorithms and Data Structures, 10th International Workshop, WADS 2007”. 4619: 637–648, Springer-Verlag. 
• (2014) „Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT '14)”.: 75–88. doi:10.1145/2674005.2674994. . Nyílt forrású megvalósítás a GitHubon.
• (2000) „Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol”. 8: 281–293. doi:10.1109/90.851975. . Előzetes változat jelent meg a SIGCOMM '98-on.
• (2010) „Small subset queries and bloom filters using ternary associative memories, with applications”. ACM SIGMETRICS Performance Evaluation Review 38, 143. o. DOI:10.1145/1811099.1811056.  
• (2020) „Xor Filters”. ACM Journal of Experimental Algorithmics 25, 1–16. o. DOI:10.1145/3376122.  
• (2018) „On the analysis of Bloom filters”. Information Processing Letters 129, 35–39. o. DOI:10.1016/j.ipl.2017.09.004.  
• (2006) „Algorithms – ESA 2006, 14th Annual European Symposium”. 4168: 456–467, Springer-Verlag, Lecture Notes in Computer Science 4168. [2009. január 31-i dátummal az eredetiből archiválva]. doi:10.1007/11841036. Hozzáférés: 2023. augusztus 3. 
• (2009) „Traffic and QoS Management in Wireless Multimedia Networks”. COST 290 Final Report, 111. o.  
• (2000) „Oceanstore: An architecture for global-scale persistent storage”. ACM SIGPLAN Notices, 190–201. o. [2012. március 11-i dátummal az eredetiből archiválva]. (Hozzáférés: 2023. augusztus 3.)  
• (2015. július) „Algorithmic nuggets in content delivery”. SIGCOMM Computer Communication Review 45 (3), 52–66. o. DOI:10.1145/2805789.2805800.  
• Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 107–112. o. (2005). ISBN 9780521835404 
• Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, 104–111. o.. DOI: 10.1145/1060590.1060606 (2005). ISBN 978-1581139600 
• Mullin, James K. (1990). „Optimal semijoins for distributed database systems”. IEEE Transactions on Software Engineering 16 (5), 558–560. o. DOI:10.1109/32.52778.  
• (2005) „Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms”.. 
• (2014) „Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014)”. 8957: 16–36, Springer-Verlag, Lecture Notes in Computer Science. doi:10.1007/978-3-319-16745-9_2. 
• Porat, Ely (2009). „Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18–23, 2009, Proceedings”. 5675: 263–273, Springer. doi:10.1007/978-3-642-03351-3_25. 
• (2013) „A generic and adaptive aggregation service for large-scale decentralized networks”. Complex Adaptive Systems Modeling 1 (19), 19. o. DOI:10.1186/2194-3206-1-19.  . A prototípus GitHubon elérhető.
• Experimental Algorithms, 6th International Workshop, WEA 2007 [archivált változat], Lecture Notes in Computer Science. Springer-Verlag, Lecture Notes in Computer Science 4525, 108–121. o.. DOI: 10.1007/978-3-540-72845-0 (2007). ISBN 978-3-540-72844-3. Hozzáférés ideje: 2023. augusztus 3. [archiválás ideje: 2007. június 23.] 
• (2012) „31st Annual IEEE International Conference on Computer Communications, 2012, Infocom 2012”.: 1880–1888. [2022. december 27-i dátummal az eredetiből archiválva]. doi:10.1109/INFCOM.2012.6195563. Hozzáférés: 2023. augusztus 3. 
• (2003) „36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, MICRO-36”.: 399–410. [2007. január 14-i dátummal az eredetiből archiválva]. doi:10.1109/MICRO.2003.1253244. Hozzáférés: 2023. augusztus 3. 
• (2003) „Efficient PDA Synchronization”. IEEE Transactions on Mobile Computing 2 (1), 40. o. DOI:10.1109/TMC.2003.1195150.  
• Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification: IFIP TC6/WG6.1 Joint International Conference. Chapman & Hall, IFIP Conference Proceedings, 333–348. o. (1996) 
• (2007) „Mathematical correction for fingerprint similarity measures to improve chemical retrieval”. Journal of Chemical Information and Modeling 47, 952–964. o. DOI:10.1021/ci600526a. PMID 17444629.  
• Wessels, Duane. 10.7 Cache Digests, Squid: The Definitive Guide, 1st, O'Reilly Media, 172. o. (2004. január 1.). ISBN 978-0-596-00162-9 „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.” 
• (2012) „IEEE Communications Surveys & Tutorials, no. 1.” 14, 131–155. o.  
• Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010), V1–586–V1–591. o.. DOI: 10.1109/ICACTE.2010.5578947 (2010). ISBN 978-1-4244-6539-2 

További információk