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

If the vectorized version of _simple_euclidean_distance is slower when
n_features
is large, this is possibly because a large array is being allocated in the
subtraction. But I don't think 10000 is a reasonable number of candidates
at this point, is it? Surely if LSH is doing its job, we should have a much
smaller sample by this point. In any case, the computation could be batched
in groups larger than 1 row at a time.


On 14 August 2014 08:34, Maheshakya Wijewardena <notifications@github.com>
wrote:

>  In sklearn/neighbors/lsh_forest.py:
>
> > +    while lo < hi:
> > +        mid = (lo+hi)//2
> > +
> > +        k = _find_matching_indices(bit_
> string_array, query,
> > +                                   left_masks[mid],
> > +                                   right_masks[mid]).shape[0]
> > +        if k > 0:
> > +            lo = mid + 1
> > +            res = mid
> > +        else:
> > +            hi = mid
> > +
> > +    return res
> > +
> > +
> > +def _simple_euclidean_distance(query, candidates):
>
> @robertlayton <https://github.com/robertlayton> , I found that, with
> loop, it is faster when the n_features is large. I can obtain the same
> results as the loop with np.linalg.norm(candidates - query, axis=1). This
> is super fast when the dimension is low. But with high dimensions, this
> gets slower than the loop. Here are some profiling results:
>
> n_samples = 10000 (fixed)
>
> n_features = 100 :
> without loop: 57.1 ms
> with loop: 3.86 ms
>
> n_features = 500 :
> without loop: 21 ms
> with loop: 70.6 ms
>
> n_features = 1000 :
> without loop: 40.5 ms
> with loop: 82.3 ms
>
> n_features = 2000 :
> without loop: 79.6 ms
> with loop: 104 ms
>
> n_features = 5000 :
> without loop: 200 ms
> with loop: 177 ms
>
> n_features = 10000 :
> without loop: 377 ms
> with loop: 302 ms
>
> n_features = 20000 :
> without loop: 752 ms
> with loop: 551 ms
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r16211149>.
>