Come eseguire il bucket degli hash sensibili alla località?

Question

Ho già l'algoritmo per produrre gli hash sensibili alla località, ma come dovrei utilizzarli per sfruttare le loro caratteristiche (ad esempio, elementi simili hanno un hash vicino (con la distanza di hamming))?

Nel codice MATLAB ho scoperto che creano semplicemente una matrice di distanza tra gli hash dei punti da cercare e gli hash dei punti nel database, per semplificare il codice, facendo riferimento a un metodo Charikar per un buon risultato implementazione del metodo di ricerca.

Ho provato a cercarlo, ma non sono sicuro di come applicare al mio caso nessuno dei metodi che ho trovato (come il metodo multi-probe). Nessuna di queste tecniche sembra facilmente inseribile se hai già gli hash. C'è qualche semplice codice di esempio per questo? O qualche suggerimento?

Questo è il link alla pagina con il codice MATLAB sto parlando: http://www.eecs.berkeley.edu/~kulis/klsh/klsh.htm

Answer 1

Sulla base di: Search in locality sensitive hashing direi che questo, dopo aver letto Similarity Estimation Techniques from Rounding Algorithms:

Questa domanda è in qualche modo ampio, quindi fornirò qui un esempio (astratto) minimo:

Abbiamo 6 (= n) vettori nel nostro set di dati, con d bit ciascuno. Supponiamo di fare 2 permessi casuali (= N).

Inizia la prima permutazione casuale! Ricorda che permutiamo i bit, non l'ordine dei vettori. Dopo permutando i bit, mantengono un ordine, per esempio:

v1 
v5 
v0 
v3 
v2 
v4 

Ora il vettore della query, q, arriva, ma è (quasi) improbabile che sta per essere la stessa con un vettore nel nostro set di dati (dopo la permutazione), quindi non lo troveremo eseguendo la ricerca binaria.

Tuttavia, stiamo per finire tra due vettori. Così ora possiamo immaginare lo scenario per essere come questo (per esempio q si trova tra V0 e v3:

v1 
v5 
v0 <-- up pointer 
    <-- q lies here 
v3 <-- down pointer 
v2 
v4 

ora passiamo verso l'alto o verso il basso il puntatore, che cercano per il vettore VI che abbinerà al massimo bit con q. Diciamo che è stato V0.

Allo stesso modo, facciamo il secondo permutazione e troviamo il VI vettore, diciamo v4. ora confrontiamo v0 dalla prima permutazione e v4, per vedere quale è più vicino al q, cioè quale ha il maggior numero di bit uguale a q.

---

Tuttavia, se si sta cercando un'implementazione pronta, è necessario chiedere in Software Recommendation. Vorrei anche esaminare il documento a cui mi collegavo per vedere se gli autori rendevano pubblico il codice, o se volevano condividerli dopo averli contattati.