Število različnih elementov v toku podatkovLevičar, Benjamin (Avtor) Cabello Justo, Sergio (Mentor) tok podatkovpretočni algoritmiaproksimacijski algoritmizgoščevalne funkcijeocenjevanje kardinalnostiOcenjevanje števila različnih elementov (F0) v toku podatkov je eden temeljnih problemov pretočnega računalništva. Vendar eksaktna rešitev v enoprehodnem, pomnilniško omejenem modelu v najslabšem primeru zahteva prostor velikostnega reda Ω(N ), kjer je N velikost domene elementov, kar je za realne tokove neizvedljivo. V delu zato obravnavamo naključnostne (ϵ, δ)-aproksimacijske algoritme, ki s pomočjo naključnosti in zgoščevalnih funkcij dosežejo natančno oceno F0 ob bistveno manjši, polilogaritmični porabi prostora. Podrobno predstavimo in dokažemo pravilnost štirih algoritmov: algoritma CVM, Knuthove optimizacije CVM, algoritma Tidemark in algoritma BJKST. Teoretične rezultate nato preverimo tudi eksperimentalno. Vse štiri algoritme implementiramo in jih ovrednotimo na osmih standardiziranih testnih tokovih podatkov pri različnih dolžinah toka in nivojih razpoložljivega prostora. Rezultati potrjujejo, da natančnost algoritmov CVM, Knuthove optimizacije CVM in BJKST ostane stabilna ne glede na dolžino toka, medtem ko algoritem Tidemark zaradi odsotnosti (ϵ, δ)-jamstva ne preseže strukturne meje natančnosti, ki izhaja iz diskretizacije njegove ocene na potence števila 2.20262026-09-16 08:15:31Diplomsko delo/naloga187895VisID: 164158sl