[MRG] Locality Sensitive Hashing for approximate nearest neighbor search(GSoC)

The hard requirement is that if the index is large enough, we should 
always return exactly k distinct neighbors from the DB. The rest is 
optional because (unless we have evidence otherwise), the data structure 
actually works for non-toy datasets.

That said, just to discuss the ideas: Yes, taking min(index_size, 5 * k) 
candidates is fine, of course: in the case where index_size is used, 
that is falling back to brute force.

When the DB is large, if you choose k at random, their average distance 
will be the average distance in the DB. If you choose at random 5k and 
choose the top k out of them, your neighbors will be better than 
average; that was why I proposed it. Of course, the LSHForest indices 
should be much better than this anyway.

Daniel

On 10/22/2014 03:57 PM, Maheshakya Wijewardena wrote:
> In sklearn/neighbors/approximate.py:
>
>> +        hashes = (grp.transform(self._fit_X) > 0).astype(int)
>> +        hash_function = grp.components_
>> +
>> +        binary_hashes = np.packbits(hashes).view(dtype='>u4')
>> +        original_indices = np.argsort(binary_hashes)
>> +
>> +        return original_indices, binary_hashes[original_indices], hash_function
>> +
>> +    def _compute_distances(self, query, candidates):
>> +        """Computes the cosine distance.
>> +
>> +        Distance is from the query to points in the candidates array.
>> +        Returns argsort of distances in the candidates
>> +        array and sorted distances.
>> +        """
>> +        distances = pairwise_distances(query, self._fit_X[candidates],
>
> Choosing fixed 5k (or any number) of candidates may not be practical
> sometimes because 5k can be greater than index size. What if only k
> distinct candidates are chosen randomly and returned? In fact choosing
> 5k candidates causes more distance computations which is redundant is
> such situation.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r19214634>.
>