| Popis: |
Opisani su algoritmi Bloomovog filtra, probabilističke strukture podataka koja se koristi za određivanje pripadnosti podataka nekom skupu, te su navedeni njegovi nedostaci. Detaljno je opisan cuckoo filter, koji predstavlja poboljšanje u odnosu na Bloomov filter. Objašnjena su i implementirana poboljšanja cuckoo filtra: dinamički cuckoo filter, koji ima mogućnost dinamičkog povećanja kapaciteta, te je opisana strategija boljeg izbora, koja omogućuje ubrzano dodavanje novog elementa. Uspoređena su vremena izvođenja operacije dodavanja, brisanja i pretraživanje elemenata za cuckoo filter i njegova poboljšanja. Implementaciju sam napisala u programskom jeziku Go te su testovi provedeni na skupovima podataka različite veličine i s različitim vrijednostima parametara. The algorithms of the Bloom filter, the probabilistic set representation data structure, are described, and its shortcomings are listed. The cuckoo filter is described in detail, which is an improvement over the standard Bloom filter. Improvements of the cuckoo filter are explained and implemented: a dynamic cuckoo filter, which has the ability to dynamically increase its capacity, and the idea of better choice strategy is described, which allows fast insertion of a new element. The execution times of insert, delete and lookup operations for the cuckoo filter and its improvements are compared. I wrote the implementation in the Go programming language and the tests were performed on datasets of different sizes and with different cuckoo filter's parameters values. |
