Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Binary features and Locality Sensitive Hashing (LSH)

I am studying FLANN, a library for approximate nearest neighbors search.

For the LSH method they represent an object (point in search space), as an array of unsigned int. I am not sure why they do this, and not represent a point simply as a double array (which would represent a point in multi-dimensional vector space). Maybe because LSH is used for binary features? Can someone share more about the possible use of unsigned int in this case? Why unsigned int if you only need a 0 and 1 for each feature?

Thanks

like image 220
user1796942 Avatar asked Jan 12 '13 18:01

user1796942


People also ask

What is LSH used for?

Near-duplicate detection: LSH is commonly used to deduplicate large quantities of documents, webpages, and other files. Genome-wide association study: Biologists often use LSH to identify similar gene expressions in genome databases.

What is LSH in big data?

Locality sensitive hashing (LSH) is a procedure for finding similar pairs in a large dataset. For a dataset of size N, the brute force method of comparing every possible pair would take N!/(2!( N-2)!) ~ N²/2 = O(N²) time. The LSH method aims to cut this down to O(N) time.

What are the advantages of locality sensitive hashing?

Locality Sensitive Hashing (LSH) is one of the most popular techniques for finding approximate nearest neighbor searches in high-dimensional spaces. The main benefits of LSH are its sub-linear query performance and theoretical guarantees on the query accuracy.


1 Answers

Please note that I will refer to the latest FLANN release, i.e. flann-1.8.3 at the time of writing.

For the LSH method they represent an object (point in search space), as an array of unsigned int

No: this is wrong. The LshIndex class includes a buildIndexImpl method that implements the LSH indexing. Since the LSH is basically a collection of hash tables, the effective indexing occurs on the LshTable class.

The elementary indexing method, i.e. the method that indexes one feature vector (aka descriptor, or point) at a time is:

/** 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) {...}

Note: the buildIndexImpl method uses the alternative version that simply iterates over the features, and call the above method on each.

As you can see this method has 2 arguments which is a pair (ID, descriptor):

  1. value which is unsigned int represents the feature vector unique numerical identifier (aka feature index)
  2. feature represents the feature vector itself

If you look at the implementation you can see that the first step consists in hashing the descriptor value to obtain the related bucket key (= the identifier of the slot pointing to the bucket in which this descriptor ID will be stored):

BucketKey key = getKey(feature);

In practice the getKey hashing function is only implemented for binary descriptors, i.e. descriptors that can be represented as an array of unsigned char:

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

Maybe because LSH is used for binary features?

Yes: as stated above, the FLANN LSH implementation works in the Hamming space for binary descriptors.

If you were to use descriptors with real values (in R**d) you should refer to the original paper that includes details about how to convert the feature vectors into binary strings so as to use the Hamming space and hash functions.

Can someone share more about the possible use of unsigned int in this case? Why unsigned int if you only need a 0 and 1 for each feature?

See above: the unsigned int value is only used to store the related ID of each feature vector.

like image 187
deltheil Avatar answered Sep 29 '22 21:09

deltheil