Število različnih elementov v toku podatkov

Levičar, Benjamin (avtor), Cabello Justo, Sergio (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: tok podatkov, pretočni algoritmi, aproksimacijski algoritmi, zgoščevalne funkcije, ocenjevanje kardinalnosti
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2026
• PID: 20.500.12556/RUL-187895
• Datum objave v RUL: 16.09.2026

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Number of distinct elements in a data stream

Izvleček

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.

• Ključne besede: data streams, streaming algorithms, approximation algorithms, hash functions, cardinality estimation