Comprendere la permutazione circolante per estendere lo stimatore CMinHash

Abstract degli autori

CMinHash apre una nuova strada per progettare algoritmi MinHash con varianza e spazio di archiviazione ridotti grazie alle permutazioni circolanti. Tuttavia, è difficile estendere l’analisi originale della varianza ad altri stimatori MinHash. Presentiamo un nuovo approccio che fornisce espressioni approssimate della varianza, esplicite e facili da confrontare, e lo usiamo per analizzare lo stimatore Minner. Gli esperimenti numerici mostrano che la nostra espressione della varianza corrisponde all’errore quadratico medio empirico (MSE) delle stime. Il nostro lavoro mostra così come applicare la permutazione circolante ad altri stimatori MinHash e calcolarne la varianza approssimata.