Esercizio - Count-Min sketch - tabella a mano e dimensionamento

Teoria: Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distintiModello a flusso (un passaggio, memoria molto minore di n); campionamento di riserva (reservoir sampling) con dimostrazione per induzione; contatore di Morris (stima non distorta 2^X-1, varianza n(n-1)/2); elementi distinti: idea di Flajolet-Martin e stima del k-esimo minimo (k-1)/v_k; Count-Min sketch con garanzia (epsilon, delta) e dimensionamento w=e/epsilon, d=ln(1/delta).Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distinti → (Count-Min sketch), Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprintHashing con catene e costo atteso 1+alfa; famiglie universali (probabilità di collisione al più 1/m) e costruzione h(x)=((ax+b) mod p) mod m con dimostrazione; hashing perfetto a due livelli (spazio lineare, ricerca O(1) nel caso peggiore); filtri di Bloom: falsi positivi (1-e^(-kn/m))^k e k ottimo (m/n) ln 2; fingerprint di stringhe e numero di bit necessari.Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint → (famiglie universali).

Testo.

1. Uno sketch ha $d=2$ righe e $w=4$ colonne. Il flusso contiene $a$ cinque volte, $b$ tre volte, $c$ due volte, $d$ e $e$ una volta ($N=12$ arrivi). Le funzioni hash (date) sono

Costruire la tabella dei contatori e le stime $\hat f(x)=\min_jC[j][h_j(x)]$ per i cinque elementi. Quali sono sovrastimati e perché? Che stima dà lo sketch per un elemento mai visto $z$ con $h_1(z)=0$, $h_2(z)=0$? 2. Dimostrare che $\hat f(x)\ge f(x)$ e che, con $w=\lceil e/\varepsilon\rceil$ e $d=\lceil\ln(1/\delta)\rceil$, $P(\hat f(x)>f(x)+\varepsilon N)\le\delta$. 3. Dimensionare uno sketch per $\varepsilon=0{,}001$, $\delta=0{,}01$ e per $\varepsilon=0{,}01$, $\delta=0{,}05$: quanti contatori? 4. Simulazione: flusso di $N=200\,000$ arrivi su $20\,000$ valori con frequenze di tipo Zipf (esponente $1{,}1$). Per i tre sketch $(\varepsilon,\delta)=(0{,}01;0{,}05)$, $(0{,}001;0{,}01)$ e $(0{,}05;0{,}2)$ misurare l'errore $\hat f-f$ massimo e medio sui $20\,000$ valori, la frazione di valori con errore superiore a $\varepsilon N$ e l'errore sull'elemento più frequente.

Soluzione

1. Tabella. Riga $1$ (somma per colonna di $h_1$): colonna $0$: $a+c=5+2=7$; colonna $1$: $b=3$; colonna $2$: $d=1$; colonna $3$: $e=1$. Riga $2$: colonna $0$: $d=1$; colonna $1$: $a+b=5+3=8$; colonna $2$: $e=1$; colonna $3$: $c=2$. $$C=\begin{pmatrix}7&3&1&1\\1&8&1&2\end{pmatrix}.$$ Stime:

