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

Sorry I haven't been following too closely. You guys have been catching 
important issues, its cool! I did want to weigh in on one:

The min_hash_length parameter avoids a bad performance issue (where we 
try to look at more than a quarter of the DB). In my opinion if 
min_hash_length avoids looking at sufficient candidates, then we should 
add some random candidates and continue as usual. Then candidates in 
_compute_distances is never empty.

Remember that even if min_hash_length kicked in in one index, it is 
quite likely that some other index is having better luck, and having 
some probability of bad performance is not a problem when using this 
type of data-structure, that's just life. Hence I think an error or 
warning should be avoided. BTW, there are algorithmic approaches we want 
to try that deal with this whole issue more elegantly, but I think we 
should test carefully after this is merged.

On a related issue: for the user to ask for more candidates than the DB 
indexes is a user error which should be raised.

Daniel

On 10/21/2014 09:20 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],
>
> Actually forest paradigm does not cause such an issue in the original
> form. There is a parameter |min_hash_length| of which the default value
> is 4. This is used to limit the number of candidates selected because
> candidates with very small hashes do not contribute to nearest neighbors
> much and it will also cause to overwhelm the set of selected candidates
> as there are many candidates with short hash length match for a query.
> In the original algorithm, candidates are selected until |max_depth|
> reaches 0. But here we allow to limit that by setting |min_hash_length|.
> If |min_hash_length| is set to 0, candidates will be selected until
> matching hash length becomes 0. Hench any input will have a closest
> hash. So the above problem will be eliminated.
>
> I think there should be a warning addressing this as well, right? To
> decrease the |min_hash_length|.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r19172313>.
>