Perché il conte-Min Sketch richiede due a due funzioni hash indipendenti?

Question

Il conte-Min Sketch è una struttura di dati impressionante per stimare le frequenze di elementi diversi in un flusso di dati . Intuitivamente, funziona scegliendo una varietà di funzioni di hash, hash ogni elemento a tali funzioni hash, e incrementando le frequenze di vari slot in varie tabelle. Per stimare la frequenza di un elemento, lo schizzo conte-Min applica le funzioni di hash a tali elementi ed assume il valore minimo di tutti gli slot che sono hash a.

Il documento originale sul Sketch conte-Min menziona che la struttura di dati richiede coppie funzioni di hash indipendenti, al fine di ottenere le necessarie garanzie sulla sua performance atteso. Tuttavia, guardando oltre la struttura, non vedo il motivo per cui l'indipendenza a coppie è necessario. Intuitivamente, penserei che tutto quello che sarebbe necessario è che la funzione di hash essere una funzione hash universale , dal momento che hash universale funzioni sono funzioni hash con basse probabilità di collisioni. L'analisi delle probabilità di collisione del conte-Min Sketch sembra molto simile all'analisi delle probabilità di collisione in una tabella hash incatenato (che richiede solo una famiglia di funzioni hash universali, non a coppie funzioni hash indipendenti), e non posso posto la differenza nelle analisi.

Perché è necessario per le funzioni hash nel disegno conte-Min di essere indipendente a coppie?

Grazie!

Answer 1

Hai ragione: sufficiente un hash universali. Pairwise indipendenza, mentre il più forte, è il solito metodo per costruire una famiglia hash universale. Anche a coppie indipendenza si contrappone alla carta con il 4-saggio indipendenza richiesti dalla metodi precedenti, come ad esempio lo schizzo AMS.