SimilaritySearch.jl

SimilaritySearch.jl is a library for nearest neighbor search. In particular, it contains the implementation for SearchGraph, a fast and flexible search index using any metric function. It is designed to support multithreading in most of its functions and structures.

The package provides the following indexes:

• ParallelExhaustiveSearch: A brute force search index where each query is solved using all available threads.
• ExhaustiveSearch: A brute force search index, each query is solved using a single thread.
• SearchGraph: An approximate search index with parallel construction.
• InvertedFiles.InvertedFile: An inverted-index structure for sparse vectors, Maximum Inner Product Search (MIPS), and set search (Jaccard, Dice, Intersection, CosineSet, RogersTanimoto, and any other distance via a direct-evaluate fallback).

The main set of functions are:

• search: Solves a single query.
• searchbatch: Solves a set of queries.
• allknn: Computes the $k$ nearest neighbors for all elements in an index.
• neardup: Removes near-duplicates from a metric dataset.
• closestpair / closestpairs: Computes the closest pair (or the $k$ closest pairs) in a metric dataset.
• bichromatic_closestpair / bichromatic_kclosestpairs / bichromatic_metricjoin: The same closest-pair family, but between two different datasets (e.g., "for every object in B, what's its closest match in A?"), plus a metric join when neither a fixed radius nor a match count per element is known ahead of time.
• fft / dnet / randsel / multirandsel: Pick a diverse, well-separated, or representative subset of a dataset (the KCenters submodule).

The precise definitions of these functions and the complete set of functions and structures can be found in the documentation, which also includes a from-scratch tutorial series covering databases, distances, SearchGraph, these whole-dataset operations, parallelism, persistence, logging, inverted files, and quantization/bit sketches.

What each release series brings

The package follows semantic versioning; a series (1.5.x, 1.4.x, ...) adds features without removing any that worked before. Patch releases inside a series are fixes and performance work.

1.5

