# SimilaritySearch.jl: A package for searching approximate nearest neighbors efficiently

**URL:** <https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056>\
**Category:** Package Announcements\
**Tags:** package\
**Created:** [February 9, 2022, 1:42am UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056 "2022-02-09T01:42:45Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Eric\_Sadit\_Tellez](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eric_sadit_tellez/32/33615_2.png) [@Eric\_Sadit\_Tellez](https://discourse.julialang.org/u/Eric_Sadit_Tellez)\
**Post date:** [February 9, 2022, 1:42am UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/1 "2022-02-09T01:42:45Z")

</div>

Hello everybody,

We are glad to announce the package [SimilaritySearch.jl](https://github.com/sadit/SimilaritySearch.jl) package. The SimilaritySearch.jl package uses a graph index and search heuristics (beam search) to solve queries fast and accurately; the current version is auto-tuned for some minimum quality or for achieving a tradeoff between speed, accuracy, memory, and construction time (all of these are opposite objectives in this kind of algorithms). It has some level of multithreading support (searching and construction). Also, it achieves performances very close to state-of-the-art methods (or even be. Yet, it can use any SemiMetric defined in [Distances.jl](https://github.com/JuliaStats/Distances.jl) and the full speed with your distance definitions.

I also want to mention that the package comes with some distance functions definitions like Levenshtein distances, distances between sets defined as ordered lists, bit-based hamming distance, Hausdorff distance, and some dense-vector based distance functions (some of them are repeated with Distances.jl, some refactoring is needed).

The documentation is still in progress, but we have an [arxiv](https://arxiv.org/pdf/2201.07917.pdf) paper with benchmarks and a repository with several [demonstrations](https://github.com/sadit/SimilaritySearchDemos) if you are interested in some examples of how to use it. Please consider that these demonstrations also uses a modified version of the UMAP.jl package. You can find the modified UMAP.jl [here](https://github.com/sadit/UMAP.jl).

We will be happy if this package helps you in any way. Contributions are also welcome.

Regards,  
Eric

---

<div class="post-metadata">

**Author:** ![Eric\_Sadit\_Tellez](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eric_sadit_tellez/32/33615_2.png) [@Eric\_Sadit\_Tellez](https://discourse.julialang.org/u/Eric_Sadit_Tellez)\
**Post date:** [March 11, 2022, 11:15pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/2 "2022-03-11T23:15:06Z")

</div>

Dear all,

We are glad to comment that we have improved the SimilaritySearch package’s [documentation](https://sadit.github.io/SimilaritySearch.jl/dev/). We also worked on a site for examples and demos.

[https://sadit.github.io/SimilaritySearchDemos/](https://sadit.github.io/SimilaritySearchDemos/)

You can find some basic examples and other more elaborate UMAP visualizations. We had also added some examples with the `ManifoldLearning` package.

In particular, we added several Pluto notebooks and static HTML previews that can run in _mybinder_.  
Some examples are perhaps too costly for running in single-threaded systems, but they will run anyway. Please note that some are better run in a local system since they will download large datasets that may take too long. In any case, please be patient.

If you like the package and find it helpful, please be kind and put a star on Github’s repository.

If you find any issue or request, please file an issue or comment on Github.

Kind regards,  
Eric

---

<div class="post-metadata">

**Author:** ![TheLateKronos](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thelatekronos/32/12824_2.png) [@TheLateKronos](https://discourse.julialang.org/u/TheLateKronos)\
**Post date:** [March 12, 2022, 11:14pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/3 "2022-03-12T23:14:40Z")

</div>

Looks nice! Could you (or @kristoffer.carlsson ) contrast this package with [NearestNeighbors.jl](https://github.com/KristofferC/NearestNeighbors.jl)?

---

<div class="post-metadata">

**Author:** ![Eric\_Sadit\_Tellez](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eric_sadit_tellez/32/33615_2.png) [@Eric\_Sadit\_Tellez](https://discourse.julialang.org/u/Eric_Sadit_Tellez)\
**Post date:** [March 13, 2022, 4:49pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/4 "2022-03-13T16:49:45Z")

</div>

Hi @TheLateKronos

The `SearchGraph` index structure in `SimilaritySearch` is an approximate similarity search method, in the same niche that the [HNSW](https://github.com/nmslib/hnswlib)/[HNSW.jl](https://github.com/JuliaNeighbors/HNSW.jl) and the (pyNNDescent)[[PyNNDescent API Guide — pynndescent 0.5.0 documentation](https://pynndescent.readthedocs.io/en/latest/api.html)][NNDescent.jl]/([https://github.com/dillondaudert/NearestNeighborDescent.jl](https://github.com/dillondaudert/NearestNeighborDescent.jl)) or [SCANN](https://github.com/google-research/google-research/tree/master/scann). Focused on medium sizes (10^5-10^8) datasets with high dimensionality. As these alternatives, ideally, it works with any distance function and improves these in aspects like memory and construction time and the easy inline auto-tuning feature.

I didn’t benchmark yet against `NearestNeighbors.` However, the rapid answer is that `KDTree` and `Balltree` will perform better for lower dimensional datasets. Mainly, KDTrees uses the structure of the data (vector’s coordinates), and therefore it works better for certain distance functions (Minkowski ones). The Balltree works for general metrics spaces but also low dimensions. Both indeed have faster constructions and lower memory requirements.

The rules of thumb (to be proved…) should be:

- If you have low dimensional data, use `NearestNeighbors.`
- If you have high dimensional data and can afford the approximation issue, use `SimilaritySearch.`
- For weird distance functions, perhaps you want to use `SimilaritySearch` since it indeed can work faster if the intrinsic dimensionality is high

Some nice features to take into account.

- `SearchGraph` supports multithreading; it works pretty fast for large datasets
- In contrast with the original (python) `NNDescent` and `HNSW,` `SearchGraph` is made in Julia, and therefore user-defined distance functions can run quite fast
- It has an online auto-tuning feature so that you ask for some quality, and it will try to adjust to it; of course, there is always a cost of some performance marker.
- Computing the all knn graph is quite fast, it supports multithreading, and also it is optimized for doing it quickly. This feature is designed for UMAP and ManifoldLearning techniques etc.

Regards,  
Eric

---

<div class="post-metadata">

**Author:** ![JAgho](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jagho/32/33240_2.png) [@JAgho](https://discourse.julialang.org/u/JAgho)\
**Post date:** [March 13, 2022, 5:46pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/5 "2022-03-13T17:46:00Z")

</div>

This looks really useful for my work! Thank you so much for providing it (and documentation!)

Is it possible to update the graph at all, or is it constructed once per use?

---

<div class="post-metadata">

**Author:** ![Eric\_Sadit\_Tellez](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eric_sadit_tellez/32/33615_2.png) [@Eric\_Sadit\_Tellez](https://discourse.julialang.org/u/Eric_Sadit_Tellez)\
**Post date:** [March 13, 2022, 6:45pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/6 "2022-03-13T18:45:50Z")

</div>

`SearchGraph` supports insertions via `push!` (one item) and `append!` (many objects at once, taking advantage of multithreading). The structure has an incremental construction.

Currently, there is no support for deletion or updates. Nonetheless, update operations can be implemented directly if the modification has little impact on the neighborhood of the modified object; clearly, the latter is a kind of application and domain-specific treat. General updates and deletions are tricky since they may impact results quality if applied frequently.

---

<div class="post-metadata">

**Author:** ![davidbp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidbp/32/463_2.png) [@davidbp](https://discourse.julialang.org/u/davidbp)\
**Post date:** [March 13, 2022, 8:59pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/7 "2022-03-13T20:59:37Z")

</div>

Very interesting package. Thanks a lot for sharing this! I wonder how much faster it could go if instead of computing the exact distances as fitness it could leverage approximated distances with ADC like in PQLinearScann, along the lines of [[2203.02505] ARM 4-BIT PQ: SIMD-based Acceleration for Approximate Nearest Neighbor Search on ARM](https://arxiv.org/abs/2203.02505) . Julia seems an excellent language to build an Approximate Nearest Neighbour Search toolbox.

---

<div class="post-metadata">

**Author:** ![Eric\_Sadit\_Tellez](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eric_sadit_tellez/32/33615_2.png) [@Eric\_Sadit\_Tellez](https://discourse.julialang.org/u/Eric_Sadit_Tellez)\
**Post date:** [July 5, 2022, 4:53pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/8 "2022-07-05T16:53:50Z")

</div>

Happy to share that our JOSS paper about the [`SimilaritySearch.jl`](https://github.com/sadit/SimilaritySearch.jl) package has been accepted for publication. It covers the last version (v0.9.3) with some speedups compared with `v0.8` due to several minor improvements and the use of the `Polyester.jl` package instead of plain `Threads.` We also updated documentation and examples [https://sadit.github.io/SimilaritySearchDemos/](https://sadit.github.io/SimilaritySearchDemos/).

[https://twitter.com/JOSS\_TheOJ/status/1544336092798668800?s=20&t=vPnEnaTafp0hwWB4B-dNLQ](https://twitter.com/JOSS_TheOJ/status/1544336092798668800?s=20&t=vPnEnaTafp0hwWB4B-dNLQ)

---

<div class="post-metadata">

**Author:** ![jbytecode](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jbytecode/32/17719_2.png) [@jbytecode](https://discourse.julialang.org/u/jbytecode)\
**Post date:** [July 5, 2022, 6:55pm UTC](https://discourse.julialang.org/t/similaritysearch-jl-a-package-for-searching-approximate-nearest-neighbors-efficiently/76056/9 "2022-07-05T18:55:48Z")

</div>

congrats!