Esercizio - Dimensionamento di un filtro di Bloom e fingerprint di documenti

Teoria: 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 → (filtri di Bloom, fingerprint), Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson → (collisioni).

Testo. Un crawler deve ricordare $n=10^5$ indirizzi già visitati con un filtro di Bloom, accettando una frazione di falsi positivi (pagine ritenute già viste ma nuove) del $1\%$.

1. Quanti bit per elemento e quanti bit totali $m$ servono, e quale $k$? Quanti byte? Confrontare con la memorizzazione di $10^5$ chiavi da $64$ bit.
2. Calcolare il tasso di falsi positivi esatto $(1-(1-\frac1m)^{kn})^k$ per $k=5,6,7,8,10$ con questo $m$.
3. Con $m=10n$ bit calcolare il $k$ ottimo intero e il tasso di falsi positivi; con $m=8n$ idem.
4. Dimostrare che il $k$ che minimizza $(1-e^{-kn/m})^k$ è $\frac mn\ln2$.
5. Fingerprint. Si vogliono identificare $n=10^6$ documenti con una fingerprint di $b$ bit, con probabilità di una collisione tra due documenti qualsiasi $\le10^{-3}$. Quanti bit? E per confrontare due stringhe di lunghezza $10^6$ con la fingerprint polinomiale modulo $p=2^{61}-1$ qual è la probabilità di errore massima?
6. Verificare con una simulazione il tasso di falsi positivi del punto 2 (modello idealizzato: ogni elemento accende $k$ bit uniformi).

Soluzione

1. Dimensionamento. Il tasso ottimo è $f=2^{-k}=0{,}6185^{m/n}$, quindi $$\frac mn=\frac{\log_2(1/f)}{\ln2}=\frac{\log_2100}{0{,}6931}=\frac{6{,}644}{0{,}6931}=9{,}585\text{ bit per elemento}.$$ $m=\lceil9{,}585\cdot10^5\rceil=\boxed{958\,506}$ bit $=119\,814$ byte $\approx117$ KiB. Il $k$ ottimo è $9{,}585\cdot\ln2=6{,}64$, quindi $\boxed{k=7}$. Le chiavi da $64$ bit occupano $800\,000$ byte: il filtro è $6{,}7$ volte più piccolo.

2. Tasso esatto. Con $m=958\,506$:

Il minimo è a $k=7$ con $f=0{,}01004$, appena sopra l'$1\%$ per l'arrotondamento di $k$; chi vuole stare sotto l'$1\%$ aggiunge un po' di bit ($m=960\,000$).

3. Altri rapporti. Con $m=10n$: $k$ ottimo reale $6{,}93\to7$ e $f=(1-(1-10^{-6})^{7\cdot10^5})^7=\boxed{0{,}00819}$ (con $k=6$: $0{,}00844$; $k=8$: $0{,}00846$; $k=3$: $0{,}0174$). Con $m=8n$: $k$ reale $5{,}55$, il minimo intero è $k=6$ con $f=\boxed{0{,}0216}$ ($k=5$: $0{,}0217$; $k=7$: $0{,}0229$). Il minimo è piatto: scostarsi di uno da $k$ ottimo costa pochissimo.

4. Ottimizzazione. Sia $q=e^{-kn/m}$ (frazione di bit a $0$): allora $k=-\frac mn\ln q$ e $\ln f=k\ln(1-q)=-\frac mn\,\ln q\ln(1-q)$. Bisogna massimizzare $g(q)=\ln q\ln(1-q)$ su $(0,1)$. È simmetrica ($g(q)=g(1-q)$) e $g'(q)=\frac{\ln(1-q)}q-\frac{\ln q}{1-q}$ si annulla in $q=\frac12$ (dove i due termini sono uguali), che per simmetria è un estremo; a $q\to0,1$ si ha $g\to0$ e $g>0$ dentro: è un massimo, con $g(\frac12)=\ln^22$. Quindi $\ln f_{\min}=-\frac mn\ln^22$, $e^{-kn/m}=\frac12\iff\boxed{k=\frac mn\ln2}$ e $f_{\min}=2^{-k}$. Con $k$ ottimo metà dei bit è a $1$.

5. Fingerprint. Il numero di coppie è $\binom n2\approx5\cdot10^{11}$ e ognuna collide con probabilità $2^{-b}$: per l'union bound $P\le\frac{n^2}{2^{b+1}}$. Si vuole $\le10^{-3}$: $2^b\ge\frac{10^{12}}{2\cdot10^{-3}}=5\cdot10^{14}$, $b\ge\log_25\cdot10^{14}=48{,}83$, quindi $\boxed{b=49}$ (con $b=48$: $1{,}78\cdot10^{-3}$; $b=40$: $0{,}45$; $b=64$: $2{,}7\cdot10^{-8}$). Per due stringhe di lunghezza $\ell=10^6$ la fingerprint $\phi(s)=\sum s_ix^i\bmod p$ con $x$ uniforme in $\mathbb Z_p$: la differenza è un polinomio non nullo di grado $<\ell$, che ha al più $\ell-1$ radici in $\mathbb Z_p$ (un polinomio di grado $d$ ne ha al più $d$), quindi $P(\text{errore})\le\frac{\ell-1}p=\frac{999\,999}{2^{61}-1}=\boxed{4{,}3\cdot10^{-13}}$.

6. Simulazione. Con $n=10^5$, $m=958\,506$ e $300\,000$ interrogazioni di elementi non inseriti (modello idealizzato): $k=6$: $0{,}01027$ (formula $0{,}01014$); $k=7$: $0{,}01018$ (formula $0{,}01004$); $k=10$: $0{,}01302$ (formula $0{,}01300$). La frazione di bit a $1$ con $k=7$ è $0{,}518$ (attesa $1-e^{-7\cdot10^5/958506}=0{,}518$). La simulazione conferma la formula entro l'errore statistico ($\approx2\cdot10^{-4}$).

Codice di verifica

import numpy as np
from math import ceil, log, log2, exp

n = 10 ** 5
m = ceil(n * log2(100) / log(2))                    # 958506
f = lambda m, k, n=n: (1 - (1 - 1 / m) ** (k * n)) ** k
print(m, m / 8, [round(f(m, k), 5) for k in (5, 6, 7, 8, 10)])
print([round(f(10 * n, k), 5) for k in (3, 6, 7, 8)], [round(f(8 * n, k), 5) for k in (5, 6, 7)])
print([10 ** 12 / 2 ** (b + 1) for b in (48, 49, 64)], 999999 / (2 ** 61 - 1))

rng = np.random.default_rng(9)
for k in (6, 7, 10):
    bit = np.zeros(m, dtype=bool)
    bit[rng.integers(0, m, size=(n, k)).ravel()] = True      # ogni elemento accende k bit
    q = rng.integers(0, m, size=(300_000, k))                # interrogazioni di elementi nuovi
    print(k, bit.mean(), bit[q].all(axis=1).mean())

Risultato: 958506 119813.25 [0.01109, 0.01014, 0.01004, 0.01053, 0.013], [0.01741, 0.00844, 0.00819, 0.00846] [0.02168, 0.02158, 0.02293] e [0.00178, 0.00089, 2.7e-08] 4.3e-13 (limiti per $b=48,49,64$ e fingerprint di stringhe), poi tre righe con la frazione di bit a $1$ e il tasso osservato ($\approx0{,}01$-$0{,}013$).