infoarena informatica de performanta

Pentru cazuri cu putine numere distincte, bloom filter aduce un accuracy destul de bun, dar daca numarul de numere distincte este semnificativ peste numarul de buckets, nu mai obtinem nici o informatie (filter ul e saturat).

Pentru numere mari, putem face o histograma si computa o estimare folosind varianta. Pe bucket avem nevoie de 28 biti* pentru a evita overflow ul.
_
* Presupunand ca sunt storate binar avem 128 milioane (2^27) numere.

As propune sa folosim o histograma de 256 elemente (256 * 28 = 7168 biti) si un bloom filter de 928 biti.

Iteram prin fisier si updatam histograma si filter ul (folosing un hashing function cu destula entropie). Daca la final filter ul nu e saturat, returnam numarul de biti setati (bucket uri atinse). Altfel, computam din histograma varianta si returnam
> total - sqrt(varianta / N),
adica
> 128M - sqrt(varianta / 928)


Ex:
 - sub 23 de numere distincte, cu peste 50% sansa bloom filter ul va returna corect.
 - daca avem un singur outlier (ex: 60M + 1 numere distincte (60M dintre ele o data si un numar de 68M ori) ), varianta estimeaza corect.



@sagetuz, @Cristy94:
Cum calculati rata de eroare independent de input?