Filtru de cuc

Filtrul cuc este o structură de date probabilistică eficientă din punct de vedere al memoriei care este utilizată pentru a testa dacă un element aparține unui set , similar filtrului Bloom . Sunt posibile false pozitive , dar nu false negative - cu alte cuvinte, interogarea returnează fie „posibil aparține setului”, fie „cu siguranță nu aparține”. De asemenea, filtrul de cuc vă permite să eliminați elementele existente, pe care filtrul de înflorire nu le poate face (cu excepția cazului în care utilizați opțiunea de numărare, care necesită mai multă memorie). În plus, pentru aplicațiile care stochează multe elemente și vizează o rată fals pozitivă moderat scăzută, filtrul cuco realizează o suprasarcină de memorie mai mică decât filtrul Bloom optimizat pentru memorie [1] .

Filtrul de cuc a fost descris pentru prima dată în 2014 [2] .

Algoritm

Filtrul cucului folosește un tabel hash asociat cu mai multe canale bazat pe hashing cuc pentru a stoca amprentele digitale ale tuturor elementelor (fiecare găleată din tabelul hash poate stoca până la intrări). În special, cei doi indici de coșuri potențiale și din tabel pentru un anumit element sunt calculați folosind următoarele două funcții hash (numite partial - key cuckoo hashing ) [2] ): $n$ $n$ $i$ $j$ $X$

i=h_{1}(x)={\text{hash})(x)

j=h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{amprenta digitală}}(x))

Utilizarea celor două funcții hash de mai sus pentru a construi tabele hash cu cuc permite ca elementele să fie mutate numai pe baza amprentei digitale atunci când elementul original nu poate fi cunoscut. Ca urmare, la inserarea unui articol nou care necesită mutarea unui articol existent , cealaltă locație posibilă din tabel pentru articolul evacuat din coșul de reciclare este calculată prin formula $X$ $y$ $j$ $y$ $eu,$

j=i\oplus {\text{hash}}({\text{amprenta digitală}}(y))

Un tabel de hash bazat pe hashing cuc cu o cheie parțială poate fi atât foarte utilizabil (datorită hashingului cuc) cât și compact, deoarece sunt stocate doar amprentele digitale. Operațiunile de căutare și ștergere sunt simple. Există maximum două locații de verificat: și . Dacă este găsit un element, operația de căutare sau ștergere corespunzătoare poate fi finalizată la timp . O analiză teoretică mai detaliată a filtrului de cuc poate fi găsită în literatura de specialitate [3] [4] . $h_{1}(x)$ $h_{2}(x)$ $O(1)$

Comparația filtrului Bloom

Filtrul Cuckoo este similar cu filtrul Bloom prin faptul că ambele sunt foarte rapide și compacte și ambele pot returna rezultate false pozitive:

Filtrele Bloom optime pentru memorie folosesc un bit pentru fiecare cheie introdusă, unde este rata fals pozitive. Filtrul de cuc are nevoie de , unde este factorul de încărcare a tabelului hash, care poate fi egal în funcție de setări. Rețineți că limita inferioară teoretică necesită biți pentru fiecare element. $1{,}44\log _{2}(1/\varepsilon )$ $\varepsilon$ $(\log _{2}(1/\varepsilon )+2)/\alpha$ $\alfa$ $95{,}5\,\%$ $\log _{2}(1/\varepsilon )$
Dacă rezultatul căutării este pozitiv, filtrul Bloom optim pentru memorie necesită un număr constant de operațiuni de acces bitmap, în timp ce filtrul cuccoo necesită nu mai mult de două astfel de operațiuni. $\log _{2}(1/\varepsilon )$
Filtrul de cuc încetinește viteza de inserție după atingerea pragului de încărcare când se recomandă extinderea mesei. Puteți continua să inserați elemente noi în filtrul Bloom, al căror dezavantaj este o rată ridicată de fals pozitive înainte de extindere.

Restricții

Din filtrul de cuc, puteți elimina doar elemente care au fost introduse cu siguranță înainte.
Inserarea poate eșua și hash-ul trebuie recalculat. Complexitatea inserției amortizate este încă [5] . $O(1)$

Link -uri

↑ Michael D. Mitzenmacher. Filtre Bloom, Cuckoo Hashing, Filtre Cuckoo, Filtre adaptive Cuckoo și Filtre Learned Bloom . (nedefinit)
↑ 1 2 Ventilator, Coș; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Filtru de cuc: practic mai bun decât Bloom . Proc. A 10-a Conferință Internațională ACM privind experimentele și tehnologiile emergente de rețea (CoNEXT '14). Sydney, Australia. pp. 75-88. DOI : 10.1145/2674005.2674994 . ISBN 9781450332798 .
↑ Eppstein, David (22 iunie 2016). Filtru de cuc: simplificare și analiză . Proc. Al 15-lea simpozion scandinav și ateliere de lucru despre teoria algoritmilor (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs). 53 . Reykjavik, Islanda. pp. 8:1–8:12. arXiv : 1604.06067 . DOI : 10.4230/LIPIcs.SWAT.2016.8 .
↑ Fleming, Noah (17 mai 2018). Cuckoo Hashing și Cuckoo Filters (PDF) (Raport tehnic). Universitatea din Toronto.
↑ Pagh, Rasmus; Rodler, Flemming Friche (2001). „Hashing cu cuc” Proc. Al 9-lea Simpozion european anual privind algoritmi (ESA 2001) . Note de curs în informatică. 2161 . Arhus, Danemarca. pp. 121-133. DOI : 10.1007/3-540-44676-1_10 . ISBN 978-3-540-42493-2 .

Link -uri

Filtre probabilistice prin exemplu — Un tutorial care compară filtrele Cuckoo și Bloom