• Multi-bit sketches. Projections.QuantSketch keeps 2, 4 or 8 bits per hyperplane instead of a single sign bit — the same fitted model, more precision per unit of memory — and Projections.SketchedSearch packages the whole encode/index/rerank pipeline as an ordinary index. index!(idx, ctx, :bitsketch; width) bootstraps a SearchGraph from those wider codes.
• Radius-bounded (ε-ball) search over SearchGraph. Passing a RadiusSorted/RadiusHeap to search now navigates the graph instead of crashing, and optimize_index!(...; radius=ε) tunes the index for that workload (with MaxMatchError, the only error function that applies when a query's true ball can be empty). The answer is approximate, as any graph search is; ExhaustiveSearch remains exact.
• Stored quantized databases can be rebuilt from their fields. SQu4Database/SQu8Database accept (E, Q) back, so a persisted per-column database no longer has to be re-quantized from the Float32 matrix it came from.
• Quantized databases grow, over any storage. Both families are one ScalarQuant.QuantDatabase whose codes live in any AbstractDatabase of UInt8 vectors: a BlockMatrixDatabase or an MMapMatrixDatabase makes push_item!/append_items! quantize on the way in, so a SearchGraph builds over a quantized database one item at a time and the codes can outlive the process. db.Q is therefore a database now, not a Matrix{UInt8} (db.Q.matrix for the default MatrixDatabase); the constructors accept either. There is one SQVec{B} vector type and one set of distances (ScalarQuant.SqL2() and friends) for every width and both families; the per-width names remain as aliases. L1 at 2 bits takes the absolute value it skipped, NormCosine exists at 4 and 2 bits, and a GlobalQuantDatabase rejects a dimension that does not fill its last byte instead of reading a plain query past its end.
• AsymmetricSearchGraph. A graph over quantized storage that inserts and searches with the raw objects, evaluated against the stored codes, so its edges are chosen on the exact distance; a SearchGraph over the same database is the symmetric one, codes against codes. Both are AbstractSearchGraphs, and the way of working is fixed when the instance is built. It is also the path for asymmetric estimators over sketches: an AbstractEstimator is a distance that says through encode what the storage receives and re-evaluates inside its own evaluate when its error model says it must, transparently to the graph; one serializable type, its parameters as fields. ScalarQuant.Cosine accepts a plain vector too.
• RaBitQ submodule. The RaBitQ estimator (Gao & Long, 2024) over that graph: RaBitQCosine/RaBitQL2 store the sign bits of the rotated vector plus three scalars and evaluate a raw query against them with an unbiased estimate and a per-object error bound (a SIMD signed sum, 67 ns per 384-d pair); RaBitQRefined keeps a fallback beside the bits, RaBitQExactFallback (Float32/Float16) or RaBitQVectorFallback (scalar-quantized), and re-evaluates from it inside the estimate when the bound cannot rule an object out.
• ScalarQuant.SQEncoder. The scalar quantizers as the encoder of an AsymmetricSearchGraph, with an optional rotation in front: it uses the estimator interface but carries no error model, since a codification has no error to exploit. Its quantizer is named by the module (SQgu4, SQu8, ...) and its rotation by the object, Projections.qr(dim, dim), the new Projections.RandomizedHadamard (random signs and the Walsh-Hadamard transform, dim log dim), or nothing; on the SISAP 2025 ccnews benchmark the rotation moved recall by less than 0.01 at every width and cost 30-50 µs per query.
• Scores with error bars. bootstrapscore(recallscore, gold, res) resamples the queries and returns the macro score with its standard deviation and a percentile interval, over any per-query score; perqueryscores gives the vector it draws from, and the bootstrap of the per-query differences of two results is the paired comparison. matcherror and the new macromatcherror are score functions in their own right now, exported beside recallscore/macrorecall (issue #92).
• The Walsh-Hadamard transform is a butterfly, not an FFTW plan. HadamardProjection used to build an FFTW plan on every per-vector transform!, under FFTW's global lock: 170-400 µs per vector, worse with threads. It is now a plain in-place butterfly on both paths, its first three passes and its 1/n scale folded into Vec{8} operations: 0.1-4.6 µs per vector at 128-4096 dimensions (500x), 33-800 ns per column of a matrix over 64 threads (60x the batched FFTW call), bit for bit the same values; Hadamard.jl and FFTW leave the dependency tree (issue #89).
• Faster quantized distances. Per-column SqL2/NormCosine are computed from integer code sums rather than dequantizing coordinate by coordinate (up to 3.5x, and an order of magnitude more accurate), and the global SQgu* kernels vectorize the remainder they used to leave to scalar code.

1.4

• BKT, an exact BK-tree index for integer-valued metrics (Levenshtein, DamerauLevenshtein, LCS), built in parallel over a flat per-object workload.
• beginbatch, which lets a distance hand each batch its own scratch buffers — replacing the Channel-based pool the edit distances used, measured ~80x faster on short words.
• @BATCHES accepts :dynamic and uses it by default, so nested and concurrent parallel regions are safe.

1.3

• Metric-hyperplane bit sketches: DistantHyperplanes, AnchoredDistantHyperplanes, RandomHyperplanes, plus PCAProjection as a data-fitted alternative to random projections.
• index!(idx, ctx, :bitsketch), a fast bootstrap that builds an empty SearchGraph's topology in sketch space (method=:gaussian, :qr, :adh, or :external for precomputed sketches).
• MaxMatchError, a continuous, distance-based goal for optimize_index!, next to MinRecall.
• DamerauLevenshtein, and String/SubString accepted directly by the edit distances.

1.2

• MMapMatrixDatabase, a disk-backed growable database via mmap.
• Two logging channels: reporters receive progress (INFORM) and observers react to structural events (OBSERVE, e.g. :add!), so persistence can hook into an index without printing anything.
• The Selection submodule: fft, dnet, randsel, multirandsel and neardup under one roof, each returning a typed selection rather than loose arrays.

Similarity search ecosystem in Julia

Currently, there exists several packages dedicated to nearest neighbor search, for instance we have NearestNeighbors.jl, RegionTrees.jl, and JuliaNeighbors implement search structures like kd-trees, ball trees, quadtrees, octrees, bk-trees, vp-tree and other multidimensional and metric structures. These structures work quite well for low dimensional data since they are designed to solve exact similarity queries.

There exist several packages performing approximate similarity search, like Rayuela.jl using product quantization schemes, the wrapper for the FAISS library Faiss.jl. The FAISS library provides high-performance implementations of product quantization schemes and locality-sensitive hashing schemes, along with an industrial-strength implementation of the HNSW index. The NearestNeighborDescent.jl implements the search algorithm behind pynndescent.

The SimilaritySearch.jl package tries to enrich the ecosystem with search structures and algorithms designed to take advantage of multithreading systems and a unique autotuning feature that simplifies its usage for practitioners. These features are succinctly and efficiently implemented due to the Julia programming language dynamism and performance. Regarding performance characteristics, the construction times are vastly reduced compared to similar approaches without reducing search performance or result quality.

Installing SimilaritySearch

You may install the package as follows

] add SimilaritySearch.jl

also, you can run the set of tests as follows

] test SimilaritySearch