• $\hat f(a)=\min(C[1][0],C[2][1])=\min(7,8)=\boxed7$ (vero $5$: sovrastimato di $2$, cioè $f(c)$: nella riga $1$ collide con $c$, nella riga $2$ con $b$, e il minimo è l'errore minore).
• $\hat f(b)=\min(C[1][1],C[2][1])=\min(3,8)=3$ ✓ (la riga $1$ non ha collisioni).
• $\hat f(c)=\min(7,C[2][3])=\min(7,2)=2$ ✓; $\hat f(d)=\min(1,1)=1$ ✓; $\hat f(e)=\min(1,1)=1$ ✓.
• Elemento mai visto $z$ con $h_1(z)=0$, $h_2(z)=0$: $\min(C[1][0],C[2][0])=\min(7,1)=\boxed1$ (vero $0$). Se invece fosse $h_1(z)=0$, $h_2(z)=1$ si avrebbe $\min(7,8)=7$: gli errori additivi possono essere grandi per gli elementi rari. Controllo: ogni riga somma a $N$ (riga $1$: $7+3+1+1=12$; riga $2$: $1+8+1+2=12$).

2. Garanzia. Nella riga $j$ la cella di $x$ contiene $C[j][h_j(x)]=f(x)+Y_j$ con $Y_j=\sum_{y\ne x}f(y)\mathbf 1[h_j(y)=h_j(x)]\ge0$, quindi ogni cella è $\ge f(x)$ e il minimo anche: $\hat f(x)\ge f(x)$. Per l'universalità $P(h_j(y)=h_j(x))\le\frac1w$ e per la linearità $E[Y_j]\le\frac Nw\le\frac{\varepsilon N}e$ (con $w\ge\frac e\varepsilon$). Markov (con $Y_j\ge0$): $P(Y_j>\varepsilon N)\le\frac1e$. Le righe usano funzioni indipendenti, quindi $P(\hat f(x)>f(x)+\varepsilon N)=P(\forall j:\ Y_j>\varepsilon N)\le e^{-d}\le\delta$ se $d\ge\ln\frac1\delta$.

3. Dimensionamento.

• $\varepsilon=0{,}001$, $\delta=0{,}01$: $w=\lceil e/0{,}001\rceil=\lceil2718{,}3\rceil=2719$, $d=\lceil\ln100\rceil=\lceil4{,}61\rceil=5$: $\boxed{13\,595}$ contatori (circa $54$ KB con contatori a $32$ bit).
• $\varepsilon=0{,}01$, $\delta=0{,}05$: $w=272$, $d=\lceil\ln20\rceil=\lceil3{,}0\rceil=3$ ($\ln20=2{,}996$): $\boxed{816}$ contatori.
• $\varepsilon=0{,}05$, $\delta=0{,}2$: $w=55$, $d=\lceil\ln5\rceil=2$: $110$ contatori.

4. Risultati della simulazione (indipendenti dal numero di valori $20\,000$):

La frazione di valori che violano il limite ($0$, $0$, $0{,}25\%$) è molto sotto $\delta$ ($5\%$, $1\%$, $20\%$): il limite è prudente. Il terzo sketch, piccolissimo, ha un errore massimo di $31\,137$ (maggiore di $\varepsilon N=10\,000$) su un valore le cui celle sono contaminate dai valori più frequenti: con $55$ colonne e $2$ righe le collisioni sono inevitabili. L'errore additivo è però trascurabile sull'elemento più frequente ($\approx6\%$ della sua frequenza al massimo): per questo lo sketch serve a trovare gli elementi frequenti, non i rari.

Codice di verifica

import random
from math import ceil, e, log

h1 = {'a': 0, 'b': 1, 'c': 0, 'd': 2, 'e': 3}
h2 = {'a': 1, 'b': 1, 'c': 3, 'd': 0, 'e': 2}
f = {'a': 5, 'b': 3, 'c': 2, 'd': 1, 'e': 1}
C = [[0] * 4 for _ in range(2)]
for x, c in f.items():
    C[0][h1[x]] += c
    C[1][h2[x]] += c
print(C, {x: min(C[0][h1[x]], C[1][h2[x]]) for x in f})
print(ceil(e / 0.001), ceil(log(100)), ceil(e / 0.01), ceil(log(20)), ceil(e / 0.05), ceil(log(5)))

def simula(eps, delta, N=200_000, U=20_000, seed=0):
    rnd = random.Random(seed)
    P = (1 << 61) - 1
    w, d = ceil(e / eps), ceil(log(1 / delta))
    ab = [(rnd.randrange(1, P), rnd.randrange(P)) for _ in range(d)]
    flusso = rnd.choices(range(U), weights=[1 / (i + 1) ** 1.1 for i in range(U)], k=N)
    C, fr = [[0] * w for _ in range(d)], {}
    for x in flusso:
        fr[x] = fr.get(x, 0) + 1
        for j, (a, b) in enumerate(ab):
            C[j][((a * x + b) % P) % w] += 1
    err = [min(C[j][((a * x + b) % P) % w] for j, (a, b) in enumerate(ab)) - fr.get(x, 0) for x in range(U)]
    top = max(fr, key=fr.get)
    return w * d, max(err), sum(err) / U, sum(r > eps * N for r in err) / U, fr[top], err[top]

for eps, delta in ((0.01, 0.05), (0.001, 0.01), (0.05, 0.2)):
    print(eps, delta, simula(eps, delta))

Risultato: la matrice [[7, 3, 1, 1], [1, 8, 1, 2]] con stime {'a': 7, 'b': 3, 'c': 2, 'd': 1, 'e': 1}, le dimensioni 2719 5 272 3 55 2, e le tre righe (celle, errore max, errore medio, frazione, f max, errore su f max) della tabella (per esempio 13595 44 7.2497 0.0 29285 3).