Just as a note regarding NearestNeighbors.jl, due to curse of dimensionality, the kd-tree becomes very bad for high dimensional data (k-d tree - Wikipedia) You want something like N >> 2^k to use it where N is the number of points and k is the dimension.
The original motivation of NearestNeighbors.jl was to run it on geometrical queries (so mostly 2D and 3D) so it is likely there it will perform the best.