Locality Sensitive Hashing(LSH) e Hamming-LSH

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Min-Hashing e k-Min-Hashing Web Search - Page Rank

Il LSH serve a trovare la similarità tra colonne usando la matrice delle segnature.
Il Min-LSH funziona così: prende
image not found
matrice kxm e la partiziona in l sottomatrici di dimensione rxm con k=lr. Quindi per ogni sottomatrice ripete i seguenti passi:

  1. Fai l'hash di ogni colonna.
  2. Se due colonne finiscono nello stesso bucket, allora sono candidate per essere simili.
  3. Dopo aver selezionato i candidati, verifica che ogni coppia candidata sia effettivamente simile controllando la similarità delle segnature.
  4. Per aumentare la probabilità che colonne simili stiano nello stesso hash bucket, ripeti il processo j volte.

Un altro metodo per trovare coppie di colonne con alta similarità è l'Hamming-LSH, la cui idea è ridurre il problema a cercare coppie di colonne con una piccola distanza di Hamming. La similarità e la distanza di Hamming sono legate dal seguente lemma:
image not found
Cioè quando consideriamo coppie con
image not found
fisso, allora la similarità è inversamente proporzionale alla distanza di Hamming.
Con l'H-LSH non avremo bisogno delle segnature ma sceglieremo collezioni random di colonne di densità simile. Per ogni insieme di colonne, sceglieremo le coppie con minima distanza di Hamming e quindi ricaveremo colonne simili usando i dati veri, invece di quelli filtrati con l'hashing come avviene nel Min-Hashing.
Il problema è che la matrice è sparsa e non è detto che le sue colonne abbiano densità simili.
Il problema è risolto con una serie di matrici M0, M1, M2, ... ognuna con densità maggiore, tali che ogni Mi+1 è ottenuta da Mi appaiando random le righe di Mi e mettendo l'OR in Mi+1. Mi+1 contiene metà delle righe di Mi. L'algoritmo è il seguente:
  1. Sia M0 = M, genera la sequenza M1, M2, ... come descritto sopra.
  2. Per ogni i>=0, seleziona k insiemi di r campioni di righe da Mi.
  3. Una coppia di colonne è candidata se esiste un i tale che:
    1. La coppia di colonne ha densità compresa nell'intervallo
      image not found
      in Mi, dove t è un parametro che indica il range di densità per le coppie candidate.
    2. E gli hash di questa coppia coincidono in almeno uno dei k insiemi.
Se n è il numero di righe, log n è il numero totale di matrici e il numero totale di righe in tutte le matrici è 2n.

Home Min-Hashing e k-Min-Hashing Web Search - Page Rank