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

Invariant: unless the number of indexed points is small than the number 
of points requested (which should raise an error), the number of 
candidates passed to distance computation should always be at least the 
requested number, so that the best k of those can be returned.

Anything else complicates the users life.

So I would complete the candidate size to a reasonable size (say, 5k) 
with random candidates.

Daniel

On 10/22/2014 10:52 AM, 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],
>
> Oops. I just pushed without seeing this comment.
> However there is another issue with candidates. We can surely use random
> set of candidates if there 0 candidates were selected. But selected
> number of candidates may be less than the requested number of neighbors.
> Here I only used a user warning for such situation. How can we address
> this better?
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r19201049>.
>