Funzioni binarie e Locality Sensitive Hashing (LSH)

Question

Sto studiando FLANN, una libreria per la ricerca dei vicini più vicini.

Per il metodo LSH rappresentano un oggetto (punto nello spazio di ricerca), come un array di int unsigned. Non sono sicuro del motivo per cui lo fanno, e non rappresentano un punto semplicemente come un doppio array (che rappresenterebbe un punto nello spazio vettoriale multidimensionale). Forse perché LSH è usato per le funzioni binarie ? Qualcuno può condividere di più sul possibile uso di unsigned int in questo caso? Perché unsigned int se hai solo bisogno di uno 0 e 1 per ogni funzione?

Grazie

Answer 1

prega di notare che farò riferimento alla versione più recente FLANN, cioè flann-1.8.3 al momento della scrittura.

Per il metodo LSH che rappresentano un oggetto (punto nello spazio di ricerca), come un array di unsigned int

No: questo è sbagliato. La classe LshIndex include un metodo buildIndexImpl che implementa l'indicizzazione LSH. Poiché l'LSH è fondamentalmente una raccolta di tabelle hash, l'indicizzazione effettiva si verifica nella classe LshTable.

Il metodo di indicizzazione elementare, cioè il metodo che indicizza una caratteristica vettore (alias descrittore, o punto) alla volta è:

/** Add a feature to the table 
* @param value the value to store for that feature 
* @param feature the feature itself 
*/ 
void add(unsigned int value, const ElementType* feature) {...} 

Nota: il metodo buildIndexImpl utilizza la versione alternativa che semplicemente itera le caratteristiche e chiamare il metodo sopra su ciascuna.

Come si può vedere questo metodo ha 2 argomenti che è una coppia (ID, descriptor):

1. value che è unsigned int rappresenta la funzione di vettore identificatore numerico univoco (caratterizzato da aka indice)
2. feature rappresenta la funzione di vettore stesso

Se si guarda all'implementazione si può vedere che il primo passo consiste nel tratteggiare il descrittto valore r per ottenere la chiave secchio correlato (= identificatore della fessura di puntamento al secchio in cui verrà memorizzato l'ID descrittore):

BucketKey key = getKey(feature); 

In pratica la funzione getKey hashing è solo implementato per descrittori binari , cioè descrittori che possono essere rappresentati come un array di unsigned char:

// Specialization for unsigned char 
template<> 
inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const {...} 

Forse perché LSH viene utilizzato per funzioni binarie?

Sì: come indicato sopra, l'implementazione di FLANN LSH funziona nello Hamming space per i descrittori binari.

Se si sceglie di usare i descrittori con valori reali (in R**d) si dovrebbe fare riferimento alla original paper che include i dettagli su come convertire i vettori di caratteristiche in stringhe binarie in modo da utilizzare le funzioni di spazio Hamming e hash.

possono condividere qualcuno di più circa il possibile uso di unsigned int in questo caso ? Perché unsigned int se hai solo bisogno di uno 0 e 1 per ogni funzione?

Vedere sopra: il valore unsigned int viene utilizzato solo per memorizzare l'ID correlato di ciascun vettore di funzionalità.