# \[ANN\] Shrike.jl: Julia beats optimized C++ (Fast accurate approximate nearest neighbor search)

**URL:** <https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763>\
**Category:** Package Announcements\
**Tags:** package\
**Created:** [June 11, 2021, 9:08pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763 "2021-06-11T21:08:48Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![djpasseyjr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djpasseyjr/32/23695_2.png) [@djpasseyjr](https://discourse.julialang.org/u/djpasseyjr)\
**Post date:** [June 11, 2021, 9:08pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/1 "2021-06-11T21:08:48Z")

</div>

I wrote a Julia package ([`Shrike.jl`](https://github.com/djpasseyjr/Shrike.jl)) for approximate nearest neighbor search. My algorithm draws heavily on the [`mrpt`](https://github.com/vioshyvo/mrpt) algorithm and uses the same principles behind [`annoy`](https://github.com/spotify/annoy) (a popular approximate nearest neighbor package by Spotify). My Julia implementation beat both of them! See the `Shrike.jl/README.md` for details.

I was shocked and thrilled! I am no Julia expert, but the fact that I was able to outperform about 2000 lines of C++ in 500 lines of Julia is a real testament to the power of the language.

As a caveat, I should mention that writing `Shrike.jl` wasn’t simple. I spent a lot of time learning about and testing different Julia optimizations strategies.

This is my first time making a public Julia package and I am planning to figure out how to add it to the registry. Any suggestions or feedback on the package would be appreciated. For instance, where can I leave out type annotations and not have it impact performance?

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [June 11, 2021, 10:40pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/2 "2021-06-11T22:40:22Z")

</div>

8 posts were split to a new topic: [Naming diversion for Shrike.jl](https://discourse.julialang.org/t/naming-diversion-for-shrike-jl/62769)

---

<div class="post-metadata">

**Author:** ![Albert\_Zevelev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_zevelev/32/11844_2.png) [@Albert\_Zevelev](https://discourse.julialang.org/u/Albert_Zevelev)\
**Post date:** [June 11, 2021, 9:48pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/4 "2021-06-11T21:48:33Z")

</div>

This looks great!  
Have you considered porting it to [MLJ](https://github.com/alan-turing-institute/MLJ.jl).jl?  
They currently have [150+ supported models](https://alan-turing-institute.github.io/MLJ.jl/dev/list_of_supported_models/) (including NearestNeighborModels.jl).

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [June 12, 2021, 12:08am UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/5 "2021-06-12T00:08:53Z")

</div>

Great! Is this package comparable to the widely used and extremely efficient NearestNeighbors.jl? If yes, can you benchmark against as well? That would be a good reference to have.

---

<div class="post-metadata">

**Author:** ![Albert\_Zevelev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_zevelev/32/11844_2.png) [@Albert\_Zevelev](https://discourse.julialang.org/u/Albert_Zevelev)\
**Post date:** [June 12, 2021, 12:33am UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/6 "2021-06-12T00:33:47Z")

</div>

> [@juliohm](#):
>
> NearestNeighbors.jl

He does this exact benchmark in the readme IIUC

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [June 12, 2021, 12:59am UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/7 "2021-06-12T00:59:02Z")

</div>

I see the plots now. I wish they were numbers though with comparable scenarios in the sense that each parameter combination is “equivalent”. I cannot fully support the statement in the README that says:

> It is important to note that `NearestNeighbors.jl` was designed to return the _exact_ k-nearest-neighbors as quickly as possible, and does not approximate, hence the high accuracy and lower speed.

by just looking at the dots in the plot. Can we really compare the dots in the upper left to the dots in the right of the plot?

BTW It is wonderful to see speed! I am just trying to be “scientifically careful” with the conclusions because nearest neighbors is a really useful tool and I depend a lot on NearestNeighbors.jl in my own packages. If @djpasseyjr could show that there is a real advantage here, I could consider taking a more in-depth look into Shrike.jl to use it in future projects.

---

<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:** [June 12, 2021, 3:47am UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/8 "2021-06-12T03:47:43Z")

</div>

> [@djpasseyjr](#):
>
> I was shocked and thrilled! I am no Julia expert, but the fact that I was able to outperform about 2000 lines of C++ in 500 lines of Julia is a real testament to the power of the language.

Glancing at your code, it should be possible to make it faster still — it seems like you do a lot of “vectorized” programming (ala Matlab/NumPy) allocating arrays in what look like critical loops.

---

<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:** [June 12, 2021, 8:19am UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/9 "2021-06-12T08:19:38Z")

</div>

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](https://en.m.wikipedia.org/wiki/K-d_tree#Degradation_in_performance_with_high-dimensional_data)) 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.

---

<div class="post-metadata">

**Author:** ![djpasseyjr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djpasseyjr/32/23695_2.png) [@djpasseyjr](https://discourse.julialang.org/u/djpasseyjr)\
**Post date:** [June 12, 2021, 12:32pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/10 "2021-06-12T12:32:08Z")

</div>

Super interested in this! Can you point me to some resources for learning how to do this? What parts of the code are you referring to?

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [June 12, 2021, 1:32pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/11 "2021-06-12T13:32:23Z")

</div>

Very nice work. I too have implemented ANN algorithms in Julia (unreleased so far) which perform comparable to C++ implementations in vastly fewer lines of code.

Have you seen [http://ann-benchmarks.com/](http://ann-benchmarks.com/)? It would be good to get this in there for a more comprehensive comparison.

---

<div class="post-metadata">

**Author:** ![gbaraldi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gbaraldi/32/22101_2.png) [@gbaraldi](https://discourse.julialang.org/u/gbaraldi)\
**Post date:** [June 12, 2021, 1:33pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/12 "2021-06-12T13:33:00Z")

</div>

For example, on the function `traverse_tree` you could probably preallocate the mask array and the \_get\_split array. Which would increase performance a little bit.

---

<div class="post-metadata">

**Author:** ![djpasseyjr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djpasseyjr/32/23695_2.png) [@djpasseyjr](https://discourse.julialang.org/u/djpasseyjr)\
**Post date:** [June 12, 2021, 2:14pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/13 "2021-06-12T14:14:30Z")

</div>

The way I see it, it depends on what you need. If you need the exact k nearest neighbors, then stick with NearestNeighbors.jl. If 80% of the exact nearest neighbors (with the remaining being 20% points that are close) is good enough, then you can get a speed boost by using an approximate nearest neighbors algorithm.

In [this](https://arxiv.org/abs/1602.00370) paper, the authors construct a nearest neighbor graph, by drawing edges between a point and it’s nearest neighbors. Because the graph just gives a topology to the data, and it doesn’t need to be exact, they use an approximate nearest neighbors search to speed things up.

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [June 12, 2021, 3:06pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/14 "2021-06-12T15:06:44Z")

</div>

[NearestNeighborDescent.jl](https://github.com/dillondaudert/NearestNeighborDescent.jl) is also a pure Julia package for approximate nearest neighbors; might be worth adding it to your benchmarks.

---

<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:** [June 12, 2021, 3:23pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/15 "2021-06-12T15:23:46Z")

</div>

> [@djpasseyjr](#):
>
> The way I see it, it depends on what you need. If you need the exact k nearest neighbors, then stick with NearestNeighbors.jl. If 80% of the exact nearest neighbors (with the remaining being 20% points that are close) is good enough, then you can get a speed boost by using an approximate nearest neighbors algorithm.

Other than thinking about ANN vs exact, I also think it is quite important to also benchmark the two packages on your specific data set. As an example using 3-dimensional points (and please correct me if I messed up some of the hyper parameters for Shrike.jl, I used those I found in the READMEl):

```julia
julia> dim = 3; n_points = 10^4; X = rand(dim, n_points); k = 10;

julia> using Shrike;

julia> @time shi = ShrikeIndex(X; depth=6, ntrees=5);
  0.199808 seconds (3.00 k allocations: 11.166 MiB)

julia> @time nn = allknn(shi, k; vote_cutoff=1, ne_iters=0);
 13.058128 seconds (379.93 k allocations: 358.101 MiB, 76.59% gc time)

julia> using NearestNeighbors;

julia> @time kd_tree = KDTree(X);
  0.006030 seconds (27 allocations: 657.781 KiB)

julia> @time nn2 = knn(kd_tree, X, k);
  0.017842 seconds (50.01 k allocations: 5.112 MiB)

```

---

<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:** [June 12, 2021, 8:59pm UTC](https://discourse.julialang.org/t/ann-shrike-jl-julia-beats-optimized-c-fast-accurate-approximate-nearest-neighbor-search/62763/16 "2021-06-12T20:59:23Z")

</div>

> [@djpasseyjr](#):
>
> Can you point me to some resources for learning how to do this?

Read the performance tips in the manual. Another productive thing to do is to post a small self-contained snippet of the most performance-critical section of your code, along with sample inputs, and ask for advice on speeding it up.