# How to compute neighbour network using NearestNeighbors.jl

**URL:** <https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644>\
**Category:** Specific Domains\
**Created:** [January 22, 2017, 7:46pm UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644 "2017-01-22T19:46:10Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 22, 2017, 7:46pm UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644/1 "2017-01-22T19:46:10Z")

</div>

Using NearestNeighbor.jl I can find which points within a collection `col` are closest to a (different) given point or set of points. What I need is slightly different. I would like to compute the points p\_i in `col` that are within a certain distance of each point p\_j, also in `col`. I suspect this is an “easier” problem, hence the question below.

I can currently get what I want by (1) building a `KDTree` of `col`, `tree=KDTree(col)`, and then (2) running e.g. `knn(tree, col, 3)` over all points in `col`.

It turns out that step (1) is typically ~ six times faster than (2) for me, and I suspect all the information I need is already contained in `tree`. So the question: is it possible to obtain the n nearest neighbors for each point in a collection without invoking `knn`, just from the data inside the `KDTree` of that collection?

[Please complain if the question is not clear. Also let me know if it should be posted elsewhere]

I take the liberty of pinging @kristoffer.carlsson, the author of NearestNeighbors.jl, I hope that’s ok!

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [January 22, 2017, 8:45pm UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644/2 "2017-01-22T20:45:29Z")

</div>

If you are interested in a certain distance you presumably want to use `inrange` and not `knn`. Also, to make sure, is what you want to do equal to [this function](https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.query_pairs.html#scipy.spatial.KDTree.query_pairs) in scipy?

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 22, 2017, 9:46pm UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644/3 "2017-01-22T21:46:00Z")

</div>

Hi Kristoffer, yes, most of the time inrange is what I need, and that’s almost twice as fast as knn for me. In those situations I indeed need _all_ pairs within a given distance, so exactly what that scipy function does. Is that functionality already somewhere inside NearestNeighbors.jl?

Amazing work, by the way. I’m blown away by the performance of your KDTree constructor.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [January 23, 2017, 8:12am UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644/4 "2017-01-23T08:12:21Z")

</div>

I had some code in a previous package that did this: [https://github.com/JuliaGeometry/KDTrees.jl/blob/master/src/kd\_tree.jl#L617](https://github.com/JuliaGeometry/KDTrees.jl/blob/master/src/kd_tree.jl#L617).

I could probably get it working in `NearestNeighbors` but it will be a while because I don’t have time to spend on it now. If I remember correctly, it wasn’t that much faster than just checking point by point.

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [January 23, 2017, 8:17am UTC](https://discourse.julialang.org/t/how-to-compute-neighbour-network-using-nearestneighbors-jl/1644/5 "2017-01-23T08:17:55Z")

</div>

Ok, good to know. I will just keep using inrange for the moment then. Many thanks.