Using the library

Please see examples. You will find a list of Jupyter and Pluto notebooks, and some scripts that exemplifies its usage.

Contribute

Contributions are welcome. Please fill a pull request for documentating and implementation contributions. For issues, please fill an issue with the necessary information (see below.) If you already have a solution please also provide a pull request.

Issues

Report issues in the package providing a minimal reproducible example. If the issue is data dependant, please don't forget to provide the necessary data to reproduce it.

Limitations of SearchGraph

The main search structure, the SearchGraph, is a graph with several characteristics, many of them induced by the dataset being indexed. Some of its known limitations are related to these characteristics. For instance:

• Metric distances work well; on the other hand, semi-metric should work, but routing capabilities are not yet characterized.
• Even when it performs pretty well compared to alternatives, discrete metrics like Levenshtein distance and others that take few possible values may also get low performances.
• Something similar will happen when there are many near-duplicates (elements that are pretty close). In this case, it is necessary to remove near-duplicates and put them in bags associated with some of its near objects.
• Very high dimensional datasets will produce long-tail distributions of the number of edges per vertex. In extreme cases, you must prune large neighborhoods and enrich single-edge paths.

About the structures and algorithms

The following manuscript describes and benchmarks the SearchGraph index (package version 0.6):

@article{tellezscalable,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={1--15},
  publisher={Springer}
}

The current algorithm (version 0.8 and 0.9) is described and benchmarked in the following manuscript:

@misc{tellez2022similarity,
      title={Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization}, 
      author={Eric S. Tellez and Guillermo Ruiz},
      year={2022},
      eprint={2201.07917},
      archivePrefix={arXiv},
      primaryClass={cs.IR}
}

This package is also described in the JOSS paper:

Eric S. Tellez and Guillermo Ruiz. SimilaritySearch.jl: Autotuned nearest neighbor indexes for Julia. Journal of Open Source Software https://doi.org/10.21105/joss.04442.

About v0.9.X series

The algorithms of this version are the same as v0.8 but break API compatibility:

• Now, it uses the Polyester package to handle multithreading instead of Threads.@threads
• Multithreading methods are enabled by default if the process is started with several threads; in v0.8 was the contrary
• allknn now preserves self-references to simplify algorithms and improve efficiency (allknn in v0.8 removes self-references automatically)

Others:

• Adds function docs and benchmarks
• Adds SearchGraph graph pruning methods
• Removes the timedsearchbatch function

About v0.10.X series

It makes easy to adjust the SearchGraph structure to different workloads and applications. For instance,

• More control for construction parameters
• Loading and saving
• Refactors search API to be consistent across structs

Please refer to https://github.com/sadit/SimilaritySearchDemos and https://github.com/sadit/SimilaritySearch.jl/blob/main/test/testsearchgraph.jl for working examples.

About v0.11 series

It introduces a major refactoring. In particular, it makes explicit use of context objects for most functions. It also introduces simple logging procedures. However, we preserve compatibility in many public functions using implicit use of default context objects.

About v0.12 series

Breaking changes:

• The context objects are now required; there are no default use of them.
• Added ProgressMeter for allknn, a small impact in the performance but pretty nice for large datasets.
• Removes dependencies of LoopVectorization; we only use it for @turbo based distance functions; these functions can be deployed in another package.

New features:

• Distances and dataset wrappers to handle non-Float32 that are casted to Float32 just before distance computations. This could improve the performance in several high throughput setups.

About v0.15 series

