Kukačkový filtr - Cuckoo filter

A kukačkový filtr je prostorově efektivní pravděpodobnostní datová struktura který se používá k testování, zda živel je členem a soubor, jako Bloomův filtr dělá. Falešně pozitivní shody jsou možné, ale falešné negativy nejsou - jinými slovy, dotaz vrátí buď „možná v sadě“, nebo „rozhodně není v sadě“. Filtr kukačky může také mazat existující položky, což filtry Bloom nepodporují. Navíc u aplikací, které ukládají mnoho položek a cílí na mírně nízkou míru falešně pozitivních výsledků, mohou kukačkové filtry dosáhnout menšího prostoru nad hlavou než filtry Bloom optimalizované pro prostor.^[1]

Kukačkové filtry byly poprvé popsány v roce 2014.^[2]

Popis algoritmu

Kukačkový filtr používá a ${ displaystyle n}$-way set-asociativní hash tabulka založená na kukačka hash k uložení otisků prstů všech položek (do každého segmentu hashtable lze uložit až ${ displaystyle n}$ Zejména dva potenciální segmenty v tabulce pro danou položku ${ displaystyle x}$ požadované hašováním kukaček se počítají z následujících dvou hashových funkcí (označovaných jako hašování kukačky s částečným klíčem^[2]):

${ displaystyle h_ {1} (x) = { text {hash}} (x)}$

${ displaystyle h_ {2} (x) = h_ {1} (x) oplus { text {hash}} ({ text {fingerprint}} (x))}$

Použití výše uvedených dvou hash funkcí na konstrukci tabulky hash kukačky umožňuje přemístění položky pouze na základě otisků prstů, když je nemožné načíst původní položku. Výsledkem je, že při vkládání nové položky, která vyžaduje přemístění stávající položky ${ displaystyle y}$, další možné umístění ${ displaystyle j}$ v tabulce pro tuto položku ${ displaystyle y}$ vykopnut z kbelíku ${ displaystyle i}$ se počítá jako

${ displaystyle j = i oplus { text {hash}} ({ text {fingerprint}} (y))}$

Na základě hašování kukaček s částečným klíčem může hašovací tabulka dosáhnout jak vysokého využití (díky hašování kukaček), tak kompaktnosti, protože se ukládají pouze otisky prstů. Operace vyhledávání a mazání kukačkového filtru jsou jednoduché. Kontrolovat lze maximálně dvě místa ${ displaystyle h_ {1} (x)}$ a ${ displaystyle h_ {2} (x)}$. Pokud je nalezen, lze v něm provést příslušnou operaci vyhledávání nebo odstranění ${ displaystyle O (1)}$ Více teoretické analýzy kukačkových filtrů lze najít v literatuře.^[3][4]

Srovnání s Bloomovými filtry

Kukačkový filtr je podobný a Bloomův filtr v tom, že jsou oba velmi rychlé a kompaktní a oba mohou vracet falešná pozitiva jako odpovědi na dotazy týkající se set-membership:

• Prostorově optimální filtry Bloom ${ displaystyle 1,44 log _ {2} (1 / epsilon)}$ bity prostoru na jeden vložený klíč, kde ${ displaystyle epsilon}$ je míra falešně pozitivních výsledků. Kukačkový filtr vyžaduje ${ displaystyle ( log _ {2} (1 / epsilon) +2) / alpha}$ kde ${ displaystyle alpha}$ je zatěžovací koeficient zatěžovací tabulky, který může být ${ displaystyle 95,5 \%}$ na základě nastavení kukačkového filtru. Povšimněte si, že teoretická dolní mez vyžaduje informace ${ displaystyle log _ {2} (1 / epsilon)}$ bity pro každou položku.
• Při pozitivním vyhledávání vyžaduje prostorový filtr Bloom konstantu ${ displaystyle log _ {2} (1 / epsilon)}$ paměť přistupuje do bitového pole, zatímco kukačkový filtr vyžaduje konstantní maximálně dvě vyhledávání.
• Kukačkové filtry mají sníženou rychlost vkládání po dosažení prahové hodnoty zatížení, když se doporučuje rozšíření tabulky. Naproti tomu filtry Bloom mohou vkládat nové položky za cenu vyšší míry falešně pozitivních výsledků před rozšířením.

Omezení

• Filtr kukačky může odstranit pouze položky, o nichž je známo, že byly vloženy dříve.
• Vkládání může selhat a je vyžadováno opětovné promíchání jako u jiných hash tabulek s kukačkou. Všimněte si, že amortizovaná složitost vložení je stále ${ displaystyle O (1)}$.^[5]

Reference

externí odkazy

• Pravděpodobnostní filtry podle příkladu - výukový program porovnávající filtry kukačky a květu.