Implement threading. about nearestneighbors.jl HOT 4 OPEN

On hold until Base threading is better.

from nearestneighbors.jl.

Thanks for this nice package. I was looking for some parallel versions for knn and it led me here. Could you please throw some light on what is the plan and how could any of us help out.

from nearestneighbors.jl.

I don't have a plan by myself but I can see ways by which parallelization could move forward. I am only talking about shared memory here.

Threaded building of the trees

The gist in the first post should give an idea how it could be done. What I did was that one thread worked on the tree and then more threads take over as the tree is split.

Threaded querying of points

Should be fairly straightforward to just partition the query points and have one thread work on each partition.

from nearestneighbors.jl.

Here's a quick code to do parallel querying in case anyone needs something practical right now!

println("KNN Searches")
function simple_partition(n::Int,k::Int)
  rval = ones(Int,k+1)
  m,r = divrem(n,k)
  fill!(rval, m)
  rval[1] = 1
  for i = 2:k+1
    rval[i] += r .> (i-2)
  end
  cumsum!(rval,rval)
end
function parallel_knn(kdtree, X, k)
    nt = Threads.nthreads()
    idxs_t = Vector{Any}(nt)
    dists_t = Vector{Any}(nt)
    parts = simple_partition(size(X,2),nt)
    Threads.@threads for i=1:nt
        idxs_t[i], dists_t[i] = knn(kdtree, X[:,parts[i]:parts[i+1]-1], k, true) 
    end
    return vcat(idxs_t...), vcat(dists_t...)
end

It passed my simple test on random points as giving the same things as knn on the full dataset. Otherwise, I haven't tested it at all.

Also, you'd probably want to make it pass more arguments to the actual knn function. I was just being lazy for my use.

Haven't tried to measure speedup! Just trying to use this to get some answers for a problem I don't want to wait forever for knn to compute.

from nearestneighbors.jl.