Finishes a threading-model migration: every parallel loop now uses this package's own @BATCHES macro (a thin, native Threads.@threads-based construct), and the Polyester/StrideArraysCore dependencies are gone. This isn't just a simplification -- Polyester (and the low-level codegen machinery it and StrideArraysCore build on) has measurable performance regressions on Julia 1.12 and is a poor fit for static/binary deployment targets (PackageCompiler, WASM) that don't tolerate its runtime code-generation approach well. Native Threads.@threads has neither problem, which is the actual point: it's what lets this package properly support Julia 1.12+ and those deployment targets going forward.

Also in this series:

• Scalar quantization (ScalarQuant): reorganized into per-scheme submodules (SQu2/SQu4/SQu8/SQgu4/SQgu8) behind a common API, with SIMD-accelerated global 4-/8-bit quantizers.
• Random/Hadamard projections and bit sketches (Projections): random-rotation and Hadamard-transform dimensionality reduction, plus SimHash-style bit sketches.
• Distance functions reorganized into independent submodules under Dist.
• Sparse-matrix support via SimilaritySearch.Special.Sparse.
• Assorted bug fixes and expanded docstrings across the package.

Breaking changes:

• Removes StrideMatrixDatabase; use MatrixDatabase instead (it already accepts any AbstractMatrix, including a user-provided StrideArray).
• Removes the StrideArraysCore and Polyester dependencies (Polyester had already been unused internally since @BATCHES replaced it).

About v1.0 series

New features:

• apps/simsearch: a standalone CLI application (build/search/evaluate/analyze subcommands) for working with SimilaritySearch.jl indexes from the shell, installable as a Julia app via pkg> app develop apps/simsearch.
• Special.Spherical: a spherical embedding (Neyshabur & Srebro) that turns Maximum Inner Product Search into ordinary nearest-neighbor search.
• A from-scratch tutorial series under docs/src/tutorial/ (databases, distances, SearchGraph, whole-dataset operations, parallelism, persistence, logging), linked from the documentation.

Breaking changes:

• Distance/block-evaluation counters moved off the KnnHeap/KnnSorted result objects and onto the context objects (GenericContext/SearchGraphContext), tracked per parallel batch. Read them with distance_evaluations/block_evaluations (mean per batch) or distance_stats/block_stats (min/mean/max per batch); optimize_index!'s internal cost function was simplified accordingly.

About v1.1 series

New features:

• InvertedFiles/Intersections: inverted-file index and posting-list intersection submodules, moved in from TextSearch.jl so sparse-vector, MIPS, and set search (Jaccard/Dice/Intersection/CosineSet/RogersTanimoto, or any other distance via a direct-evaluate fallback) are available directly from this package. Originally shipped as separate BinaryInvertedFile/WeightedInvertedFile types, later merged into a single InvertedFile.
• Bichromatic submodule: bichromatic_closestpair/bichromatic_kclosestpairs (the closest pair(s) between two distinct datasets) and bichromatic_metricjoin (a metric join between two datasets when neither a fixed radius nor a match count per element is known ahead of time). closestpair/closestpairs are now defined as the same-dataset special case of these.
• KCenters submodule: fft and dnet moved here, joined by two new prototype-selection algorithms, randsel (uniform random sampling) and multirandsel (randomized farthest-first, a middle ground between randsel and fft).
• @BATCHES scheduler control: every context now carries a scheduler field (:dynamic/:default/:static/:greedy/:sequential), so parallel loops can be forced to run single-threaded (:sequential) without changing Threads.nthreads(). The global default is :dynamic (set_batch_scheduler!/SIMSEARCH_BATCH_SCHEDULER): unlike :static, it lets unrelated indexes run their parallel loops concurrently in one process.
• A tutorial page for the InvertedFiles/Bichromatic submodules and for ScalarQuant/bit-sketch quantization; multi-version documentation deployment (dev/stable/v#.#).
• CI now runs on Julia 1.12.

Breaking changes:

• KnnHeap/KnnSorted switched to a struct-of-arrays layout (parallel ids::Vector{UInt32}/dists::Vector{Float32}, instead of a single Vector{IdDist}); searchbatch/searchbatch!/allknn now return/fill an (ids, dists) tuple of matrices instead of a single Matrix{IdDist}.
• The distance/block-evaluation counter fields were renamed to costdists/costblocks.