# \[ANN\] VPTrees.jl - nearest neighbor search in metric spaces

**URL:** <https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477>\
**Category:** Package Announcements\
**Created:** [November 25, 2019, 7:33am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477 "2019-11-25T07:33:34Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![altre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/altre/32/17036_2.png) [@altre](https://discourse.julialang.org/u/altre)\
**Post date:** [November 25, 2019, 7:33am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/1 "2019-11-25T07:33:34Z")

</div>

[VPTrees.jl](https://github.com/altre/VPTrees.jl)

A Vantage Point Tree is a simple data structure effective for use in fast nearest neighbor search and range search for any metric developed by Peter Yianilos: [Data structures and algorithms for nearest neighbor search in general metric spaces](http://web.cs.iastate.edu/~honavar/nndatastructures.pdf).  
It’s very simple to use, for example with Levenshtein distance using [StringDistances.jl](https://github.com/matthieugomez/StringDistances.jl):

```julia
using VPTrees
using StringDistances

data = ["bla", "blub", "asdf", ":assd", "ast", "baube"]
metric = (a, b) -> evaluate(Levenshtein(),a,b)
vptree = VPTree(data, metric)
query = "blau"
radius = 2
data[find(vptree, query, radius)]
# 2-element Array{String,1}:
# "bla" 
# "blub"
n_neighbors = 3
data[find_nearest(vptree, query, n_neighbors)]
# 3-element Array{String,1}:
# "baube"
# "blub" 
# "bla"

```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [November 25, 2019, 9:48am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/2 "2019-11-25T09:48:04Z")

</div>

Given the proliferation of metric trees, would it make sense to merge them under one API and package (and along the way document which are appropriate for what kind of data)? Maybe nearest neighbors? I have a cover tree and some self-made construction lying around, ready to donate.

Many trivial algorithms (branch & bound search, approx branch & bound search) could work with most trees, as could some less trivial ones, like dual tree search.

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 25, 2019, 10:31am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/3 "2019-11-25T10:31:14Z")

</div>

@altre Can you please do some benchmark comparisons with NearestNeighbors.jl?

@foobar_lv2 there is a Julia org: [https://github.com/JuliaNeighbors](https://github.com/JuliaNeighbors) maybe it is time to put them all there as a first step, and as a second step consider a unifying API?

---

<div class="post-metadata">

**Author:** ![Tomas\_Pevny](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomas_pevny/32/25466_2.png) [@Tomas\_Pevny](https://discourse.julialang.org/u/Tomas_Pevny)\
**Post date:** [November 25, 2019, 11:14am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/4 "2019-11-25T11:14:02Z")

</div>

There is also [GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures and algorithms for Julia.](https://github.com/KristofferC/NearestNeighbors.jl) by Kristoffer Carlsson.

It would be really nice all of them having the same api if possible and unify to the same package. It is a lot of work though.

---

<div class="post-metadata">

**Author:** ![altre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/altre/32/17036_2.png) [@altre](https://discourse.julialang.org/u/altre)\
**Post date:** [November 26, 2019, 8:19am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/5 "2019-11-26T08:19:26Z")

</div>

Here are a few benchmarks for VPTrees, BKTrees, NearestNeighbors and linear search. Be aware though that random data is good for VPTree performance. Most interesting: For fast metrics, linear search is often faster. For expensive metrics, such as Levenshtein Distance, VPTrees is fastest. NearestNeighbors cannot accept Strings, which was my original use-case (with Levenshtein Distance).

```julia
using BenchmarkTools, Random, VPTrees, Distances, NearestNeighbors, BKTrees, DataStructures, StringDistances
Random.seed!(1);

rands = [rand(64) for _ in 1:10_000];
# Construction time
@btime VPTree(rands, (x,y) -> Distances.Minkowski(3.5)(x,y));
# 177.578 ms (116172 allocations: 7.15 MiB)
data = hcat(rands...);
@btime BallTree(data, Distances.Minkowski(3.5));
# 152.731 ms (32 allocations: 10.91 MiB)
# BKTrees are fastest in construction!
@btime BKTree((x,y) -> Distances.Minkowski(3.5)(x,y), rands);
# 21.077 ms (178625 allocations: 11.19 MiB)

const query = rand(64);
rands = [rand(64) for _ in 1:50_000];
vptree = VPTree(rands, (x,y) -> Distances.Minkowski(3.5)(x,y));
data = hcat(rands...);
btree = BallTree(data, Distances.Minkowski(3.5));
bktree = BKTree((x,y) -> Distances.Minkowski(3.5)(x,y), rands);
@btime inrange(btree, query, 1.4);
# 84.242 ms (10 allocations: 16.39 KiB)
@btime BKTrees.find(bktree, query, 2);
# 124.779 ms (250034 allocations: 8.87 MiB)
@btime VPTrees.find(vptree, query, 1.4);
# 77.486 ms (17 allocations: 1.00 MiB)
# VPTrees seems fastest, but for cheap metrics, it's hard to beat findall! (tested up to 1_000_000 random points)
@btime findall(x -> Distances.Minkowski(3.5)(x, query) < 1.4, rands);
# 65.777 ms (20 allocations: 1.00 MiB)

@btime knn(btree, query, 20);
# 80.167 ms (3 allocations: 512 bytes)
@btime BKTrees.find(bktree, query, 10; k=20);
# 126.905 ms (250034 allocations: 8.87 MiB)
@btime find_nearest(vptree, query, 20);
# 76.402 ms (8 allocations: 1.36 KiB)
# Once again, don't use trees for fast metrics!
@btime nsmallest(20, [(Distances.Minkowski(3.5)(query,r), i) for (i,r) in enumerate(rands)]);
# 65.691 ms (50011 allocations: 2.29 MiB)

metric(a::AbstractString, b::AbstractString) = evaluate(Levenshtein(), a,b);
randstrings = [randstring("01234456789") for _ in 1:50_000];
vptree = VPTree(randstrings, metric);
bktree = BKTree(metric, randstrings);
const stringquery = randstrings[rand(1:length(randstrings))];
@btime BKTrees.find(bktree, stringquery, 2);
# 39.493 ms (148066 allocations: 6.94 MiB)
@btime VPTrees.find(vptree, stringquery, 2);
# 9.668 ms (40066 allocations: 5.50 MiB)
# With expensive metrics, VPTrees are finally actually faster than linear search
@btime findall(a -> metric(stringquery, a) <= 2, randstrings);
# 12.637 ms (50005 allocations: 6.86 MiB)
# Unfortunately NearestNeighbors does not accept strings, so this does not work:
btree = BallTree(randstrings, Levenshtein())

```

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 26, 2019, 10:10pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/6 "2019-11-26T22:10:14Z")

</div>

Thanks for sharing these benchmarks. At JuliaDynamics we are constantly doing a lot of nearest neighbor searching and it will be interesting to compare these three packages also for the datasets that we use there.

They are fundamentally different in the sense that they are composed of low-dimensional static arrays. I know that NearestNeighbors have been optimized a lot for these kind of datasets.

In JuliaDynamics, specifically the “Base” package for datasets, I have defined a `neighborhood` interface that links to NearestNeighbors.jl . It would be trivial to extend this to accommodate all packages. I only have to define dispatch for the second argument (currently only “tree”) of the [`neighborhood` function](https://juliadynamics.github.io/DynamicalSystems.jl/dev/embedding/dataset/#DelayEmbeddings.neighborhood)

maybe @altre , @kristoffer.carlsson and @JonasIsensee and @zgornel you wouldbe interested into bringing everything together in JuliaNeighbors ? I’d be happy to contribute the common interface via `neighborhood` or something similar.

---

<div class="post-metadata">

**Author:** ![JonasIsensee](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jonasisensee/32/4704_2.png) [@JonasIsensee](https://discourse.julialang.org/u/JonasIsensee)\
**Post date:** [November 26, 2019, 10:32pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/7 "2019-11-26T22:32:07Z")

</div>

Trivial is probably a bit too optimistic.  
For example Approximate NN libraries like [https://github.com/JuliaNeighbors/HNSW.jl](https://github.com/JuliaNeighbors/HNSW.jl)  
will need additional arguments.

But I agree that it would be worthwhile to work on some kind of shared API.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [November 30, 2019, 9:25am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/8 "2019-11-30T09:25:58Z")

</div>

Makes sense to me. I am a bit confused about what is the approach to transfer a registered package from one organization/account (specifically for [IVFADC.jl](https://github.com/zgornel/IVFADC.jl) and [BKTrees.jl](https://github.com/zgornel/BKTrees.jl) )

Some sort of “informal” API proposal for NN/ANN methods should also exist somewhere.

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 30, 2019, 9:57am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/9 "2019-11-30T09:57:24Z")

</div>

> approach to transfer a registered package

You just transfer it by going to the Settings page. Nothing breaks because github will autolink your repo to the moved one. But one typically also does a PR at the GeneralRegistry that changes a single url.

Here is my proposal for the universal API, composed of two functions

```julia
datastructure = whatever_structure_each_package_uses
neighborhood(query, datastructure, ntype; kwargs...)

```

It uses the “datastruture” to find nearest neighbors of the `query`. As there are (almost) always two types of neighbhorhood (we use `FixedSize(ε::Real)` and `FixedMass(k::Int)`) that find either all neighbhors in range `ε` or the `k` nearest neighbors.

Each package just has to implement two versions of `neighborhood`.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [November 30, 2019, 10:37am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/10 "2019-11-30T10:37:46Z")

</div>

> [@Datseris](#):
>
> But one typically also does a PR at the GeneralRegistry that changes a single url.

Can you be more explicit here? Im using the registrator and tag bots. Im reluctant to break things because I use some of this stuff in production and experimenting is not an option. Hopefully, there is a procedure somewhere to transfer a registered package and update the general registry; im not aware of any as this is a pretty rare case.

> [@Datseris](#):
>
> Here is my proposal for the universal API, composed of two functions

We obviously have different needs and views. I for example am interested in interfaces to work with indexed points, mostly pusing, poping, insertion and delition (with index update). AFAIK, only IVFADC supports `push!`/`pop!`/`deleteat!` etc. Also, range searches are optional…

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 30, 2019, 11:18am UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/11 "2019-11-30T11:18:05Z")

</div>

> We obviously have different needs and views

I see. Thanks for showing this side of the coin.

You are right, and I also cannot imagine a common API that satisfy both the needs from my field, as well as yours.

> [@zgornel](#):
>
> Im reluctant to break things

I have done this transfer of packages many times already, across several different organizations and nothing broke. In fact, everything work just like before without any change. But I can say for sure that I am not willing to _promise_ anything. In the end, a transfer is not really necessary. It helps the community, but that’s about it.

The biggest concern is that the common API does not seem possible at all given the difference in needs.

---

<div class="post-metadata">

**Author:** ![JonasIsensee](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jonasisensee/32/4704_2.png) [@JonasIsensee](https://discourse.julialang.org/u/JonasIsensee)\
**Post date:** [November 30, 2019, 12:50pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/12 "2019-11-30T12:50:37Z")

</div>

No need to give up just yet.  
Given the various features supported by different algorithms it does not make sense  
to _limit_ ourselves to a common API. That does not mean that we can’t add one that would make benchmarks and comparisons easier.  
Im thinking of something along the lines of

```julia
ds = produce_structure(MyAlgType, data; kwargs...) # Initialize structure
do_preparatory_work!(ds; kwargs....) # Build your tree, graph or whatever
search(ds, query; kwargs...) # Do your searches 

# Implement these, if your structure allows that.
insert!(ds, new_point) # is new_point an actual vector or just an index to somewhere?
delete!(ds, point) 

```

This or something similar would hopefully provide an interface to switch out different algorithms for comparison purposes without having to change much code.

What are your thoughts?

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 30, 2019, 12:53pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/13 "2019-11-30T12:53:46Z")

</div>

I like a lot the piece of code you paste. I would still argue that `search` should have 3 arguments, because searching `inrange` and searching `knn` is at a fundamental level different enough of an operation that I wouldn’t use a keyword for it.

But other than that what you suggest seems fine for me, and easy ti implement as well.

---

<div class="post-metadata">

**Author:** ![JonasIsensee](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jonasisensee/32/4704_2.png) [@JonasIsensee](https://discourse.julialang.org/u/JonasIsensee)\
**Post date:** [November 30, 2019, 1:02pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/14 "2019-11-30T13:02:24Z")

</div>

Other things to consider would be return values.  
Some structures might return points, or indices, and maybe not the distances?

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 30, 2019, 1:12pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/15 "2019-11-30T13:12:18Z")

</div>

Seems there is interest. Let’s continue the conversation over here: [https://github.com/JuliaNeighbors/Neighborhood.jl/issues/1](https://github.com/JuliaNeighbors/Neighborhood.jl/issues/1) to keep things localized.

@zgornel @altre and @kristoffer.carlsson if you are interested you are welcome to join the conversation there.

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [November 30, 2019, 1:49pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/16 "2019-11-30T13:49:55Z")

</div>

Hi, I am not currently working on the nearest neighbors problem, but I am interested in the metric space interoperability in general. For example, my package [DirectSum.jl](https://github.com/chakravala/DirectSum.jl) is a repository for organizing metric spaces and vector bundle manifolds (abstractly). These vector bundles with a metric can be used in [AbstractTensors.jl](https://github.com/chakravala/AbstractTensors.jl) and [Grassmann.jl](https://github.com/chakravala/Grassmann.jl) to specify the metric of the statically allocated tensor algebra elements I work with (similar to what @Datseris is probably in need of). Not sure if this is entirely relevant to the discussion here, but my general intention with these packages is to provide a universal interface for computing in manifold spaces having a metric specification (and direct sum interoperability). If this kind of interoperability interests you, please let me know, but maybe my needs are completely different from the needs talked about here.

Also, I happen to have my own unrelated binary tree package called [Dendriform.jl](https://github.com/chakravala/Dendriform.jl), which I plan to revise and update soon, sorry if this is getting off topic, but the whole tree and metric space thing resonates with me a bit, so please let me know if the metric spaces I am talking about might be useful for perhaps @Datseris needs for metrics.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [November 30, 2019, 1:52pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/17 "2019-11-30T13:52:15Z")

</div>

> [@Datseris](#):
>
> I have done this transfer of packages many times already, across several different organizations and nothing broke.

That’s good enough for me. Could you make an idiot’s guide to the steps (no pressure really)? Thanks 😉

> [@Datseris](#):
>
> The biggest concern is that the common API does not seem possible at all given the difference in needs.

Well, any recommendation would be a plus for anyone that is thinking of contributing with new packages. For example, preferred returned format i.e. `Tuple{Vector{<:Integer}, Vector{<:AbstractFloat}}`, methods names i.e. `knn`/`knn_search` etc.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [November 30, 2019, 1:52pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/18 "2019-11-30T13:52:54Z")

</div>

Will do.

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 30, 2019, 2:03pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/19 "2019-11-30T14:03:39Z")

</div>

> [@zgornel](#):
>
> That’s good enough for me. Could you make an idiot’s guide to the steps (no pressure really)? Thanks

It’s simpler than what you’d expect actually 😉

1. Transfer repo by going to its settings.
2. Add JuliaRegistrator / tagbot in the new host organization. But I think @JonasIsensee has already done that for JuliaNeighbors
3. Do A PR in the General Registry changing [e.g. this line](https://github.com/JuliaRegistries/General/blob/master/V/VPTrees/Package.toml#L3) (or the corresponding one for the transferred package) to the new host url.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [November 30, 2019, 2:24pm UTC](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477/20 "2019-11-30T14:24:04Z")

</div>

Alright, thanks. Will try in the following days.  
EDIT: All done 😉  
[https://github.com/JuliaNeighbors](https://github.com/JuliaNeighbors)

[Next page](https://discourse.julialang.org/t/ann-vptrees-jl-nearest-neighbor-search-in-metric-spaces/31477.md?page=2)