20.500.12556/RUL-187895 Število različnih elementov v toku podatkov Number of distinct elements in a data stream Ocenjevanje š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. Estimating the number of distinct elements (F0) in a data stream is a fundamental problem in streaming computation. However an exact solution in the single-pass, memory-limited model requires, in the worst case, Ω(N ) space, where N is the size of the element domain, which is infeasible for real-world streams. This thesis examines randomized (ϵ, δ)-approximation algorithms that, through randomness and hash functions, achieve accurate estimates of F0 using substantially less, polylogarithmic space. We present and prove the correctness of four algorithms in detail: the CVM algorithm, Knuth’s optimization of CVM, the Tidemark algorithm, and the BJKST algorithm. We then validate these theoretical results experimentally, all four algorithms are implemented and evaluated on eight standardized benchmark data streams across varying stream lengths and space budgets. The results confirm that the accuracy of the CVM algorithm, Knuth’s optimization of CVM, and the BJKST algorithm remains stable regardless of stream length, while the Tidemark algorithm, lacking an (ϵ, δ)-guarantee, cannot go below a structural accuracy floor arising from its estimate being discretized to powers of 2. tok podatkov pretočni algoritmi aproksimacijski algoritmi zgoščevalne funkcije ocenjevanje kardinalnosti data streams streaming algorithms approximation algorithms hash functions cardinality estimation true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-09-16 08:15:31 2026-09-16 08:15:34 2026-09-17 04:29:51 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 164158 24425.pdf 24425.pdf 1 622C897C591D2138A7B864E288ADCD85 7bc0a02a031a8c6acdd09b125b31189e3ae8b9484d62ebbccecea54ef9b6476a fe3763fc-b195-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=247724 Fakulteta za matematiko in fiziko 0 0 0