Dinamički cuckoo filtar s dodatnim svojstvima

diplomski rad

• Naslov (engleski): Extended dynamic cuckoo filter
• Autor: Matej Radović
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Ivica Botički (član povjerenstva)
• Član povjerenstva: Tomislav Jagušt (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2020-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Bloomov filtar je memorijski i vremenski učinkovita, probabilistička struktura podataka koja služi za utvrđivanje pripada li element skupu podataka. Iako ispunjava svoju svrhu, primjena Bloomovog filtra je ograničena isključivo na statičke skupove podataka s unaprijed poznatom kardinalnošću. Cuckoo filtar je struktura podataka sa istom svrhom kao i Bloomov filtar, ali s proširenim skupom funkcionalnosti koji omogućava rad i s dinamičkim skupovima podataka. U ovom radu se cuckoo filtru dodaju proširenja koja mu omogućuju učinkovitiji rad sa skupovima k-mera nekog genoma garantirajući manju stopu pogreške od običnog cuckoo filtra.

Sažetak (engleski)

Bloom filter is a space and time efficient, probabilistic data structure that is used to determine whether an element is a member of a data set. Although it fulfills its purpose, the application of the Bloom filter is limited exclusively to static data sets with cardinality known in advance. Cuckoo filter is a data structure with the same purpose as Bloom filter's, but with an extended set of functionalities which allow it to work with dynamic data sets. In this thesis, extensions are added to the cuckoo filter so that it can work more efficiently with sets of genome's k-mers, guaranteeing a lower error rate than a normal cuckoo filter.

• Ključne riječi: Bloomov filtar; cuckoo filtar; dinamički skupovi podataka; pohranjivanje k-mera
• Ključne riječi (engleski): Bloom filter; cuckoo filter; dynamic data sets; storing k-mers
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:552811
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:39:41