# Nearest Neighbor Search for points consisting of vectors/arrays

**URL:** <https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893>\
**Category:** Data\
**Tags:** question\
**Created:** [May 6, 2020, 3:04pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893 "2020-05-06T15:04:34Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![FrootLoops](https://avatars.discourse-cdn.com/v4/letter/f/c4cdca/32.png) [@FrootLoops](https://discourse.julialang.org/u/FrootLoops)\
**Post date:** [May 6, 2020, 3:04pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893/1 "2020-05-06T15:04:35Z")

</div>

Hello everybody,

I am trying to use the nearest neighbor package in Julia. I read the documentary and it was very easy to understand the examples for one dimensional problems. In my case it is a little bit more complicated.

I have a given point p = (x,y) where x and y are both 3 dimensional vectors. My data is a set consisting of points p\_i = (x\_i, y\_i) where x\_i and y\_i are also 3 dimensional vectors. Now I want to find the nearest point p\_i to p such that

min (|| x - x\_i ||^2 + || y - y\_i ||^2)

So far I tried a little bit, but I am always getting different kind of error messages. In the case below I used arrays instead of “real” vectors. But I am open to any suggestions for improvement.

```julia
# Create random data point p_i = (x_i, y_i) with x_i, y_i vectors
data = Array{Array{Float64, 1}}[]
for k in 1:10
    x_i = rand(Float64, (3))
    y_i = rand(Float64, (3))
    push!(data, [x_i, y_i])
end

# Create random point p = (x, y) with x,y vectors
point = Array{Array{Float64, 1}}[]
x = [0.1, 0.2, 0.3]
y = [0.5, 0.6, 0.7]
push!(point, [x, y])

# Find nearest point p_i in data to point p 
k = 3
kdtree = KDTree(data)
idxs, dists = knn(kdtree, point, k, true)

```

---

<div class="post-metadata">

**Author:** ![FrootLoops](https://avatars.discourse-cdn.com/v4/letter/f/c4cdca/32.png) [@FrootLoops](https://discourse.julialang.org/u/FrootLoops)\
**Post date:** [May 6, 2020, 8:21pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893/2 "2020-05-06T20:21:39Z")

</div>

Okay I found a workaround. My idea is to create a new data set consisting of vectors with entries x\_i and y\_i such that each data element is a vector with 6 entries.

In theory it would be something like:

```julia
data = Array{Float64, 1}[]
# Create random data point p_i = (x_i, y_i) with x_i, y_i vectors
for k in 1:10
    x_i = rand(Float64, (3))
    y_i = rand(Float64, (3))
    new_point = append!(x_i, y_i)
    push!(data, new_point)
end

# point p = (x, y) with x,y vectors
x = [0.1, 0.2, 0.3]
y = [0.5, 0.6, 0.7]
point = append!(x, y)

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 6, 2020, 8:31pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893/3 "2020-05-06T20:31:43Z")

</div>

> [@FrootLoops](#):
>
> My idea is to create a new data set consisting of vectors with entries x\_i and y\_i such that each data element is a vector with 6 entries.

Exactly. However, you should use [StaticArrays.jl](https://github.com/JuliaArrays/StaticArrays.jl) for this kind of thing (arrays of fixed-length short arrays) — it will be _dramatically_ faster.

That is, your 3-component points should be `x = SVector(0.1, 0.2, 0.3)` etcetera, and your 6-component points should be `SVector(x..., y...)` (6-component `SVector`s). And your `point` array then becomes a `Vector{SVector{6,Float64}}` (a 1d `Array` of 6-component `SVector`).

You should see big performance boosts — because the length of an `SVector` is known at compile time, many optimizations suddenly become possible.

---

<div class="post-metadata">

**Author:** ![FrootLoops](https://avatars.discourse-cdn.com/v4/letter/f/c4cdca/32.png) [@FrootLoops](https://discourse.julialang.org/u/FrootLoops)\
**Post date:** [May 6, 2020, 8:35pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893/4 "2020-05-06T20:35:20Z")

</div>

Thank you stevengj. I mean in this case it is working with the idea of append both vectors. My other question is now, how would you solve this problem, if you have for two different norms i.e.measuring the distance of the x\_i to x by a different norm as y\_i to y.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 6, 2020, 9:46pm UTC](https://discourse.julialang.org/t/nearest-neighbor-search-for-points-consisting-of-vectors-arrays/38893/5 "2020-05-06T21:46:45Z")

</div>

> [@FrootLoops](#):
>
> My other question is now, how would you solve this problem, if you have for two different norms i.e.measuring the distance of the x\_i to x by a different norm as y\_i to y.

You could define a custom type `MyType` that stores both `x` and `y`, and overload `+`, `-`, and `norm` for `MyType`:

```julia
MyType{T<:Number}
    x::SVector{3,T}
    y::SVector{3,T}
end
MyType(x,y) = MyType{promote_type(eltype(x),eltype(y))}(x, y)
Base.:+(a::MyType, b::MyType) = MyType(a.x+b.x, a.y+b.y)
Base.:-(a::MyType, b::MyType) = MyType(a.x-b.x, a.y-b.y)
LinearAlgebra.norm(a::MyType) = ....some norm....

```

(You could define other functions too, e.g. `zero` for the additive identity, `*` for scalars, etcetera, but you may not need any more methods for `KDTree`.)