struct ExhaustiveSearch{DistanceType<:PreMetric,DataType<:AbstractDatabase} <: AbstractSearchIndex

ExhaustiveSearch(dist::PreMetric, db::AbstractDatabase)

A brute-force (sequential) exact index that solves queries by evaluating dist between the query and every element in db. Useful as a gold-standard baseline or for small datasets where an approximate index is not worth its construction cost.

Arguments

• dist: the distance function
• db: the database being indexed

struct ParallelExhaustiveSearch{DistanceType<:PreMetric,DataType<:AbstractDatabase} <: AbstractSearchIndex

ParallelExhaustiveSearch(dist::PreMetric, db::AbstractDatabase)
ParallelExhaustiveSearch(dist::PreMetric, db::AbstractVecOrMat)

A brute-force exact index, like ExhaustiveSearch, but that solves each query by evaluating dist against every element of db in parallel (across Threads.nthreads() tasks). Each batch of the underlying @BATCHES call accumulates its own private, lock-free top-k buffer (indexed by @batchid()), merged into the final result once all batches join – see search for details. Useful as a gold-standard baseline for small-to-medium datasets where parallelizing a single query is beneficial.

Note that this should not be used in conjunction with searchbatch(...; parallel=true) since they will compete for the same thread pool.

Arguments

• dist: the distance function
• db: the database being indexed, given either as an AbstractDatabase or as a raw vector/matrix

abstract type AbstractSearchGraph <: AbstractSearchIndex end

The graph indexes: a SearchGraph, which inserts and searches with the objects as its database stores them, and the structures that specialize how the graph works with its data without changing the graph itself – AsymmetricSearchGraph, which stores a transformed form and works with the raw objects. Each is one way of working, fixed when the instance is built.

SearchGraph(dist::PreMetric, db::AbstractDatabase; adj=AdjList(UInt32), hints=UInt32[],
              algo=Ref(BeamSearch()), len=Ref(zero(Int64))) -> SearchGraph

SearchGraph index. It stores a set of points that can be compared through a distance function dist. The performance is determined by the search algorithm algo and the neighborhood policy. It supports callbacks to adjust parameters as insertions are made.

Keyword Arguments

• dist: The distance function (a PreMetric) used to compare stored objects, e.g., Dist.SqL2().
• db: The database of indexed objects, see AbstractDatabase (e.g., MatrixDatabase, VectorDatabase).
• adj: The adjacency list storing the graph's direct links between objects.
• hints: Initial points for exploration (empty hints imply using random points).
• algo: The local search algorithm used to solve queries, stored as a Ref{BeamSearch} (see BeamSearch).
• len: The number of stored elements, as a Ref{Int64}; use length(index) instead of accessing it directly.

Note: Parallel insertions should be made through append! or index! function with parallel_block > 1

Examples

using SimilaritySearch
const Dist = SimilaritySearch.Dist

X = rand(Float32, 8, 10^4)          # 10^4 vectors of dimension 8
db = MatrixDatabase(X)

G = SearchGraph(Dist.SqL2(), db)
ctx = SearchGraphContext()
index!(G, ctx)                       # builds the graph (inserts all items in db)

q = rand(Float32, 8)
res = knnqueue(ctx, 8)                # a knn result set for k=8
search(G, ctx, q, res)                # solves a single query

Q = MatrixDatabase(rand(Float32, 8, 10^2))
knns = searchbatch(G, ctx, Q, 8)      # solves many queries at once

AsymmetricSearchGraph(dist::PreMetric, db::AbstractDatabase; kwargs...)

A SearchGraph whose database stores a transformed form of the objects it is given – quantized codes, today, from a ScalarQuant.QuantDatabase that quantizes on push_item!; the codes of an AbstractEstimator tomorrow – and which inserts and searches with the objects in their raw form, evaluated against the stored form by dist. It is the asymmetric mode of the graph: each new item picks its neighbors by its exact distance to the stored codes, so the quantization error is not baked into the edges, and every query is evaluated the same way.

A SearchGraph over the same database is the symmetric mode, codes against codes on both sides: cheaper at every step, and the only one available when the codes are all there is (a database read back from storage). The mode is a property of the instance, not of a call: this type never inserts or searches with the stored form, and a SearchGraph never sees the raw objects. Which one pays was measured on the SISAP 2025 ccnews benchmark (issue #86): the asymmetric edges are better below 8 bits (searched in exact precision, 0.901 against 0.882 of recall@10 at 4 bits and 0.940 against 0.884 at 2), but a query evaluated against codes cannot cash that (0.81 at 4 bits and 0.65 at 2 with either graph), so the asymmetric graph is the one to build when its distance re-evaluates what the codes alone cannot resolve, and the symmetric one otherwise.

Arguments

• dist: evaluates a raw object against a stored one, and says through encode(dist, obj) what is stored and through encodequery(dist, q) what a raw query becomes before being evaluated (once per query, once per inserted item). It is what the graph navigates with, at insertion and at query time, and what the hyperparameters callback tunes with – on a sample of the raw items being inserted, not on stored codes. ScalarQuant.SqL2, L1, NormCosine and Cosine all take a plain vector against an SQVec and encode nothing (the QuantDatabase quantizes); an AbstractEstimator encodes its own codes and re-evaluates inside its evaluate when its error model says it must.
• db: the storage, any growable AbstractDatabase whose push_item! accepts what encode(dist, obj) produces
• remaining keywords go to the SearchGraph constructor (adj, hints, algo)

Interface

append_items!(g, ctx, items) and push_item!(g, ctx, item) take raw objects; search/searchbatch take raw queries; optimize_index!(g, ctx, kind; queries) requires raw queries, since the index holds no raw object to sample from. index!(g, ctx) and rebuild only have the stored form to work with and are not available: they are the symmetric operations, use a SearchGraph over the same database for them.

Examples

using SimilaritySearch, SimilaritySearch.ScalarQuant

X = randn(Float32, 64, 10_000)
db = GlobalQuantDatabase(4, BlockMatrixDatabase(32, UInt8), extrema(X); dim=64)  # stores 4-bit codes
G = AsymmetricSearchGraph(ScalarQuant.SqL2(), db)         # SqL2 evaluates Float32 against codes
ctx = SearchGraphContext(; reporters=[])
append_items!(G, ctx, MatrixDatabase(X))                  # edges on Float32 vs codes; storage at 4 bits
search(G, ctx, randn(Float32, 64), knnqueue(KnnSorted, 10))

An estimator that stores a coarse code next to a finer one and re-evaluates from the fine one only when the coarse estimate is close enough to matter:

struct TwoLevel <: AbstractEstimator
    coarse::GlobalQuantDatabase{2}    # the parameters; empty databases, used to quantize
    fine::GlobalQuantDatabase{8}
    τ::Float32                        # coarse estimates above it are far enough to trust
end
SimilaritySearch.encode(e::TwoLevel, v) = (ScalarQuant.quantize(e.coarse, v), ScalarQuant.quantize(e.fine, v))
function SimilaritySearch.evaluate(e::TwoLevel, q, stored)
    d = evaluate(ScalarQuant.SqL2(), q, stored[1])
    d > e.τ ? d : evaluate(ScalarQuant.SqL2(), q, stored[2])
end
SimilaritySearch.evaluate(::TwoLevel, a::Tuple, b::Tuple) = evaluate(ScalarQuant.SqL2(), a[2], b[2])   # candidates among themselves
G = AsymmetricSearchGraph(TwoLevel(c2, c8, 0.5f0), VectorDatabase(type=Tuple{SQVec{2,Vector{UInt8}},SQVec{8,Vector{UInt8}}}))

Sketches and estimators

index!(idx, ctx, :bitsketch) builds a SearchGraph's topology from sketches and keeps the raw vectors: it is symmetric on the sketch side, code against code, which is the weaker estimate. This type is the path for the asymmetric estimators, a raw query against a code: the graph only evaluates the distance, and everything the model needs travels in the code it encodes. Two ship with the package: ScalarQuant.SQEncoder, the scalar quantizers as a plain codification with no error model (an optional rotation in front), and the RaBitQ estimators, sign bits with a per-object error bound and, in RaBitQ.RaBitQRefined, a fallback re-evaluated inside the estimate when that bound cannot rule an object out.

abstract type AbstractEstimator <: PreMetric end

A distance that is an estimator: it evaluates a raw query against an encoded object, and may carry an error of its own. It is one plain type whose parameters are fields, so a graph and everything that gives its codes meaning serialize together; nothing in it is a closure.

An estimator implements:

• encode(est, obj): what is stored for the raw obj, the code plus whatever the estimator keeps with it (a norm, a correction term, a finer code);
• encodequery(est, q), when the query side needs preparing: what evaluate takes as its query for the raw q. A rotation, for one – applying it inside evaluate would cost D^2 per pair against the D of the estimate, so the graph applies it once per query and once per inserted item. The default is the identity;
• evaluate(est, q, stored): the distance between the raw query q and a stored object, in that order – every index here evaluates its query first. It receives everything the model has – the raw query, the encoded object with what was kept beside the code, and the estimator's own parameters – so a model that can bound its error re-evaluates inside the evaluation when it must, and returns the distance it stands behind. The graph only ever evaluates the distance; whether that was an estimate, a corrected estimate or a re-evaluation is the estimator's business.
• evaluate(est, a, b) between two stored objects as well: the neighborhood filters (SatNeighborhood and its relatives) compare a new item's candidates among themselves to decide which edges to keep, and those candidates are stored objects. That is the symmetric estimate, code against code, and it only shapes the edges; the scalar quantizers' distances already have it.

The no-op estimator is a plain distance: ScalarQuant.SqL2() against an SQVec evaluates the query against the codes and nothing needs correcting. Any PreMetric works as the distance of an asymmetric graph; this type is the documented home for the ones that encode.

encode(dist::PreMetric, obj)

What an AsymmetricSearchGraph stores for the raw obj under dist: the form dist evaluates a raw query against. The default returns obj itself, for a storage that transforms what it stores on its own, as a ScalarQuant.QuantDatabase does under the scalar quantizers' distances. An AbstractEstimator whose codes the storage does not produce overrides it.

Rotates once and quantizes: the SQVec the storage receives.

encode(e, o) -> RaBitQCode

The sign bits of the rotated o, c = ⟨ō, o⟩ / ‖o‖ (scale-free, so it does not depend on how the rotation scales its output), ‖o‖ of the raw vector, and the error scale.

encodequery(dist::PreMetric, q)

What an AsymmetricSearchGraph evaluates dist with on the query side for the raw q: the form evaluate(dist, encodequery(dist, q), stored) takes. The default returns q itself. An AbstractEstimator whose evaluation needs the query prepared once – rotated, projected, quantized on the query side – overrides it, and the graph applies it once per query and once per inserted item (which is the query of its own neighborhood search), never per evaluation.

Rotates once: the Float32 vector the mixed kernels take on the query side.

encodequery(e, q) -> RaBitQQuery

The rotated q, normalized to a unit vector so that the estimate below is one signed sum per pair, and ‖q‖ of the raw vector for the Euclidean distance.

rotate(rot, v) -> Vector{Float32}

Applies the rotation rot to v, returning a fresh Vector{Float32} of the same norm. It is the one thing an estimator that lives in a rotated space asks of its rotation, and the graph pays it once per query and once per inserted item (encodequery, encode), never per evaluation. nothing is the rotation that rotates nothing and only casts; a square Projections.RandomProjections (Projections.qr(dim, dim)) and a Projections.RandomizedHadamard implement it (see Projections.Rotation), and any other type may, together with rotationdim.

rotationdim(rot) -> Int

The dimension rot rotates, so an estimator reads it off its rotation and checks its data against it. A RandomProjections that is not square throws: a projection that changes the dimension is not a rotation.

BKT(dist::Dist.Metric, db::AbstractDatabase; checkmetric::Bool=true)
BKT(db::AbstractDatabase; dist::Dist.Metric, checkmetric::Bool=true)

A BK-tree: an exact index for metrics whose distance takes few distinct, integer values – e.g. Dist.Seqs.Levenshtein, Dist.Bits.Hamming. Each internal node holds a pivot object and buckets its subtree by the exact integer distance to that pivot, so a query prunes a whole subtree with a single distance evaluation.

The structure is built once with index!; it does not support incremental insertion (like Sat, and unlike SearchGraph).

Why integer-valued distances only

The pruning rule is a direct consequence of the triangle inequality: every object x hanging under the child keyed k of a node p satisfies d(p, x) == k exactly, hence d(q, x) >= |d(q, p) - k|, and the whole subtree is discarded when that bound exceeds the covering radius of the result. A continuous distance breaks this twice over: the exact-key bucketing degenerates (almost every pair gets its own bucket, so the tree becomes a list with no pruning power), and the rounding that assigns a bucket breaks the d(p, x) == k invariant the bound relies on.

This is a contract, not a check. index! rounds every distance it observes to an Int32 key and trusts the caller: handing BKT a continuous distance builds a tree that answers queries without complaining and can quietly miss true neighbors. Verifying it cheaply is not possible anyway – the build only ever sees a fraction of the n^2 pairs – so it is stated here rather than half-enforced.

Why a Metric and not a SemiMetric

Pruning needs the triangle inequality, which Dist.SemiMetric does not promise. A relevant example lives in this very package: Dist.Seqs.DamerauLevenshtein is integer-valued but deliberately typed SemiMetric because the restricted/OSA variant violates the triangle inequality, so a BKT built on it can miss true neighbors. The constructor rejects a non-Metric distance for this reason. checkmetric=false overrides it, for either of two quite different reasons: the distance really is a metric and is merely typed loosely, or you knowingly accept an approximate index (see below).

Searching by Damerau-Levenshtein

Two routes, both useful, neither free:

1. Key the tree by DamerauLevenshtein itself (checkmetric=false). Pruning is no longer provably sound, so this is an approximate index. Measured on a 20k-word dictionary with 200 typo queries (transpositions included), it lost nothing at all – recall 1.0 at radius 1, 2 and 3 – at 7.9%/39%/68% of an exhaustive scan. Empirical evidence on one corpus, not a guarantee: it says OSA's triangle-inequality violations are too rare or too small to bite at these thresholds, not that they cannot.
2. Key the tree by Dist.Seqs.Levenshtein, search at radius 2r, then filter the candidates by DamerauLevenshtein. Exact, with no reliance on OSA being a metric: OSA allows every Levenshtein operation plus adjacent transposition, and each transposition can be replayed as two substitutions, so DL <= Lev <= 2*DL and DL(q,x) <= r implies Lev(q,x) <= 2r. The doubled radius costs pruning: on that same dictionary it took 33%/79%/107% of an exhaustive scan for r = 1/2/3, i.e. by r = 3 it is already worse than not having an index.

Both degrade quickly as the threshold grows, which is the general caveat below in its sharpest form: a BK-tree over edit distance is a small-threshold structure.

When a BK-tree pays off

Pruning bites when the result's covering radius is small next to the spread of the distance distribution – the shape of dictionary lookup/spelling correction, where the neighbors sought sit 1-2 edits away while the bulk of the collection sits much farther. It does nothing for a query whose radius covers most of that spread (a large k over data with no near neighbors, e.g. uniformly random strings): every child key then falls inside [d(q,p)-r, d(q,p)+r], the whole tree is visited, and the search degenerates into an exhaustive scan – correct, just with no speedup. That is a property of the data, not of this implementation, and it is why this index ships alongside (rather than replacing) ExhaustiveSearch.

Arguments

• dist: the distance function; must be integer-valued (see above)
• db: the database to index

Keyword Arguments

• checkmetric: whether a non-Dist.Metric distance is rejected (default true)

Examples

using SimilaritySearch

db = VectorDatabase([collect(w) for w in ["form", "from", "fort", "fore", "ford"]])
bkt = BKT(Dist.Seqs.Levenshtein(), db)
ctx = GenericContext()
index!(bkt, ctx)
search(bkt, ctx, collect("fond"), knnqueue(KnnSorted, 3))

PermutedSearchIndex(; index, π, π′=invperm(π))

Wraps a search index together with a permutation π of its identifiers, and defines the related accessor functions. Applying a permutation to the underlying storage (e.g., so that frequently co-accessed objects are stored close together) can improve cache efficiency; this wrapper lets that reordering be applied without changing the identifiers seen by the application.

Keyword Arguments

• index: the wrapped search index.
• π: permutation mapping internal identifiers (as stored in index) to external identifiers.
• π′: inverse permutation, mapping external identifiers to internal identifiers in index; defaults to invperm(π).

Examples

π = shuffle(1:length(index))
p = PermutedSearchIndex(; index, π)

distance(qs::QuantSketch)

The distance function the sketches produced by qs must be compared with: Hamming at 1 bit, and the matching SQgu*.SqL2 (squared Euclidean over the packed codes, evaluated with SIMD without dequantizing) at 2, 4 and 8 bits.

distance(S::SketchedSearch)

The original distance S re-scores its candidates with – the one its results are expressed in. The cheap sketch-space distance is distance(S.qs) instead; see QuantSketch.

distance(index)

Gets the distance function used in the index

search(S::SketchedSearch, ctx::AbstractContext, q, res::AbstractKnnQueue) -> res

Solves q in two stages: sketches it with S's encoder and retrieves factor * maxlength(res) candidates from the sketch index under the sketch distance, then re-scores every candidate with the original distance against the original objects and pushes the results into res. Only the second stage's distances are charged to ctx's evaluation counter by this method; the sketch stage charges its own.

Arguments

• S: the pipeline
• ctx: the running context
• q: the query, in the original space (not pre-sketched)
• res: the result set, which receives ids into database(S) and exact distance(S) values

search(bs::BeamSearch, index::SearchGraph, ctx, q, res, hints, vstate)

Tries to reach the set of nearest neighbors specified in res for q.

• bs: the parameters of BeamSearch
• index: the local search index
• ctx: A SearchGraphContext object with preallocated objects
• q: the query
• res: The result object, it stores the results and also specifies the kind of query
• hints: Starting points for searching, randomly selected when it is an empty collection
• vstate: data structure to mark visited vertices

search(index::SearchGraph, ctx::SearchGraphContext, q, res::AbstractMetricQueue) -> AbstractMetricQueue

Solves the specified query res for the query object q using the SearchGraph index index. It dispatches the work to the local search algorithm stored in index.algo (e.g., BeamSearch), using ctx to access preallocated caches (visited-vertices state, beams) and configuration. The result object res is updated in-place and also returned.

Examples

using SimilaritySearch

# G::SearchGraph and ctx::SearchGraphContext already built and indexed
q = rand(Float32, 8)
res = knnqueue(ctx, 8)     # k=8 nearest neighbors
search(G, ctx, q, res)

search(index::SearchGraph, ctx::SearchGraphContext, q, res::AbstractRadiusQueue; kmin::Int=8) -> res

Solves the radius-bounded (epsilon-ball) query q and fills res with every item the search found within its radius.

The graph is navigated with a BallKnn instead of res itself, and only its in-ball prefix is copied back here. A radius container cannot drive a graph search on its own: it rejects every candidate outside the ball, so it is still empty when the beam needs a starting point (issue #67's segfault), and its maximum is a constant, so the beam's admission test stops shrinking and a search that starts outside the ball dies on its first expansion. BallKnn keeps a kmin-sized navigation reserve that restores both, and the reserve never reaches res.

Unlike the exhaustive indexes, this answer is approximate: it is a subset of the true ball, whose completeness is governed by the same BeamSearch parameters as a k-NN search (bsize and Δ above all). Use an ExhaustiveSearch when the ball must be exact.

Arguments

• index, ctx, q: as in the k-NN method above
• res: the radius container to fill (RadiusSorted/RadiusHeap); its radius is read with covradius

Keyword Arguments

• kmin: size of the navigation reserve. It is the floor of the search's cost – a radius query costs about what a k-NN query with k = kmin costs – and, at the hyperparameters construction leaves behind, it is what keeps a beam starting outside the ball alive. Tuning bsize/Δ for the radius workload makes the choice nearly free, and then 2 is measurably cheaper; the default protects the untuned path. See #67 for the measurements.

search(g::AsymmetricSearchGraph, ctx::SearchGraphContext, q, res::AbstractMetricQueue)

Searches with the raw query q, prepared once by encodequery(distance(g), q) and evaluated against the stored form by the graph's distance.

search(p::PermutedSearchIndex, ctx::AbstractContext, q, res) -> res

Solves query q against the wrapped p.index, then remaps each result's identifier from internal (p.index) space to external (p.π) space, so callers always see identifiers relative to the original, unpermuted dataset.

search(sat::Sat, ctx::AbstractContext, q, res::AbstractKnnQueue) -> res

Solves query q with the spatial access tree, descending from sat.root and pruning subtrees using each internal node's stored covering radius.

search(seq::ExhaustiveSearch, ctx::AbstractContext, q, res::AbstractMetricQueue) -> res

Solves query q by sequentially evaluating the distance between q and every item of the indexed database, pushing each candidate into res.

Arguments

• seq: the exhaustive search index
• ctx: the running context, charged with the distance-evaluation count
• q: the query to solve
• res: the result set that receives the candidates

search(pex::ParallelExhaustiveSearch, ctx::GenericContext, q, res::AbstractKnnQueue) -> res

Solves queries evaluating dist in parallel for the query and all elements in the dataset.

Solves query q by evaluating the distance between q and every item of the indexed database in parallel. Instead of pushing every candidate into the shared res under a lock, each batch accumulates its own private top-k buffer (k = maxlength(res)), indexed by @batchid() – race-free by construction, no lock needed – and all batches' buffers are merged into res once they have all joined (@END, run sequentially, once).

The extra memory this needs is k * @nbatches() IdDist entries: @nbatches() never scales with n (the database size) – getminbatch aims for ~8 batches per thread regardless of n, and @BATCHES's own fast path collapses to a single batch entirely whenever n is small relative to the computed minbatch – so this temporary buffer stays bounded by the thread count and k, not by the size of the database being searched. ctx.maxbatches (default 8 * nthreads(), see GenericContext) directly caps @nbatches() further, for cases with a large k and/or nthreads() where even that bounded buffer is too large; see getminbatch for the trade-offs of capping it (fewer batches can leave threads idle and worsens load-balancing).

Arguments

• pex: the search structure
• ctx: the running context; ctx.maxbatches bounds the number of batches (and thus the size of the temporary k * @nbatches() buffer), passed as getminbatch(ctx, n)
• q: the query to solve
• res: the result set that receives the candidates

search(bkt::BKT, ctx::AbstractContext, q, res::AbstractMetricQueue) -> res

Solves query q, pushing candidates into res. The result is exact: every object the search discards is separated from q by more than the covering radius of res, by the triangle inequality (see BKT).

Works with a k-nearest-neighbor queue (the radius shrinks as res fills up) and with a RadiusSorted/RadiusHeap range queue (a fixed radius) alike, since both answer covradius.

search(idx::AbstractInvertedFile, ctx::InvertedFileContext, q, res::AbstractKnnQueue; t=1)

Searches q in idx using the cosine dissimilarity, it computes the full operation on idx. res specify the query

searchbatch(index, ctx, Q, k::Integer) -> (ids::Matrix{UInt32}, dists::Matrix{Float32})
searchbatch(index, Q, k::Integer) -> (ids::Matrix{UInt32}, dists::Matrix{Float32})

Searches a batch of queries in the given index (searches for k neighbors). Returns a tuple (ids, dists) where both are (k, length(Q)) matrices.

Arguments

• index: The search structure
• Q: The set of queries
• k: The number of neighbors to retrieve
• ctx: caches, hyperparameters, and meta data
• sorted=true: ensures that the results are sorted by distance.

Note: The i-th column in ids/dists corresponds to the i-th query in Q. Note: Unused slots (fewer than k neighbors found) are filled with 0/Inf32.

searchbatch!(index, ctx, Q, ids, dists; sorted) -> (ids, dists)

In-place batch search. Fills ids::AbstractMatrix{UInt32} and dists::AbstractMatrix{Float32} (each of size (k, length(Q))) with the k nearest neighbors of each query in Q.

Arguments

• index: The search structure
• ctx: Context of the search algorithm
• Q: The set of queries
• ids: Output matrix of UInt32 identifiers, size (k, length(Q))
• dists: Output matrix of Float32 distances, size (k, length(Q))

Keyword arguments

• sorted: whether each column should be sorted by distance (default false).

searchbatch!(index, ctx, Q, knns::AbstractVector{<:AbstractMetricQueue}) -> knns

In-place batch search using caller-provided, per-query result containers instead of pre-sized (k, length(Q)) matrices. Unlike the matrix-based searchbatch! above, knns need not hold a uniform, fixed-size container per query: each knns[i] can be any AbstractMetricQueue – a fixed-k KnnSorted/KnnHeap, or a growable, radius-thresholded RadiusSorted/RadiusHeap – and they need not even share the same concrete type. This is the only entry point radius-bounded containers are meant to be driven through; they are not wired into the (ids, dists) matrix form (which requires a uniform k) or into GenericContext/SearchGraphContext's automatic knnqueue(ctx, k) construction (which has no notion of a radius).

Does not call reuse! on the elements of knns – pass already-fresh containers.

Arguments

• index: The search structure
• ctx: Context of the search algorithm
• Q: The set of queries
• knns: One result container per query, length(knns) == length(Q)

Examples

# radius-bounded search: every point within 0.3 of each query, however many that is
knns = [RadiusSorted(0.3f0) for _ in 1:length(Q)]
searchbatch!(index, ctx, Q, knns)
for (q, res) in zip(Q, knns)
    for p in IdDistView(res)
        println(p.id, " ", p.dist)
    end
end

allknn(index::AbstractSearchIndex, ctx::AbstractContext, k::Integer; sort::Bool=true, progress=Progress(length(index); desc="allknn", dt=4)) -> (ids, dists)

Computes all the k nearest neighbors (all vs all) using the given index. Note that each object is its own nearest neighbor, so the user is responsible for removing these self references from the output if needed.

Arguments

• index: the index
• ctx: the index's context (caches, hyperparameters, logger, etc)
• k: the number of neighbors to retrieve for each object indexed by index

Keyword Arguments

• sort: ensures that each result set is presented in ascending order by distance. Ties are not ordered deterministically: the sort compares distances only (_lt_dist) and is a heapsort, so among neighbors at exactly equal distance the order comes from the heap's internal arrangement, which depends on the order the search happened to visit them – nondeterministic under a parallel search. Two runs over the same data can return the same neighbors in a different order. A caller that needs a reproducible artifact must impose its own tie-break (e.g. sort each column by (distance, id)); see the note at _lt_dist in pqueue/pqueue.jl
• progress: a ProgressMeter.Progress object used to report the progress of the computation, or nothing to disable it

Returns

A tuple (ids, dists) where both are (k, n) matrices. The i-th column corresponds to the i-th object in the dataset. Trailing zeros in ids (and Inf32 in dists) mean that the retrieval found fewer than the desired k neighbors for that object.

Examples

using SimilaritySearch

X = MatrixDatabase(rand(Float32, 8, 10^3))
G = SearchGraph(Dist.SqL2(), X)
ctx = SearchGraphContext()
index!(G, ctx)

ids, dists = allknn(G, ctx, 8)  # both are (8, 10^3) matrices

closestpair(idx::AbstractSearchIndex, ctx::AbstractContext; min_k::Int=8) -> (i, j, dist)

Finds the closest pair among all elements indexed by idx. If idx is an approximate index then the resulting pair may also be an approximation of the true closest pair.

Implemented as the case of bichromatic_closestpair where idx plays both roles – idxA and B (via database(idx)) – which is what lets it reuse idx's own internal structure (e.g. a SearchGraph node's adjacency) as a search hint and excludes self-matches, without paying for a second index.

Arguments

• idx: the search structure that indexes the set of points
• ctx: the search context (caches, hyperparameters, etc)

Keyword Arguments

• min_k: instead of looking for k=1 some approximate methods can take advantage of a larger k (also needed for stability: must be >= 2 here, since one slot is spent on the excluded self-match)

Returns

A tuple (i, j, dist) with the identifiers i and j of the closest pair found and their distance dist.

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 2, 10^3))
G = SearchGraph(dist, X)
ctx = SearchGraphContext()
index!(G, ctx)

i, j, d = closestpair(G, ctx)

bichromatic_closestpair(idxA::AbstractSearchIndex, ctx::AbstractContext, B::AbstractDatabase; min_k::Int=8, samedata::Bool=database(idxA) === B) -> (i, j, dist)

Finds the closest pair (a, b) with a an identifier of idxA and b an identifier of B, i.e., the closest pair between dataset A (already indexed as idxA) and dataset B (queried directly, with no index of its own). If idxA is an approximate index then the resulting pair may also be an approximation of the true closest pair.

If database(idxA) === B (i.e. idxA indexes B itself, as closestpair uses), self-matches (an element paired with itself) are excluded from the result; otherwise A and B are assumed to be disjoint datasets and every candidate pair is eligible. samedata defaults to this check but can be overridden explicitly.

This function always iterates over B's elements querying into idxA; it does not (yet) pick the smaller side to minimize the number of queries.

Always uses the @BATCHES-driven implementation (there is no separate sequential path) – on a single thread @BATCHES itself collapses to a single serial batch, so there is no parallelism overhead to avoid.

Arguments

• idxA: the search structure indexing dataset A
• ctx: the search context used by idxA (caches, hyperparameters, scheduler, etc.)
• B: the dataset queried against idxA, with no index of its own

Keyword Arguments

• min_k: instead of looking for k=1 some approximate methods can take advantage of a larger k (also needed for stability: must be >= 2 when samedata == true, since one slot is spent on the excluded self-match)
• samedata: whether idxA indexes B itself, i.e. whether self-matches must be excluded

Returns

A tuple (i, j, dist) with the identifier i of idxA, the identifier j of B, and their distance dist.

Examples

using SimilaritySearch

dist = Dist.L2()
A = MatrixDatabase(rand(Float32, 2, 10^3))
B = MatrixDatabase(rand(Float32, 2, 10^3))
GA = SearchGraph(dist, A)
ctx = SearchGraphContext()
index!(GA, ctx)

i, j, d = bichromatic_closestpair(GA, ctx, B)

bichromatic_closestpair(dist::PreMetric, A::AbstractDatabase, B::AbstractDatabase; min_k::Int=8, recall::Real=1.0) -> (i, j, dist)

Convenience wrapper for bichromatic_closestpair that builds and indexes A itself (B is queried directly, unindexed, as bichromatic_closestpair does), mirroring neardup's convenience-wrapper pattern: an ExhaustiveSearch (exact) when recall == 1.0 (the default), or otherwise a SearchGraph tuned to approach the given recall via OptimizeParameters(MinRecall(recall)).

Arguments

• dist: the distance function shared by A and B
• A, B: the two datasets (A gets indexed, B is queried directly)

Keyword Arguments

• min_k: see bichromatic_closestpair
• recall: target recall used to decide between an exact (recall=1.0) or approximate index

Examples

using SimilaritySearch

dist = Dist.L2()
A = MatrixDatabase(rand(Float32, 2, 10^3))
B = MatrixDatabase(rand(Float32, 2, 10^3))

i, j, d = bichromatic_closestpair(dist, A, B)

closestpairs(idx::AbstractSearchIndex, ctx::AbstractContext; k::Int=1, min_k::Int=max(k, 8)) -> Vector{Tuple{Int32,Int32,Float32}}

Finds the k closest pairs among all elements indexed by idx. If idx is an approximate index then the resulting pairs may also be an approximation of the true k closest pairs.

Implemented as the case of bichromatic_kclosestpairs where idx plays both roles – idxA and B (via database(idx)) – exactly as closestpair does for a single pair (k == 1).

Arguments

• idx: the search structure that indexes the set of points
• ctx: the search context (caches, hyperparameters, etc)

Keyword Arguments

• k: how many globally closest pairs to return
• min_k: see bichromatic_kclosestpairs; must be >= k for exactness (the default max(k, 8) guarantees this)

Returns

Up to k tuples (i, j, dist) with the identifiers of each closest pair and their distance, sorted ascending by distance. Fewer than k tuples are returned if idx has fewer than k eligible pairs.

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 2, 10^3))
G = SearchGraph(dist, X)
ctx = SearchGraphContext()
index!(G, ctx)

pairs = closestpairs(G, ctx; k=10)

bichromatic_kclosestpairs(idxA::AbstractSearchIndex, ctx::AbstractContext, B::AbstractDatabase; k::Int=1, min_k::Int=max(k, 8), samedata::Bool=database(idxA) === B) -> Vector{Tuple{Int32,Int32,Float32}}

Finds the k closest pairs (a, b) between dataset A (already indexed as idxA) and dataset B (queried directly, with no index of its own) – the same idea as bichromatic_closestpair (which is exactly the k == 1 case), generalized from "the single globally closest pair" to "the k globally closest pairs". If idxA is an approximate index then the resulting pairs may also be an approximation of the true k closest pairs.

Self-match exclusion works exactly as in bichromatic_closestpair: controlled by samedata, defaulting to database(idxA) === B.

Each b ∈ B is searched for its min_k nearest candidates in idxA (not just its single nearest, as bichromatic_closestpair does), since a single b may contribute more than one of the k globally closest pairs. min_k must be >= k for the result to be exact on an exact index (the default max(k, 8) guarantees this); a smaller min_k would silently cap how many pairs a single b can contribute. Every batch keeps its own bounded (<= k) ascending buffer of candidate pairs, which are merged into the final top k once every batch finishes – the same per-batch-then-merge structure bichromatic_closestpair uses for a single best pair.

Arguments

• idxA: the search structure indexing dataset A
• ctx: the search context used by idxA (caches, hyperparameters, scheduler, etc.)
• B: the dataset queried against idxA, with no index of its own

Keyword Arguments

• k: how many globally closest pairs to return
• min_k: candidate buffer size per query into idxA; must be >= k for exactness (see above)
• samedata: whether idxA indexes B itself, i.e. whether self-matches must be excluded

Returns

Up to k tuples (i, j, dist) (identifier i of idxA, identifier j of B, and their distance), sorted ascending by distance. Fewer than k tuples are returned if there aren't that many eligible pairs (e.g. a very small dataset with samedata == true).

Examples

using SimilaritySearch

dist = Dist.L2()
A = MatrixDatabase(rand(Float32, 2, 10^3))
B = MatrixDatabase(rand(Float32, 2, 10^3))
GA = SearchGraph(dist, A)
ctx = SearchGraphContext()
index!(GA, ctx)

pairs = bichromatic_kclosestpairs(GA, ctx, B; k=10)

bichromatic_kclosestpairs(dist::PreMetric, A::AbstractDatabase, B::AbstractDatabase; k::Int=1, min_k::Int=max(k, 8), recall::Real=1.0) -> Vector{Tuple{Int32,Int32,Float32}}

Convenience wrapper for bichromatic_kclosestpairs, analogous to bichromatic_closestpair's dataset wrapper above.

Arguments

• dist: the distance function shared by A and B
• A, B: the two datasets (A gets indexed, B is queried directly)

Keyword Arguments

• k, min_k: see bichromatic_kclosestpairs
• recall: target recall used to decide between an exact (recall=1.0) or approximate index

Examples

using SimilaritySearch

dist = Dist.L2()
A = MatrixDatabase(rand(Float32, 2, 10^3))
B = MatrixDatabase(rand(Float32, 2, 10^3))

pairs = bichromatic_kclosestpairs(dist, A, B; k=10)

bichromatic_metricjoin(idxA::AbstractSearchIndex, ctx::AbstractContext, B::AbstractDatabase;
                        k::Int, rank::Int=1, q::Float64=0.9, mingroup::Int=8,
                        samedata::Bool=database(idxA) === B) -> Vector{Tuple{Int32,Int32,Float32}}

Metric (similarity) join between dataset A (indexed as idxA) and dataset B, when neither the number of matches per b nor a join radius is known ahead of time. k is a deliberately overestimated guess passed to a single searchbatch call; the real work is deciding, per candidate pair (a, b), whether it is close enough to actually count as a match – i.e. picking a cutoff radius, and picking it per a rather than a single global one, since different regions of A can have very different local density.

The per-a radius is estimated from the reverse view of the very same searchbatch result: every b that ranked a among its own closest rank candidates "votes" for a with its distance, and a's own cutoff is the q-quantile of the distances of everyone who voted for it. This is usually a far more stable estimate than anything derivable from a single b's own (possibly tiny/noisy) neighbor list, since a well-connected a typically collects many more voters than rank. a's that collect fewer than mingroup voters (e.g. isolated points, or simply length(B) < mingroup) fall back to a single global cutoff instead: the q-quantile of the pooled distances of every a that did reach mingroup voters (free – no extra distance evaluations, and on the right distance scale, unlike e.g. a random-pair sample). If not even that pool has enough data (every group is under mingroup, a pathological corner case), it falls back once more to a small random cross-sample of A-B pairs. mingroup is clamped to at least 1 internally, since a genuinely empty group (zero voters, common whenever A is larger than B, or rank doesn't reach every a) has no quantile to speak of.

If database(idxA) === B (i.e. idxA indexes B itself), self-matches (a == b) are excluded both from voting and from the final result – controlled by samedata, defaulting to that check, exactly as in bichromatic_closestpair. This matters more here than it does there: with the default rank == 1, an unexcluded self-join would make every point's only rank-1 vote its own (trivial, zero-distance) self-match, leaving no real neighborhood information in any group and collapsing every threshold to the last-resort fallback.

Because the vote only uses rank (a small constant, << k) candidates per b, but the final filter is applied against every one of the k candidates searchbatch found, a single b can still end up matched to several a's – this is a join, not a top-k query, so the output size is data-dependent, not fixed.

Arguments

• idxA: the search structure indexing dataset A
• ctx: the search context used by idxA
• B: the dataset queried against idxA, with no index of its own

Keyword Arguments

• k: overestimated neighbor count for the initial searchbatch(idxA, ctx, B, k); there is no good data-independent default, so this must be supplied
• rank: how many of each b's top candidates vote for their respective a (<< k in practice, e.g. 1-3)
• q: quantile used both per-group and for the pooled global fallback
• mingroup: minimum number of voters an a needs before its own quantile is trusted over the (pooled, or last-resort sampled) global fallback; clamped to at least 1
• samedata: whether idxA indexes B itself, i.e. whether self-matches must be excluded

Returns

A Vector of (a, b, dist) triples (identifier a of idxA, identifier b of B, their distance) that survived the per-a cutoff – unsorted, and of a size determined by the data, not by k.

Examples

using SimilaritySearch

dist = Dist.L2()
A = MatrixDatabase(rand(Float32, 2, 10^3))
B = MatrixDatabase(rand(Float32, 2, 10^3))
GA = SearchGraph(dist, A)
ctx = SearchGraphContext()
index!(GA, ctx)

pairs = bichromatic_metricjoin(GA, ctx, B; k=16)

module Selection

Algorithms that pick a subset of a database to stand for the whole of it, and the two result types they share.

They come in two dual shapes, which is the thing to know before reading any of them:

• fix the count, let the radius fall out – fft, dnet, randsel, multirandsel are told how many centers to pick, and how well those centers cover the database is whatever it turns out to be. They return a CenterSelection.
• fix the radius, let the count fall out – neardup is told how close is too close, and the number of survivors is whatever it turns out to be. It returns a NearDupSelection.

Both results name the same things the same way (AbstractSelection), so code that reads one reads the other.

abstract type AbstractSelection end

What every algorithm in Selection returns. The two concrete types differ only in what each one additionally reports; these five fields mean the same thing in both, so code that reads one reads the other:

• centers::Vector{UInt32} – the selected objects, as identifiers into X, without repetitions.
• assign::Vector{UInt32} – one entry per object of X, in X order. assign[i] is the position in centers (a value in 1:length(centers)) of the center object i was assigned to, not its identifier in X. The identifier is one indexing away: centers[assign[i]].
• assigndist::Vector{Float32} – the distance from object i to the center assign[i] names. Zero for a center itself.
• costdists::Int / costblocks::Int – distance and block evaluations performed by the call.

Why assign holds positions and not identifiers

Because the identifier is recoverable from the position in one indexing operation, and the position is not recoverable from the identifier without building a dictionary. Every consumer of these results inside the library used to receive identifiers and immediately rebuild that dictionary, while the producers computed the position and threw it away.

Which center an object is assigned to

assigndist always agrees with assign – it is the distance to the center assign names. Whether that center is the nearest one depends on how the algorithm works, and the split is clean:

• Single-pass selectors know all their centers before assigning, so they assign to the nearest: fft, randsel, multirandsel.
• Incremental selectors assign an object when they meet it, to whichever center claimed it at that moment – and a center created later can turn out to be closer: dnet (around 40% of objects, measured on 120 random points in 4 dimensions) and neardup (8.8% on 400 points at ϵ=0.25). That assignment is the structure those algorithms compute; recomputing it as a nearest-center assignment would cost another full pass over the data for something the caller can do itself.

The practical consequence is that covering, being the largest assigndist, is the exact covering radius for the single-pass selectors and an upper bound on it for the incremental ones.

fft(dist::SemiMetric, X::AbstractDatabase, k::Integer; start::Int=0, verbose::Bool=true, reporters=InformativeLog(), scheduler::Symbol=get_batch_scheduler())

Selects k items that are far from each other based on the Farthest First Traversal (FFT) algorithm; this is useful to obtain a diverse, representative subset of X (e.g., as candidate centers for clustering). If start=0 then a random starting point is selected, otherwise a valid object id of X should be given.

Arguments

• dist: the distance function
• X: the input database
• k: the number of centers (far away items) to select

Keyword Arguments

• start: the identifier of the first center; 0 means a random starting point is selected
• verbose: whether the per-center progress message is produced at all
• reporters: where that message goes, see AbstractReporter. fft takes no context, so a caller that has one should pass reporters=ctx.reporters for its silencing to reach here; pass reporters=[] to silence it directly.
• scheduler: the @BATCHES scheduler used for the per-pivot distance update (:dynamic, :default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A CenterSelection, the same type every other selector in KCenters returns. k is clamped to length(X): asking for more centers than there are objects used to return the same object several times.

Both radii are exact and free here. The traversal picks each new center at the distance that separates it from everything selected so far, and that distance decreases monotonically, so the last one is the separation; what remains afterwards, the distance from the farthest object to its nearest center, is the covering.

Based on enet.jl from KCenters.jl

Note: fft is well-defined for metric distances

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 4, 10^3))
R = fft(dist, X, 16)
R.centers               # 16 well-separated identifiers into X
R.assign                # position in R.centers of each object's nearest center
R.centers[R.assign[7]]  # ... as an identifier into X
R.assigndist            # distance to that center
R.covering, R.separation
R.costdists             # distance evaluations performed by this call

dnet(dist::SemiMetric, X::AbstractDatabase, numcenters::Integer; verbose::Bool=true, reporters=InformativeLog(), scheduler::Symbol=get_batch_scheduler())

Selects one representative per density-based ball, returning the same CenterSelection every other selector here returns, so they are interchangeable.

Each round takes a random surviving object, gives it the k nearest objects still in the pool, and removes all of them. So a center is not chosen to be far from the previous ones – it is simply whatever survived outside the balls carved so far, which is enough to spread the centers out without any farthest-point search (separation reports how far, and it lands well above randsel's in practice).

numcenters is a target, not the count: the algorithm carves the database into balls of k = max(1, length(X) ÷ numcenters) objects each and keeps going until nothing is left, so it returns exactly cld(length(X), k) centers – numcenters itself when k divides evenly, and one more when it does not (asking for 8 over 300 objects returns 9). Use fft, randsel or multirandsel when the count has to be exact.

Arguments

• dist: distance function
• X: the objects to be computed
• numcenters: number of centers to be computed

Keyword Arguments

• verbose: whether the per-center progress message is produced at all
• reporters: where that message goes, see AbstractReporter. dnet takes no context, so a caller that has one should pass reporters=ctx.reporters for its silencing to reach here; pass reporters=[] to silence it directly.
• scheduler: the @BATCHES scheduler stored in the internal GenericContext used for this call (:dynamic, :default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A CenterSelection, with the assign caveat above. Unlike fft/multirandsel, dnet is not a greedy farthest-point traversal, so its separation is not free: it is measured afterwards, over the centers actually selected, and the k(k-1)/2 evaluations that takes are counted into costdists like any other.

randsel(dist::SemiMetric, X::AbstractDatabase, k::Integer; scheduler::Symbol=get_batch_scheduler())

Selects k centers randomly and computes, for every object of X, the same properties fft and dnet do – returning the same CenterSelection, so the four selectors are interchangeable.

Arguments

• dist: distance function
• X: the objects to be computed
• k: number of centers to be computed

Keyword Arguments

• scheduler: the @BATCHES scheduler stored in the internal GenericContext used for this call (:dynamic, :default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A CenterSelection. Its separation is measured over the selected centers afterwards, and those k(k-1)/2 evaluations are counted into costdists; a random selection has no separation guarantee, which is precisely what the number reports.

multirandsel(dist::SemiMetric, X::AbstractDatabase, k::Integer; m::Int=_default_m(length(X)), start::Int=0, scheduler::Symbol=get_batch_scheduler())

Selects k centers iteratively. Starts with a random point (or start if start > 0). In each step, it selects m random candidates from X and adds the one with the largest total distance to all currently selected centers (i.e. farthest from all of them at once). Once k centers are selected, it computes for the entire database the same properties fft and randsel do, returning the same CenterSelection.

Arguments

• dist: distance function
• X: the objects to be computed
• k: number of centers to be computed

Keyword Arguments

• m: number of candidates to evaluate per step (default is ceil(Int, log2(length(X))), and 1 for a database of two objects or fewer, where that formula gives 0 or -Inf); internally capped so at least k - 1 rounds are always possible
• start: index of the first center. If 0, a random center is chosen.
• scheduler: the @BATCHES scheduler used for the per-step candidate evaluation and stored in the internal GenericContext used for the final nearest-center pass (:dynamic, :default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A CenterSelection. Its separation costs nothing extra: each round already evaluates every candidate against every selected center, so the winner's distances to all of them are sitting in the matrix that chose it.

CenterSelection(centers, assign, assigndist, covering, separation, costdists, costblocks)

What the fixed-count selectors return: fft, dnet, randsel and multirandsel all produce this same type, so they are interchangeable at the call site. See AbstractSelection for the fields they share with neardup's result.

Fields beyond the shared ones

• covering::Float32 – the largest assigndist: the radius the selected centers need in order to reach every object of X. Smaller is a better cover.
• separation::Float32 – the smallest distance between two selected centers. Larger is a more spread-out selection. typemax(Float32) when fewer than two centers exist, since there is then no pair to measure.

costdists includes the k(k-1)/2 evaluations spent measuring separation.

covering and separation are different numbers

They used to share the name ε, meaning the covering radius in fft and the separation in multirandsel, while fft's docstring described its own as the separation. They are not interchangeable: on 300 random points in 4 dimensions with k=8, fft gives covering=0.715 and separation=0.908. Both are now always computed, by all four.

Examples

using SimilaritySearch

X = MatrixDatabase(rand(Float32, 4, 10^3))
R = fft(Dist.L2(), X, 16; verbose=false)

R.centers                       # 16 identifiers into X
R.centers[R.assign[7]]          # the identifier of the center object 7 belongs to
R.assigndist[7]                 # how far object 7 is from it
R.covering, R.separation        # how well the 16 cover X, and how spread out they are
count(==(3), R.assign)          # how many objects the third center took

neardup(idx::AbstractSearchIndex, ctx::AbstractContext, X::AbstractDatabase, ϵ::Real; k::Int=8, blocksize::Int=256, filterblocks=true)
neardup(dist::PreMetric, X::AbstractDatabase, ϵ::Real; recall=1.0, kwargs...)

Find near duplicates in database X using the empty index idx. The algorithm iteratively tries to index elements in X, and items that are nearer than ϵ to some already indexed element are not inserted again (they are considered duplicates of it).

The two-argument dist-based method is a convenience wrapper that builds and manages its own index internally: it uses an ExhaustiveSearch (exact) when recall == 1.0, or otherwise a SearchGraph (approximate) tuned to approach the given recall via OptimizeParameters(MinRecall(recall)).

Returns a NearDupSelection: the surviving objects as centers, which of them covers each object of X as assign, and the index built over them as idx.

This is the radius-driven half of Selection: you fix ϵ and the number of survivors is whatever the data gives. The fixed-count selectors (fft, dnet, randsel, multirandsel) are the dual – you fix the count and the radius falls out – and they report the same centers/assign/assigndist under the same names.

Arguments

• idx: An empty index (e.g., a SearchGraph or an ExhaustiveSearch) – only for the idx-based method

• ctx: the index's context (caches, hyperparameters, logger, etc) – only for the idx-based method

• dist: the distance function to use – only for the dist-based method

• X: The input dataset

• ϵ: the radius below which two objects count as duplicates of each other. It must not be negative – every distance would exceed it, so nothing would ever be collapsed – and a negative value is rejected rather than silently returning every object as its own center. ϵ = 0 is meaningful: it collapses exact duplicates only. To pick one from the data rather than by hand, sample the distance distribution first with distsample and take a low quantile of it:

  ϵ = quantile(distsample(dist, X; samplesize=2^10), 0.01)
  D = neardup(dist, X, ϵ)

Keyword Arguments

• k: The number of nearest neighbors to retrieve (some algorithms benefit from retrieving larger k values)
• blocksize: the number of items processed at a time
• filterblocks: if true then it filters neardups inside blocks (see blocksize parameter), otherwise, it supposes that blocks are free of neardups (e.g., randomized order).
• recall: (only for the dist-based method) target recall used to decide between an exact (recall=1.0) or approximate index

The ctx-based method reports through ctx: verbose(ctx) decides whether its progress messages are produced, ctx.reporters where they go. The dist-based wrapper takes verbose, reporters and observers directly, since it builds the context itself.

Notes

• The index idx must support incremental construction
• If you need to customize object insertions, you must wrap the index idx and implement your custom methods; it requires valid implementations of the following functions:
  • searchbatch(idx::AbstractSearchIndex, ctx, queries::AbstractDatabase, knns::Matrix, dists::Matrix)
  • distance(idx::AbstractSearchIndex)
  • length(idx::AbstractSearchIndex)
  • append_items!(idx::AbstractSearchIndex, ctx, items::AbstractDatabase)
• The $ϵ$-net itself is centers; database(idx) holds the same objects, in the same order

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 4, 10^3))
ϵ = 0.1

# using an explicit index
G = SearchGraph(dist, VectorDatabase(Vector{Float32}[]))
ctx = SearchGraphContext()
D = neardup(G, ctx, X, ϵ; blocksize=256)
D.centers                     # the ϵ-net: which objects of X survived
D.centers[D.assign[7]]        # which of them covers object 7
D.assigndist[7]               # how far object 7 sits from it (<= ϵ)
D.covering, D.epsilon         # the radius actually needed, and the one asked for
D.costdists, D.costblocks     # cost of this call

# convenience wrapper (builds its own exact index since recall=1.0)
D2 = neardup(dist, X, ϵ)

NearDupSelection(idx, centers, assign, assigndist, covering, epsilon, costdists, costblocks)

What neardup returns: the $ϵ$-net it found, i.e. the objects that survived as non-duplicates and, for every object of X, which survivor covers it. See AbstractSelection for the fields it shares with the fixed-count selectors.

Fields beyond the shared ones

• idx – the index holding the centers, ready to be reused: searching it answers with positions into centers, and it is what makes neardup usable as a deduplicating index builder rather than just a report.
• epsilon::Float32 – the radius that defined "too close", so the result is self-describing: all(assigndist .<= epsilon) holds without the caller keeping ϵ around.
• covering::Float32 – the largest assigndist, the radius actually needed. Always <= epsilon, and how far below says how much of the budget the data used: on 400 random points at ϵ=0.25 it came out at 0.2493.

There is no separation here, on purpose

Being an $ϵ$-net is a separation guarantee: an object only becomes a center when every existing center is farther than ϵ, so no two centers are closer than that. Reporting it would echo the input back (measured: 0.2501 for ϵ=0.25). It would also be the one expensive field in this type – unlike the fixed-count selectors, neardup does not know how many centers it will end up with, and that count can approach length(X).

Examples

using SimilaritySearch

X = MatrixDatabase(rand(Float32, 4, 10^3))
R = neardup(Dist.L2(), X, 0.1)

R.centers                    # the ϵ-net: identifiers into X that survived
R.centers[R.assign[7]]       # which survivor covers object 7
R.assigndist[7] <= R.epsilon # always true
R.covering                   # the radius the net actually needed, <= epsilon
length(R.centers)            # how many survived -- the output here, not the input

hsp_queries(dist, X::AbstractDatabase, Q::AbstractDatabase,
            knns_ids::AbstractMatrix{UInt32}, knns_dists::AbstractMatrix{Float32};
            scheduler::Symbol=get_batch_scheduler()) -> (ids, dists, hsp)

Computes the Half-Space Proximal (HSP) neighborhood of each query in Q by filtering its candidate neighbors (given by knns_ids/knns_dists, e.g., as produced by searchbatch) so that only proximal, non-redundant neighbors are kept.

Arguments

• dist: the distance function used to evaluate candidates
• X: the database the candidate identifiers in knns_ids point into
• Q: the set of queries (its i-th element corresponds to the i-th column)
• knns_ids: a (k, n) matrix of UInt32 identifiers (e.g., as produced by searchbatch)
• knns_dists: a (k, n) matrix of Float32 distances, parallel to knns_ids

Keyword Arguments

• scheduler: the @BATCHES scheduler used for the per-query HSP filtering (:dynamic, :default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A tuple (hsp_ids, hsp_dists, hsp) where:

• hsp_ids: a (k, n) matrix of UInt32 identifiers backing the hsp result objects
• hsp_dists: a (k, n) matrix of Float32 distances backing the hsp result objects
• hsp: a vector of KnnSorted objects, one per query, containing its HSP-filtered neighborhood

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 4, 10^3))
E = ExhaustiveSearch(dist, X)
ctx = GenericContext()

ids, dists = searchbatch(E, ctx, X, 32)
hsp_ids, hsp_dists, hsp = hsp_queries(dist, X, X, ids, dists)
length.(hsp)  # size of each query's HSP neighborhood

rerank!(dist::PreMetric, db::AbstractDatabase, q, ids, dists) -> (ids, dists)

Re-scores and re-sorts, in place, an existing candidate result set (ids, dists) for query q using dist as the exact (or otherwise more precise) distance function. This is typically used to refine a result set obtained with a cheaper proxy distance or a lossy/approximate index.

Arguments

• dist: the (typically exact) distance function used to re-score candidates
• db: the database that candidate identifiers in ids point into
• q: the query object
• ids: a vector of UInt32 candidate identifiers; entries equal to 0 mark the end of valid candidates
• dists: a parallel vector of Float32 distances to re-score

Returns

(ids, dists), sorted in ascending order by the recomputed distance (only over the valid, non-zero-id prefix).

rerank!(dist::PreMetric, db::AbstractDatabase, queries::AbstractDatabase,
        knns_ids::AbstractMatrix{UInt32}, knns_dists::AbstractMatrix{Float32}) -> (knns_ids, knns_dists)

Batch variant of rerank! that re-scores and re-sorts, in place and in parallel (one task per query column), the candidate result set of every query in queries.

Arguments

• dist: the (typically exact) distance function used to re-score candidates
• db: the database that candidate identifiers point into
• queries: the set of queries; its i-th element corresponds to the i-th column
• knns_ids: a (k, n) matrix of UInt32 candidate identifiers (e.g., as produced by searchbatch)
• knns_dists: a (k, n) matrix of Float32 distances, parallel to knns_ids

Returns

(knns_ids, knns_dists), with every column re-scored and sorted in ascending order by distance.

Examples

using SimilaritySearch

exact_dist = Dist.L2()
proxy_dist = Dist.SqL2()
X = MatrixDatabase(rand(Float32, 8, 10^3))
Q = MatrixDatabase(rand(Float32, 8, 32))

E = ExhaustiveSearch(; dist=proxy_dist, db=X)
ctx = GenericContext()
ids, dists = searchbatch(E, ctx, Q, 8)

rerank!(exact_dist, X, Q, ids, dists)  # refines in place using the exact distance

rerank!(dist::PreMetric, db::AbstractDatabase, q, res::AbstractKnnQueue) -> res

Re-scores and re-sorts, in place, an AbstractKnnQueue result object res for query q using dist.

distsample(dist::PreMetric, X::AbstractDatabase; samplesize=ceil(Int, sqrt(length(X)))) -> S

Computes a sample of the pairwise distance matrix by drawing samplesize random pairs (with repetition, possibly including an object paired with itself) from X and evaluating dist on each pair. Returns an array of size samplesize.

Arguments

• dist: distance function
• X: input database

Keyword Arguments

• samplesize: the size of the sample

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 4, 500))
S = distsample(dist, X)          # samplesize defaults to ceil(Int, sqrt(500))
S2 = distsample(dist, X; samplesize=1000)

distsample_ut(dist::SemiMetric, X::AbstractDatabase; prob::Float64=0.01, samplesize=0) -> S

Computes a sample of the upper triangular pairwise distance matrix. Returns an array of distances of close to $prob \cdot n^2/2$ entries for a database of size $n$. This method is fine to work with small datasets (not million-sized datasets); this method does not return duplicates nor symmetric duplicates.

Arguments

• dist: distance function
• X: input database

Keyword Arguments

• prob: sampling probability (on the upper triangle pairwise distance matrix)
• samplesize: if given (> 0), it ignores the given probability and computes the necessary prob to achieve a sample size close to samplesize

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 4, 500))
S = distsample_ut(dist, X; samplesize=1000)  # ~1000 sampled pairwise distances

recallscore(gold, res) -> Float64

Computes the recall score of a single result set res against its gold standard gold, i.e., the fraction of the identifiers in gold that also appear in res. Both gold and res can be a Set, an AbstractVector{IdDist}, an AbstractVector{<:Integer}, or an AbstractKnnQueue object.

Arguments

• gold: the gold standard (exact) result set
• res: the result set to be evaluated

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 8, 10^3))
E = ExhaustiveSearch(; dist, db=X)
ctx = getcontext(E)

gold = searchbatch(E, ctx, X, 8)
res = searchbatch(E, ctx, X, 8)  # here identical to gold, just for illustration
recallscore(view(gold, :, 1), view(res, :, 1))  # 1.0

macrorecall(goldI::AbstractMatrix, resI::AbstractMatrix, k::Integer=size(goldI, 1)) -> Float64

Computes the macro recall score, i.e., the average of the per-query recallscore, using goldI as the gold standard and resI as the predictions to be evaluated; both are expected to be matrices of identifiers (e.g., IdDist or integers) with one column per query. If k is given, then each column is cut to its first k entries before scoring.

Arguments

• goldI: a (k, n) matrix with the gold standard (exact) result of n queries
• resI: a (k, n) matrix with the result to be evaluated of the same n queries
• k: the number of neighbors (per column) to consider; defaults to size(goldI, 1)

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 8, 10^3))
E = ExhaustiveSearch(dist, X)
ctx = getcontext(E)

gold = searchbatch(E, ctx, X, 8)
G = SearchGraph(dist, X)
gctx = getcontext(G)
index!(G, gctx)
res = allknn(G, gctx, 8)

macrorecall(gold, res)  # macro recall of the approximate index against the exact gold standard

macrorecall(goldlist::AbstractVector, reslist::AbstractVector) -> Float64

Computes the macro recall score, i.e., the average of the per-query recallscore, using vectors of per-query result sets (each element can be a Set, an AbstractKnnQueue object, or a vector of identifiers) instead of matrices.

Arguments

• goldlist: a vector with one gold-standard result set per query
• reslist: a vector with one result set (to be evaluated) per query, length(reslist) == length(goldlist)

Examples

using SimilaritySearch

dist = Dist.L2()
X = MatrixDatabase(rand(Float32, 8, 200))
E = ExhaustiveSearch(; dist, db=X)
ctx = getcontext(E)

knns = searchbatch(E, ctx, X, 8)
goldlist = [Set(collect(IdView(view(knns, :, i)))) for i in 1:length(X)]
reslist = goldlist  # here identical to gold, just for illustration
macrorecall(goldlist, reslist)  # 1.0

matcherror(golddist::AbstractVector{Float32}, res::AbstractKnnQueue, p::Real, η::Real, minspread::Real=1f-2)::Float64

Per-query MatchError (see MaxMatchError): compares the distances actually returned in res against the exact gold distances golddist (both compared in ascending rank order), penalizing missing positions with η. minspread is the absolute floor added to the gold neighborhood's spread before normalizing by it, guarding against a degenerate (all-tied) gold neighborhood – see MaxMatchError. It is the per-query score behind MaxMatchError; macromatcherror is its mean over the queries.

matcherror(golddist::AbstractVector{Float32}, res::BallKnn, p::Real, η::Real, minspread::Real=1f-2)::Float64

MatchError of a radius-bounded search: scores only the items res holds within its radius, never its navigation reserve (see BallKnn), against the true ball's distances. Each ball member the search did not reach costs η, which is what makes this the radius counterpart of recall – and why MaxMatchError is the only ErrorFunction that transfers to radius queries: MinRecall goes through macrorecall, which divides by the gold set's size, and a small radius routinely produces queries whose true ball is empty.

matcherror(golddist, res, err::MaxMatchError) -> Float64
macromatcherror(golddists, reslist, err::MaxMatchError) -> Float64

The per-query and the macro matcherror with the parameters p, η and minspread taken from err, so a score can be computed outside the optimizer exactly as optimize_index! computes it: bootstrapscore((g, r) -> matcherror(g, r, err), golddists, reslist).

macromatcherror(golddists, reslist, p::Real=1, η::Real=1, minspread::Real=1f-2) -> Float64

The mean of the per-query matcherror over the queries: the macro MatchError, the distance-based counterpart of macrorecall, and what MaxMatchError scores a configuration by (macromatcherror(golddists, reslist, err::MaxMatchError) takes the parameters from err). golddists holds each query's exact gold distances in ascending order, as a vector with one vector per query or as a (k, n) matrix (the second output of searchbatch over an exact index), and reslist the result queues to score, one per query. 0 is a perfect match; it is unbounded above.

Examples

using SimilaritySearch

X = MatrixDatabase(rand(Float32, 8, 10^3))
Q = MatrixDatabase(rand(Float32, 8, 100))
E = ExhaustiveSearch(Dist.SqL2(), X)
goldI, goldD = searchbatch(E, GenericContext(), Q, 10)
G = SearchGraph(Dist.SqL2(), X); ctx = SearchGraphContext(); index!(G, ctx)
knns = [search(G, ctx, Q[i], knnqueue(KnnSorted, 10)) for i in 1:length(Q)]
macromatcherror(goldD, knns)          # p = 1, η = 1: the MaxMatchError() defaults

perqueryscores(score, gold, res; k=nothing) -> Vector{Float64}

score(gold_i, res_i) for every query i: the vector a macro score is the mean of, and what bootstrapscore resamples. gold and res are each either a matrix with one column per query, cut to its first k rows when k is given (as macrorecall does), or a vector with one entry per query; score is any two-argument function – recallscore, (g, r) -> matcherror(g, r, p, η), or a user's.

perqueryscores(recallscore, goldI, resI)                       # what macrorecall averages
perqueryscores((g, r) -> matcherror(g, r, 1, 1), goldD, knns)   # what macromatcherror averages

bootstrapscore(perquery::AbstractVector{<:Real}; nboot=1000, level=0.95, rng=Random.default_rng()) -> BootstrapScore
bootstrapscore(score, gold, res; k=nothing, nboot=1000, level=0.95, rng=Random.default_rng()) -> BootstrapScore

The distribution of a macro score under resampling of the queries. A macro score (macrorecall, macromatcherror) is the mean of a per-query score, and a single number says nothing about how much it would move with another sample of queries; this draws length(perquery) queries with replacement nboot times, takes the mean of each draw, and returns the mean, the standard deviation, and the percentile interval at level of those means (see BootstrapScore). The per-query scores are computed once, by perqueryscores in the second form, and only that vector is resampled, so nboot costs nothing next to the searches that produced res; rng makes the draws reproducible.

Two results on the same queries are compared paired: bootstrap the per-query differences, so each draw takes the same queries from both, and read whether the interval excludes zero:

a = perqueryscores(recallscore, goldI, resA)
b = perqueryscores(recallscore, goldI, resB)
d = bootstrapscore(a .- b; nboot=10_000)      # d.lo > 0: A is better on these queries at that level

Examples

using SimilaritySearch

X = MatrixDatabase(rand(Float32, 8, 10^3))
Q = MatrixDatabase(rand(Float32, 8, 100))
E = ExhaustiveSearch(Dist.SqL2(), X)
goldI, goldD = searchbatch(E, GenericContext(), Q, 10)
G = SearchGraph(Dist.SqL2(), X); ctx = SearchGraphContext(); index!(G, ctx)
resI, _ = searchbatch(G, ctx, Q, 10)
bootstrapscore(recallscore, goldI, resI)                       # BootstrapScore(0.97 ± 0.0056, 95% [0.959, 0.981], 100 queries, 1000 resamples)
knns = [search(G, ctx, Q[i], knnqueue(KnnSorted, 10)) for i in 1:length(Q)]
bootstrapscore((g, r) -> matcherror(g, r, MaxMatchError()), goldD, knns)

BootstrapScore

What bootstrapscore returns: mean, the macro score itself (the mean of perquery); std, the standard deviation of the resampled macro scores; lo and hi, the percentile confidence interval at level; samples, one macro score per resample; and perquery, the per-query scores they were drawn from.

@BATCHES minbatch [scheduler=:dynamic|:default|:static|:greedy] for i in range ... end
@BATCHES minbatch [scheduler=...] begin
    @BEGIN ... end            # optional, runs once, before dispatch
    @BEGINBATCH ... end       # optional, runs once per batch, before its elements
    @LOOP for i in range ... end   # mandatory
    @ENDBATCH ... end         # optional, runs once per batch, after its elements
    @END ... end              # optional, runs once, after all batches join
end

Splits range into consecutive chunks ("batches") of (approximately) minbatch elements each and processes each batch as one task, using Threads.@threads under the selected scheduler. No Polyester dependency is involved (unlike this package's earlier @batch-based macros).

The simple, one-argument form above (no @BEGIN/@BEGINBATCH/@ENDBATCH/@END) is exactly equivalent to using only @LOOP; it exists so straightforward per-element loops don't need any of the section machinery.

Sections

• @BEGIN: runs once, in the caller's own scope, before any batch starts. Variables declared here are plain local variables of the enclosing function – visible later in @END, and (via ordinary closure capture) inside every batch's @BEGINBATCH/@LOOP/ @ENDBATCH too. @nbatches() is available here (typically to size a shared, per-batch array, e.g. results = Vector{Float32}(undef, @nbatches())).
• @BEGINBATCH: runs once per batch, at the start of that batch's task, before its @LOOP iterations. @batchid()/@nbatches() and @BEGIN's variables are available.
• @LOOP for i in range ... end: mandatory. The per-element body, run once for every i in this batch's chunk of range. Shares one lexical/closure scope with @BEGINBATCH/@ENDBATCH (of the same batch), so a variable declared in @BEGINBATCH can be read and updated here directly.
• @ENDBATCH: runs once per batch, after that batch's @LOOP iterations finish (same task, before it joins). Sees @BEGIN's variables plus whatever @BEGINBATCH/ @LOOP left in the per-batch scope. Writing into results[@batchid()] here is race-free by construction (batch ids are disjoint, unlike Threads.threadid() which can alias/migrate under non-:static schedulers – see set_batch_scheduler!).
• @END: runs once, in the caller's own scope, after all batches have joined. Sees @BEGIN's variables (e.g. to reduce the now fully-populated results array).

Sections that are omitted generate no code at all. When present, sections must appear in the order @BEGIN, @BEGINBATCH, @LOOP, @ENDBATCH, @END (each except @LOOP may be individually omitted).

Arguments

• minbatch: (approximate) number of iterations processed per batch; the first positional argument. Use getminbatch to compute a reasonable value (aims for ~8 batches per thread) instead of hand-picking one.
• scheduler: overrides the global get_batch_scheduler/ set_batch_scheduler! selection for this call site only. One of :dynamic, :default, :static, :greedy, or :sequential – scheduler=:sequential forces this call site to run its whole range as a single, unthreaded batch (@nbatches() is 1, @batchid() is 1), regardless of Threads.nthreads() or how range compares to minbatch; see set_batch_scheduler!. May be given either as a literal (scheduler=:static, validated immediately, at macro-expansion time) or as an arbitrary runtime expression – e.g. scheduler=ctx.scheduler for a context-typed caller that stores its own scheduler choice (see GenericContext/SearchGraphContext) – which is evaluated and validated once, right before this call's batches start.

# BUGGY: every batch's find_neighborhood! call resolves getvstate/getbeam via the
# SAME outer `ctx` (batchid always 1) -- a live race across concurrently-running
# batches, on every scheduler, despite `tmp`/`N` themselves being correctly
# @batchid()-sliced right above it.
@BEGINBATCH
    bctx = beginbatch(ctx, @batchid())
    tmp = knnqueue(bctx, view(qcache, 1:ksearch, 2 * @batchid() - 1))
    N = knnqueue(bctx, view(qcache, 1:ksearch, 2 * @batchid()))
@LOOP for objID in 1:n
    find_neighborhood!(N, g, ctx, database(g, objID), tmp, 1:-1; hints=...)  # bug: ctx, not bctx
end

# FIXED
@LOOP for objID in 1:n
    find_neighborhood!(N, g, bctx, database(g, objID), tmp, 1:-1; hints=...)
end

Examples

julia> using SimilaritySearch

julia> n = 100_000; out = zeros(Int, n);

julia> @BATCHES getminbatch(n) for i in 1:n
           out[i] = i^2
       end

julia> out == [i^2 for i in 1:n]
true

julia> function sumsq(n, minbatch)
           local total
           @BATCHES minbatch begin
               @BEGIN
                   partial = zeros(Float64, @nbatches())
               @BEGINBATCH
                   acc = 0.0
               @LOOP for i in 1:n
                   acc += abs2(i)
               end
               @ENDBATCH
                   partial[@batchid()] = acc
               @END
                   total = sum(partial)
           end
           total
       end;

julia> sumsq(1000, getminbatch(1000)) == sum(abs2, 1:1000)
true

@BEGIN

Marks the start of the @BATCHES section that runs once, in the caller's own scope, before any batch starts. See @BATCHES.

@BEGINBATCH

Marks the start of the @BATCHES section that runs once per batch, at the start of that batch's task, before its @LOOP iterations. See @BATCHES.

@LOOP for i in range ... end

Marks the mandatory @BATCHES section: the per-element body, run once for every element of the batch's chunk. Must be immediately followed by exactly one for i in range ... end loop. See @BATCHES.

@ENDBATCH

Marks the start of the @BATCHES section that runs once per batch, after that batch's @LOOP iterations finish (same task, before it joins). See @BATCHES.

@END

Marks the start of the @BATCHES section that runs once, in the caller's own scope, after all batches have joined. See @BATCHES.

@batchid()

Inside a @BATCHES call's @BEGINBATCH, @LOOP, or @ENDBATCH section, expands to the current batch's fixed, 1-based ordinal index (stable for the whole lifetime of that batch's task). Since batch ids are disjoint – no two concurrently-running batches ever share one – indexing a shared, @nbatches()-sized array by @batchid() is race-free by construction, regardless of scheduler (:dynamic/:static/:greedy); this is safer than indexing by Threads.threadid(), which can alias/migrate under non-:static schedulers. Not meaningful in @BEGIN/@END (those run once, globally, not per batch) – using it there raises UndefVarError.

@nbatches()

Inside a @BATCHES call (any section: @BEGIN, @BEGINBATCH, @LOOP, @ENDBATCH, @END), expands to the total number of batches/chunks used for that call (always >= 1; 1 when the fast/serial path was taken). Typically used in @BEGIN to size a shared, @batchid()-indexed array. Raises UndefVarError if used outside of @BATCHES.

set_batch_scheduler!(sched::Symbol)

Sets the global Threads.@threads schedule kind used by @BATCHES whenever a call site does not give its own scheduler= override. Must be one of:

• :dynamic (the default): Threads.@threads :dynamic, i.e. migratable tasks placed by Julia's dynamic scheduler. Unlike :static it puts no restriction whatsoever on where a @BATCHES call may run: any number of them may be live at once in one process, nested or concurrent, which is what any library serving several indexes from one process needs. This package no longer has any Threads.threadid()-indexed shared state on its own parallel paths: searchgraph/context.jl's vstates/beams, searchgraph/rebuild.jl, searchgraph/insertions.jl, closestpair.jl, and exact/parallel-exhaustive.jl all use @batchid()-indexing (safe under every scheduler); dist/seqs.jl's Levenshtein/LCS, which can't reach a @batchid() at all (their scratch buffer is needed inside the generic, context-free evaluate(dist, a, b)), use a Channel-based buffer pool instead of thread-indexing.
• :default: whatever Threads.@threads picks when given no schedule annotation at all (currently :dynamic, but that is a default Julia explicitly reserves the right to change). Use it only when following Julia's future choice is what you actually want; to ask for the dynamic schedule itself, say :dynamic.
• :static: one task per thread, fixed placement, never migrates mid-execution. Worth choosing deliberately in two situations: (a) in controlled experiments and benchmarks, where its fixed, precomputed chunking is the cheapest and most reproducible schedule available – no migration, no work-stealing, no per-batch scheduling decisions – so timings vary less between runs; and (b) as the only schedule under which Threads.threadid() is a valid index into per-thread data structures, which is occasionally the only option for code that cannot reach a @batchid() (be aware that a nested @BATCHES region would still break that assumption). Trade-off, and the reason it is no longer the default: Julia refuses to enter a @threads :static region while another one is already running anywhere in the process, and the flag it tests is global – two unrelated indexes, in unrelated calls, each under its own lock, still collide – so it throws if a @BATCHES call is nested inside another already-threaded region, runs concurrently with one, or is invoked from a non-main thread.
• :greedy: spawns up to Threads.threadpoolsize() tasks that each greedily pull the next batch of work as they finish; best for very uneven per-batch cost. Requires Julia >= 1.11 (raises ArgumentError on older versions, at the point this is set, not merely when a @BATCHES call later tries to use it).
• :sequential: disables threading entirely. Every @BATCHES call site that does not give its own scheduler= override runs its whole range as a single batch, in the caller's own task – exactly the existing small-n/single-thread fast path, just forced regardless of Threads.nthreads() or how range compares to minbatch. @nbatches() is 1 and @batchid() is 1 for the entire call.

See also get_batch_scheduler.

get_batch_scheduler() -> Symbol

Returns the current global scheduler used by @BATCHES when a call site does not specify its own scheduler= override. One of :dynamic, :default, :static, :greedy, :sequential. See set_batch_scheduler! for what each means and how to change it.

push_item!(res::KnnHeap, p::IdDist)

Appends an item into the result set

push_item!(res::KnnHeap, i::Integer, d::Real)

Convenience overload of push_item! that builds the IdDist item from an id/dist pair given as separate arguments.

push_item!(res::KnnHeap, p::Pair)

Convenience overload of push_item! that builds the IdDist item from a id => dist pair.

push_item!(res::KnnSorted, p::IdDist)

Appends an item into the result set

push_item!(res::KnnSorted, i::Integer, d::Real)

Convenience overload of push_item! that builds the IdDist item from an id/dist pair given as separate arguments.

push_item!(res::KnnSorted, p::Pair)

Convenience overload of push_item! that builds the IdDist item from a id => dist pair.

push_item!(res::RadiusSorted, p::IdDist)

Accepts p into res iff p.dist <= res.radius, keeping res sorted by distance. Returns whether the item was accepted.

push_item!(res::RadiusHeap, p::IdDist)

Accepts p into res iff p.dist <= res.radius, appending it without maintaining any order (marks res as unsorted). Returns whether the item was accepted.

push_item!(res::BallKnn, item::IdDist)

Accepts item if it falls within the ball, or if it improves the navigation reserve; returns whether it was accepted.

push_item!(db::MatrixDatabase, v)

Not supported; MatrixDatabase is a fixed-size wrapper over a matrix. Use BlockMatrixDatabase or VectorDatabase instead if you need to grow the database.

push_item!(db::BlockMatrixDatabase, v::AbstractVector)

Appends v as a new object at the end of db, allocating a new internal block when the current one is full.

push_item!(db::MMapMatrixDatabase, v::AbstractVector)

Appends v as a new object at the end of db, growing (extending and remapping) the underlying file when the current capacity is exceeded. length(db) reflects v immediately, but nothing is made durable by this call – see the type docstring's "Durability" section, and call flush when that matters to you.

push_item!(db::VectorDatabase, v)

Appends v as a new object at the end of db.

push_item!(S::SubDatabase, v)

Not supported; SubDatabase is a read-only view over a parent database and cannot be mutated directly.

push_item!(
    index::SearchGraph,
    ctx::SearchGraphContext,
    item,
    neighbors_,
    tmp,
    push_db::Bool
)

Appends a single object into the index, computing its neighborhood, connecting reverse links, and running the registered callbacks. Low-level function used by the sequential and parallel insertion loops (append_items!/index!).

Arguments:

• index: The search graph index where the insertion is going to happen.
• ctx: The context environment of the graph, see SearchGraphContext.
• item: The object to be inserted, it should be in the same space than other objects in the index and understood by the distance metric.
• neighbors_: knnqueue used to store the computed neighborhood of item, later attached to the graph.
• tmp: knnqueue used as scratch space by the neighborhood computation.
• push_db: if false, item is not appended to index.db (used when item is already present in the database but not yet indexed).

push_item!(g::AsymmetricSearchGraph, ctx::SearchGraphContext, item)

Appends one raw item: stored as encode(distance(g), item), indexed with its raw form.

push_item!(db::QuantDatabase, v::AbstractVector)
push_item!(db::QuantDatabase, v::SQVec)

Appends v to db: a plain vector is quantized with quantize(db, v) first, an already quantized one is stored as it is (its parameters must be db's in the global family). The codes go to db.Q, which must support growth (BlockMatrixDatabase, MMapMatrixDatabase, VectorDatabase, ...); a MatrixDatabase throws, as it does for plain vectors.

push_item!(idx::AbstractInvertedFile, ctx::InvertedFileContext, obj)

Inserts a single element into the index. This operation is not thread-safe.

Arguments

• idx: The inverted index
• ctx: the index's context
• obj: The object to be indexed

append_items!(a::MatrixDatabase, b)

Not supported; MatrixDatabase is a fixed-size wrapper over a matrix. Use BlockMatrixDatabase or VectorDatabase instead if you need to grow the database.

append_items!(db::BlockMatrixDatabase, B)

Appends every object in B (e.g., an iterator of vectors, such as eachcol of a matrix) to the end of db.

append_items!(db::MMapMatrixDatabase, B)

Appends every object in B (e.g., an iterator of vectors, such as eachcol of a matrix) to the end of db, growing the underlying file as needed. length(db) reflects every item of B immediately, but as with push_item!, nothing is made durable by this call – call flush when that matters to you.

append_items!(db::VectorDatabase, B)

Appends every object in B to the end of db.

append_items!(
    index::SearchGraph,
    ctx::SearchGraphContext,
    db
)

Appends all items in db to the index. It can be made in parallel or sequentially.

Arguments:

• index: the search graph index
• db: the collection of objects to insert, an AbstractDatabase is the canonical input, but supports any iterable objects
• ctx: The context environment of the graph, see SearchGraphContext.

Examples

G = SearchGraph(dist, VectorDatabase())
ctx = SearchGraphContext()
append_items!(G, ctx, MatrixDatabase(rand(Float32, 8, 1000)))

append_items!(g::AsymmetricSearchGraph, ctx::SearchGraphContext, items::AbstractDatabase)

Appends the raw items: each is stored as encode(distance(g), item), and then indexed with its raw form as the query that picks its neighbors (see InsertionSource). Parallel or sequential as ctx says, like a SearchGraph's.

append_items!(db::QuantDatabase, items)

Appends every object of items (an AbstractDatabase, an iterator of vectors, or a matrix whose columns are the vectors) to db, through push_item!.

append_items!(idx, ctx, items)

Appends all items elements into the index idx. It work in parallel using all available threads. Grows database(idx) then delegates the actual indexing work to index!, which is the sole emitter of the :add! log event for this batch – this function itself does not log, per the exactly-once contract documented on OBSERVE.

Arguments:

• idx: The inverted index
• items: The database of sparse objects, it can be only indices if each object is a list of integers or a set of integers, SparseVectors, among other combinations (see identiterator for the exact set of natively supported object types; dense vectors are not accepted directly — convert with SparseArrays.sparse first).
• n: The number of items to insert (defaults to all)

index!(idx::SearchGraph, ctx::SearchGraphContext, ::Val{:knr},
       knr_ids::Matrix{UInt32}, knr_dists::Matrix{Float32};
    n_neighbors::Integer=2,
    hints_size::Int=100,
    start_factor::Float64=0.97,
)

Fast non-incremental construction of a SearchGraph index using hierarchical combination clusters of nearest references. Groups start at length k, and each subsequent level L table is generated by taking all combinations of size L from the length L+1 keys. Duplicate sub-clusters are deduplicated using Set before linking.

index!(idx::SearchGraph, ctx::SearchGraphContext, kind::Val{:knr};
    numrefs::Integer=ceil(Int, sqrt(length(database(idx)))),
    k::Integer=4,
    sample_method::Symbol=:fft,
    n_neighbors::Integer=2,
    hints_size::Int=100,
    start_factor::Float64=0.97
)

Computes the knr projection matrix using numrefs references and calls index!(idx, ctx, Val(:knr), knr). Progress is reported through ctx: verbose(ctx) decides whether the messages are produced, ctx.reporters where they go.

index!(idx::SearchGraph, ctx::SearchGraphContext, kind::Val{:bitsketch};
    method::Symbol=:gaussian,
    nbits::Int=256,
    kind::ErrorFunction=MaxMatchError(; maxerror=0.01f0),
    logbase::Float32=1.3f0,
    parallel_block::Int=2^13
)

Fast non-incremental construction of a SearchGraph via a cheap proxy space: database(idx) is sketched into an nbits-bit sign sketch (method, see SimilaritySearch.Projections.bitsketch), a topology is built over that sketch under Dist.Bits.Hamming using the normal incremental index! (tuned towards kind), and that topology (adjacency + hints – not the sketch-space-tuned BeamSearch, see below) is copied into idx, which keeps its own real distance(idx)/database(idx) for serving.

This grew out of a long investigation (issue #52) into :knr's hierarchical-clustering construction, which turned out to (a) scale badly on real, high-dimensional embeddings (its own construction cost, not just the resulting recall) and (b) need a rebuild pass afterward to fix its hub-heavy degree distribution – one whose own quality turned out to depend entirely on algo[]'s carried-over maxvisits (issue #59, now fixed) and whose net effect on recall was inconsistent and hard to predict. Sketching into a proper bit-sketch (not just a handful of reference ids, :knr's approach) and building the topology via the already-well-tested incremental index! sidesteps both problems: no combinatorial clustering algorithm to scale badly, and – per repeated measurement against a real ~600k-row embedding slice, confirmed at n=100_000 and n=200_000 with a fixed seed – no rebuild pass needed to reach a competitive recall/QpS trade-off against an equal-effort incremental build.

idx.algo[] is deliberately left untouched (never overwritten with the sketch-space-tuned BeamSearch): its bsize/Δ/maxvisits were tuned for Hamming distance's very different scale, and carrying that over would silently miscalibrate every later search/optimize call against idx's real distance (the exact bug fixed in issue #59, there for rebuild). Call optimize_index! once idx is populated, same as after any other construction method.

If, after tuning, the resulting recall/QpS trade-off isn't good enough, a further rebuild pass against the real distance(idx)/database(idx) is worth trying – it is not required or applied automatically here, since in repeated measurement it did not reliably improve on the plain sketch-built topology (see issue #52).

Keyword Arguments

• method: the bit-sketch generator: :gaussian (default), :qr, :adh (AnchoredDistantHyperplanes, built with its own defaults – construct one directly first if it needs tuning), or :external (use a sketch computed outside this package – e.g. another binarization method entirely – passed via sketch) – see SimilaritySearch.Projections.bitsketch; see the vector-space warning above.
• sketch: only used when method=:external. A precomputed (nbits÷64, n) UInt64 matrix (one nbits-bit sketch per column, n == length(database(idx))), used as-is instead of computing B internally – lets any external binarization method (not just :gaussian/:qr/:adh) bootstrap the topology the same way.
• nbits: how many hyperplanes the sketch model is built with, must be a multiple of 64 (default 256). More hyperplanes cost more memory/compute per comparison but tend to improve recall; see issue #52 for measurements across 64-1536 bits on real embeddings. At width=1 this is also the sketch's size in bits, which is why the name says "bits".
• width: bits spent per hyperplane – 1 (default: one sign bit, compared with Hamming, the historical behavior) or 2/4/8 (a QuantSketch code, compared with the matching SQgu*.SqL2). The model is not resized by this: the same nbits hyperplanes are fitted either way, and the sketch simply occupies nbits * width bits instead of nbits. So width buys precision with memory at no additional model-fitting cost – a sign bit only records which side of a hyperplane an object falls on, while a wider code also records how far, which is information the model already computed and was throwing away. method=:external supports only width=1.
• kind: the ErrorFunction OptimizeParameters/optimize_index! tunes the sketch-space construction towards (default MaxMatchError(; maxerror=0.01f0), calibrated to roughly match MinRecall(0.9)'s achieved quality on real embeddings while building noticeably faster and far more consistently run-to-run – see issue #52's measurements). Pass MinRecall(...) to use the more familiar identifier-set-based criterion instead.
• logbase: log base for the sketch-space Neighborhood's size growth, see Neighborhood.
• parallel_block: forwarded as the sketch-space construction's own parallel_block (size of the batch processed in parallel at a time), see SearchGraphContext.

index!(index::SearchGraph, ctx::SearchGraphContext)

Indexes the already initialized database (e.g., given in the constructor method). It can be made in parallel or sequentially. The arguments are the same than append_items! function but using the internal index.db as input.

Arguments:

• index: The graph index
• ctx: The context environment of the graph, see SearchGraphContext.

index!(sat::Sat, ctx::AbstractContext, ipart::SatInitialPartition=SatInitialPartition(); <kwargs...>)
index!(sat::Sat, ctx::AbstractContext, ipart::RandomInitialPartition; <kwargs...>)

Performs the indexing of the referenced dataset in the tree. It supports limited forms of multithreading, induced by initial partitioning schemes.

Arguments

• sat: The metric data structure.
• ctx: context object (caches and hyperparameters).
• ipart: initial partitioning scheme for the tree. It supports the following kinds of objects:
  • SatInitialPartition(): Traditional construction, default value. Each part is a SAT partition and will be processed in parallel via @BATCHES.
  • RandomInitialPartition(nparts=Threads.nthreads(), shuffle=false): construction that divides the dataset (randomly if shuffle=true) in nparts disjoint parts. The resulting structure violates the SAT partitioning in a whole and creates a kind of SAT forest that are fine SAT partitions. Useful to limit the height of the tree and for multiprocessing purposes, i.e., each part will be processed in parallel.

Keyword arguments

• sortsat: The strategy to create the spatial access tree, it heavily depends on the order of elements while it is build. It accepts:
  • RandomSortSat(): children are randomized (default value)
  • ProximalSortSat(): classical approach, near elements are put first.
  • DistalSortSat(): recent approach, distant elements are put first.
• minleaf: Minimum number of children to perform a spatial access separation (half space partitioning)

index!(bkt::BKT, ctx::AbstractContext; npivots=2, nsample=32, minleaf=12)

Builds the tree over the whole database(bkt), top-down: at each node it picks a pivot, partitions the remaining objects by their exact integer distance to it, and recurses into each resulting bucket. Returns bkt. The tree must be empty (BKT is build-once, it has no incremental insertion).

Keyword Arguments

• npivots: how many pivot candidates are considered per node; the one producing the most distinct distance values wins, i.e. the one splitting its objects into the most buckets. 1 disables the choice altogether. On a 30k-word dictionary going from 1 to 2 improved every query shape measured (k-NN and range alike) by 10-20%, while 3 and 5 bought nothing beyond it and were often worse: the criterion also rewards outlier pivots, which see many distinct distances precisely because they sit far from everything, and the more candidates are drawn the likelier one is picked.
• nsample: how many of a node's own objects each candidate is judged against. Selection is a heuristic, so it is judged on a sample rather than on everything the node covers – that keeps its cost npivots * nsample per node instead of npivots times the node's size, which would make npivots a straight multiplier on the whole build. Every candidate of a node faces the same sample, so they compete on equal terms.
• minleaf: objects per long leaf. A group this size or smaller becomes a leaf holding a plain list, scanned exhaustively, instead of a sub-tree. This trades query cost for build cost and size, and it is a real trade in both directions: on that same dictionary, going from 4 to 32 shrank the tree ~7x (4622 to 613 internal nodes) and the build ~20%, and cost ~40% more distance evaluations per query. Pass 1 to build the tree all the way down.

Nodes of the same level are expanded in parallel (@BATCHES, scheduler=ctx.scheduler): they own disjoint ranges of the working permutation, so they never contend. Only the reservation of their slots in the shared child/bucket arrays is serial, and that is a prefix sum over the level's nodes – O(#nodes), against the O(npivots * n) distance evaluations each level spends. Pivot candidates are drawn from the task-local RNG, so Random.seed! still controls the build, but the tree it produces depends on the thread count.

index!(idx::AbstractInvertedFile, ctx::InvertedFileContext)

Builds postings for every object already present in database(idx) but not yet indexed, i.e. the block database(idx)[length(idx)+1 : length(database(idx))]. It is a no-op (nothing is logged) if db has not grown past length(idx). Mirrors SearchGraph's index!: grow database(idx) first (e.g. push_item!(database(idx), obj) / append_items!(database(idx), items)), then call index!(idx, ctx) to catch up. push_item!/append_items! on idx itself already call this internally, so it only needs to be called explicitly when db was grown directly. This is the sole emitter of the :add! log event for the batch it indexes – see the exactly-once contract documented on OBSERVE.

rebuild(g::SearchGraph, ctx::SearchGraphContext;
    progress=Progress(length(g); desc="rebuild", dt=2.0))

Rebuilds the SearchGraph index but seeing the whole dataset for the incremental construction, i.e., it can connect the i-th vertex to its knn in the 1..n possible vertices instead of its knn among 1..(i-1) as in the original algorithm. Returns a new SearchGraph (the input g is not modified).

g.algo[]'s maxvisits is not carried over verbatim into the rebuild search: it may have been tuned for a smaller, partial graph (e.g. by OptimizeParameters during incremental insertion, before every vertex existed) or for a completely different distance/database (e.g. a cheap proxy sketch used only to bootstrap g's current topology), and in either case isn't necessarily right for searching the whole, final graph with g's actual distance, which is what this function's own neighborhood search does. Carrying it over would silently cap every node's rebuild-time search at that value, baking a permanently degraded topology into the result – no later optimize_index! call can fix that, since it only retunes search-time parameters, not the graph's edges. bsize/Δ (the fields optimize_index! itself explores) are kept as-is; only maxvisits is reset to a fresh BeamSearch()'s default before searching, and the result carries that reset config forward too.

Arguments

• g: The search index to be rebuild.
• ctx: The context to run the procedure, it can differ from the original one; ctx.maxbatches bounds the number of batches used by the internal @BATCHES calls (passed as getminbatch(ctx, n)), bounding the size of the per-batch scratch buffer (qcache) regardless of n; see getminbatch for the trade-offs of capping it.

Keyword Arguments

• progress: a ProgressMeter.Progress object (or nothing to disable) used to report progress.

Examples

ctx = SearchGraphContext()
G = SearchGraph(dist, db)
index!(G, ctx)
G = rebuild(G, ctx)

abstract type AbstractLog end

Root of the logging taxonomy. A log is stored in a context (a subtype of AbstractContext) and receives events emitted by index operations, so that those operations can report what they do without depending on any particular backend.

There are two kinds of log, and a context holds them in two separate slots because they answer two different questions:

• AbstractReporter, in ctx.reporters — renders an event somewhere a human or a service will read it: stderr, a file, a monitoring endpoint. Receives INFORM.
• AbstractObserver, in ctx.observers — reacts to an event so that something durable happens: persist the range that was just inserted, checkpoint, update statistics. Receives OBSERVE.

Keeping them apart is what makes it possible to silence the console without disabling persistence (reporters=[] leaves observers intact), and what lets an internally built context inherit the caller's reporters without inheriting its observers – see OBSERVE for why that second one matters.

Rules

• A reporter is meant to be shared; that is what makes one throttle govern one console instead of several indexes fighting over the screen with a dt each.
• An observer belongs to exactly one index. Its state is that index's id ranges, and sharing it across indexes mixes two histories into one stream.
• Never call OBSERVE or INFORM inside a @BATCHES block. Backends carry no lock: every mutating entry point (push_item!, append_items!, index!) is serial by design and every call site today sits outside any parallel region. Breaking this costs a duplicated or garbled line rather than corruption, but it also breaks the exactly-once guarantee OBSERVE consumers rely on.

abstract type AbstractReporter <: AbstractLog end

A log that renders events for reading: to stderr, to a file, to a service. Reporters live in ctx.reporters and receive INFORM. A concrete subtype must implement

INFORM(r::MyReporter, ctx, msg::Function, index, data)

where msg is a zero-argument function returning the message text, index is the index the message is about or nothing, and data is an arbitrary structured payload or nothing. ctx is the context the message came from, or nothing when it came from a function that has no context (see INFORM's vector form).

Call msg() only after deciding the message will be emitted. That is the whole point of it being a function: a throttled or filtered message must not pay for building its own text.

See InformativeLog for the reference implementation.

abstract type AbstractObserver <: AbstractLog end

A log that reacts to structural events so that something durable happens. Observers live in ctx.observers and receive OBSERVE. A concrete subtype must implement

OBSERVE(o::MyObserver, event::Symbol, index::AbstractSearchIndex, ctx::AbstractContext, sp::Integer, ep::Integer)

See CallbackLog for the reference implementation, and OBSERVE for the contract the event stream obeys.

INFORM(ctx::AbstractContext, msg; index=nothing, data=nothing)

Sends a free-form message to every reporter in ctx.reporters, in order. Unlike OBSERVE this carries no contract at all: the message does not have to say what it affects, and neither index nor data is required.

msg may be a String or a zero-argument function returning one; a String is wrapped. Prefer @inform at call sites: it also skips building the message when there are no reporters at all.

Keyword Arguments

• index: the index the message is about, when there is one. A reporter may use it (e.g. to append the current length); it is never required.
• data: an arbitrary structured payload for a reporter that does not want text – a service emitting JSON takes this, stderr takes the string.

INFORM(log::InformativeLog, ctx, msg::Function, index, data)

Prints one status line, unless log.dt > 0 and fewer than log.dt seconds have elapsed since the previous printed line, in which case nothing happens and msg is never called. See InformativeLog for the dt <= 0 case.

@inform ctx "message $(interpolated)"
@inform ctx "message" index=idx data=(; k, n)
@inform reporters "message"

Call-site form of INFORM. Expands to an emptiness check on the reporter list followed by an INFORM whose message is a closure, so that a silenced context pays neither for the message nor for the closure that would have built it. Use it in preference to calling INFORM directly, especially at sites that run once per indexed item.

The first argument is a context, or a bare vector of reporters for a function that has none.

InformativeLog(io=nothing; dt::Real=1.0, prompt::AbstractString="LOG")

The reference AbstractReporter: renders a message as a status line, throttled so that it prints at most once every dt seconds. The line carries the message, the index length when the message names an index, live heap and max-RSS, and a timestamp.

Arguments

• io: where to write. nothing (the default) means whatever stderr is bound to at print time, so redirect_stderr follows it; pass an IO (an open file handle, stdout, ...) to fix a destination. The stream is flushed after every line.

Keyword Arguments

• dt: minimum number of seconds between two printed lines. dt <= 0 disables throttling entirely, and then no message is ever dropped – at the cost of making the reporter a serialization point, which is invisible at a per-block call site and very much not invisible at a per-item one. With dt > 0, throttling is the only reason a message is ever lost.
• prompt: a prefix printed at the beginning of every line, useful to tell apart the reporters of different indexes or stages.

Examples

using SimilaritySearch

ctx = GenericContext()                                          # prints to stderr, dt=1
ctx = GenericContext(; reporters=InformativeLog(; dt=10))       # once every 10 seconds
ctx = GenericContext(; reporters=InformativeLog(open("build.log", "a")))  # to a file
ctx = GenericContext(; reporters=[InformativeLog(), InformativeLog(io)])  # to both
ctx = GenericContext(; reporters=[])                            # silent

OBSERVE(ctx::AbstractContext, event::Symbol, index::AbstractSearchIndex, sp::Integer, ep::Integer)

Reports a structural event to every observer in ctx.observers, in order. Called by index operations that mutate the index (push_item!, append_items!, index!).

The event contract

event names what happened, not which Julia function was called – it must not simply mirror the name of the calling method (:push_item!, :append_items!, :index!, ...). It is one of a small, curated set of event kinds. Today there is exactly one:

• :add! – one or more objects were added to the index, and sp:ep is the exact, contiguous range of ids affected by this call. Every index type (SearchGraph, ExhaustiveSearch/ParallelExhaustiveSearch, InvertedFile/DictInvertedFile, BM25InvertedFile, Sat) emits this same event, regardless of whether the call arrived via a single-item push_item! or a batch append_items!/index! – one canonical name for one canonical kind of mutation, not one name per entry point.

Anything that is not structural – an index! on a brute-force index where db already is the index, so there is nothing to build – is not an event at all: it is an @inform message. The observation channel carries no informative pings, so a consumer never has to learn which event kinds to ignore.

Exactly-once: when one mutating function calls another mutating function internally (e.g. an append_items! that delegates its actual work to index!), only the function that performs/owns the mutation may call OBSERVE for that range – a caller that purely delegates must stay silent, never reporting the same range again under a different (or the same) event name. See SimilaritySearch.InvertedFiles's append_items!/index! (or SearchGraph's, in searchgraph/insertions.jl) for the reference pattern: the outer function delegates without observing, and the inner function it calls is the sole emitter.

Why this precision matters: every current index type is append-only (ids are assigned monotonically and are never removed or modified), so a correctly-behaving stream of :add! events – exactly one per logical batch, with an accurate, gap-free sp:ep – is on its own sufficient for a consumer to reconstruct or checkpoint which ids are durably indexed at any point in time. This is what makes the mechanism usable as a write-ahead log for incremental or crash-recoverable indexing: a consumer can replay the :add! stream instead of re-deriving state from the index itself. Duplicate events, an event misnamed as if it were a different action, or an inaccurate sp:ep silently break that invariant.

Observers do not travel into internally built contexts. Several functions build a context of their own for a scratch index (see hints.jl's EpsilonHints callback). That scratch index emits :add! for ids of a different index; letting those reach the caller's observers would corrupt the very reconstruction described above. Reporters do travel, which is what makes silencing reach the whole call tree. Inherit observers only when the new context drives the same index the caller's observers are already watching.

Examples

using SimilaritySearch

struct Recorder <: AbstractObserver
    events::Vector{Tuple{Symbol,Int,Int}}
end

SimilaritySearch.OBSERVE(o::Recorder, event, index, ctx, sp, ep) = push!(o.events, (event, Int(sp), Int(ep)))

rec = Recorder([])
ctx = GenericContext(; reporters=[], observers=rec)   # silent, but still observed
idx = ExhaustiveSearch(Dist.SqL2(), MatrixDatabase(rand(Float32, 4, 0)))
append_items!(idx, ctx, MatrixDatabase(rand(Float32, 4, 10)))
rec.events   # [(:add!, 1, 10)]

OBSERVE(log::CallbackLog, event::Symbol, index::AbstractSearchIndex, ctx::AbstractContext, sp::Integer, ep::Integer)

Invokes log.callback(index, sp, ep). See CallbackLog.

CallbackLog(callback::Function)

The reference AbstractObserver: calls callback(index, sp, ep) on every event it receives. This is the mechanism to persist, checkpoint, or account for a range of ids the moment it becomes part of the index.

The callback runs inline and its exceptions propagate: if the durable write fails, the insertion that triggered it fails too, which is the correct behaviour for a write-ahead log. It is not called concurrently – see AbstractLog's rules – so it needs no locking of its own, but it does belong to exactly one index.

Examples

using SimilaritySearch

ranges = Tuple{Int,Int}[]
ctx = GenericContext(; observers=CallbackLog((index, sp, ep) -> push!(ranges, (Int(sp), Int(ep)))))

LOG(args...)

Removed. The single logging call was split in two, along with the single ctx.logger slot that received it:

• OBSERVE(ctx, event, index, sp, ep) reports a structural event to ctx.observers.
• INFORM(ctx, msg) / @inform sends a free-form message to ctx.reporters.

A backend that used to implement LOG now implements one of the two, and declares itself AbstractReporter or AbstractObserver accordingly. LogList is gone as well: the context field is already a list, and reporters=[] is how a context is silenced.

L1()

The manhattan distance or $L_1$ is defined as

\[L_1(u, v) = \sum_i{|u_i - v_i|}\]

L2()

The euclidean distance or $L_2$ is defined as

\[L_2(u, v) = \sqrt{\sum_i{(u_i - v_i)^2}}\]

SqL2()

The squared euclidean distance is defined as

\[L_2(u, v) = \sum_i{(u_i - v_i)^2}\]

It avoids the computation of the square root and should be used whenever you are able do it.

LInfty()

The Chebyshev or $L_{\infty}$ distance is defined as

\[L_{\infty}(u, v) = \max_i{\left| u_i - v_i \right|}\]

Lp(p)
Lp(p, pinv)

The general Minkowski distance $L_p$ distance is defined as

\[L_p(u, v) = \left|\sum_i{(u_i - v_i)^p}\right|^{1/p}\]

Where $p_{inv} = 1/p$. Note that you can specify unrelated p and pinv if you need an specific behaviour.

Cosine()

The cosine is defined as:

\[\cos(u, v) = \frac{\sum_i u_i v_i}{\sqrt{\sum_i u_i^2} \sqrt{\sum_i v_i^2}}\]

The cosine distance is defined as $1 - \cos(u,v)$

NormCosine()

Similar to Cosine but suppose that input vectors are already normalized, and therefore, reduced to simply one minus the dot product.

\[1 - \sum_i {u_i v_i}\]

Angle()

The angle distance is defined as:

\[∠(u, v)= \arccos(\cos(u, v))\]

NormAngle()

Similar to Angle but suppose that input vectors are already normalized

\[\arccos \sum_i {u_i v_i}\]

Jaccard()

The Jaccard distance is defined as

\[J(u, v) = \frac{|u \cap v|}{|u \cup v|}\]

Dice()

The Dice distance is defined as

\[D(u, v) = \frac{2 |u \cap v|}{|u| + |v|}\]

Intersection()

The intersection dissimilarity uses the size of the intersection as a mesuare of similarity as follows:

\[I(u, v) = 1 - \frac{|u \cap v|}{\max \{|u|, |v|\}}\]

CosineSet()

The cosine distance for very sparse binary vectors represented as sorted lists of positive integers where ones occur.

RogersTanimoto(σ)

The Rogers-Tanimoto dissimilarity for very sparse binary vectors represented as sorted lists of positive integers where ones occur (as with Jaccard, Dice, and CosineSet). The field σ is the size of the full universe, i.e., the total number of possible elements/dimensions, and is used to recover the number of positions where both a and b are zero.

Using the usual contingency-table notation for two binary vectors, with $tt$ the number of shared ones (the intersection size), $tf$ and $ft$ the number of ones that appear in only one of the two sets, and $ff = \sigma - tt - tf - ft$ the number of shared zeros, the Rogers-Tanimoto dissimilarity is defined as

\[RT(u, v) = 1 - \frac{tt + ff}{tt + ff + 2(tf + ft)}\]

Access via Dist.Sets.RogersTanimoto.

Examples

d = Dist.Sets.RogersTanimoto(σ)
evaluate(d, u, v)

Hamming()

Binary hamming uses bit wise operations to count the differences between bit strings

RogersTanimoto()

The Rogers-Tanimoto dissimilarity for binary vectors represented as arrays of unsigned integers (bit strings), where each bit is a binary attribute. Access via Dist.Bits.RogersTanimoto.

Using $tt$ for the number of bits set to one in both a and b, $ff$ for the number of bits set to zero in both, and $tf$, $ft$ for the number of mismatching bits, the dissimilarity is defined as

\[RT(u, v) = 1 - \frac{tt + ff}{tt + ff + 2(tf + ft)}\]

Examples

d = Dist.Bits.RogersTanimoto()
evaluate(d, u, v)

RussellRao()

The Russell-Rao dissimilarity for binary vectors represented as arrays of unsigned integers (bit strings), where each bit is a binary attribute. Access via Dist.Bits.RussellRao.

It measures the fraction of bits set to one in both a and b ($tt$) with respect to the total number of bits $n$ (computed as length(a) * 64, i.e., it assumes 64-bit words):

\[RR(u, v) = 1 - \frac{tt}{n}\]

Examples

d = Dist.Bits.RussellRao()
evaluate(d, u, v)

CommonPrefix()

Uses the common prefix as a measure of dissimilarity between two strings

Levenshtein(; icost=1, dcost=1, rcost=1)
Levenshtein(ctx; icost=1, dcost=1, rcost=1)

The levenshtein distance measures the minimum number of edit operations to convert one string into another. The costs insertion icost, deletion cost dcost, and replace cost rcost.

Scratch buffers, and why there is no lock

evaluate needs a row of Int16s (plus, for AbstractString inputs, a Vector{Char}). A Levenshtein built the ordinary way owns no scratch and allocates what it needs per call, which is what makes it safe to share across tasks unconditionally – there is no mutable state to race on, under any scheduler or any concurrency model of your own.

To skip even that allocation, ask beginbatch for a batch-local copy at the top of a @BATCHES batch (bdist = beginbatch(distance(index))) and use that inside the batch. The copy owns private buffers it grows once and reuses; a batch is single-tasked, so nothing guards them and nothing needs to.

This replaced a Channel-based buffer pool. The pool was safe, but its take!/put! pair per call turned out to cost far more than the work it was protecting whenever evaluations are cheap: on a 200k-element parallel map of 5-10 character words over 64 threads it was ~80x slower than allocating (302ms vs 3.6ms), and it lost even single-threaded.

ctx is still accepted and ignored, so old call sites keep working – it used to size the pool. It will go away in 2.0.

AbstractString inputs (String, SubString, ...)

a/b can be passed as plain String/SubString directly – Unicode included – with no need to collect them into a Vector{Char} first. A dedicated method (see below) walks each string with Julia's string-iteration protocol (for c in s, the efficient, allocation-free equivalent of repeatedly calling nextind) instead of integer-indexing s[i] for i in 1:length(s), which is what the generic evaluate(::Levenshtein, a, b) method above does and why it throws StringIndexError on a String/SubString containing non-ASCII characters (a String is indexed by codeunit – a byte, for its UTF-8 encoding – not by character, and only ASCII characters take exactly one codeunit each). The shorter of the two strings is decoded once into a second pooled scratch buffer (see the scratch section above) so it can be randomly indexed inside the O(alen*blen) dynamic-programming loop; the longer one is walked forward-only and never needs random access, so it costs nothing beyond that same forward pass.

DamerauLevenshtein(; icost=1, dcost=1, rcost=1, tcost=1)
DamerauLevenshtein(ctx; icost=1, dcost=1, rcost=1, tcost=1)

The restricted Damerau-Levenshtein distance (a.k.a. Optimal String Alignment, OSA): Levenshtein extended with a fourth edit operation, the transposition of two adjacent characters, at cost tcost. This captures a common typo pattern, e.g. "form" -> "from" (the middle "or" swapped to "ro"), as a single edit instead of two substitutions.

This is the restricted variant: it disallows editing a substring that already participated in a transposition again, which is what keeps the algorithm inside the same row-by-row scratch-buffer scheme as Levenshtein (a small extra lookback row, rather than a full O(alen*blen) matrix). The consequence is that this distance is a SemiMetric, not a Metric: it satisfies d(a,a) == 0 and d(a,b) == d(b,a), but not the triangle inequality (e.g. evaluate(dl, "ca", "abc") can exceed evaluate(dl, "ca", "ac") + evaluate(dl, "ac", "abc")) – the unrestricted/"true" Damerau-Levenshtein distance that does satisfy it needs the full matrix and is not implemented here.

AbstractString inputs (String, SubString, ...)

a/b can be passed as plain String/SubString directly – Unicode included – via a dedicated method (see below); see Levenshtein's docstring for why the generic evaluate(::DamerauLevenshtein, a, b) method above throws StringIndexError on those inputs and how the AbstractString method avoids it (string-iteration instead of s[i]-indexing, plus a scratch buffer holding the shorter string's characters).

evaluate(::DamerauLevenshtein, a, b) handles scratch exactly as Levenshtein does – allocated per call unless beginbatch handed out a batch-local copy, never locked – the only difference being that three rolling rows (current, previous, and two-rows-back, for the transposition lookback) share one buffer instead of one row using it.

Hamming()

The hamming distance counts the differences between two equally sized strings

LCS()
LCS(ctx)

Instantiates a Levenshtein object to perform LCS distance. See Levenshtein for the meaning of ctx (optional; sizes the internal scratch pool from ctx.maxbatches).

Hausdorff(dist::PreMetric)

Hausdorff distance is defined as the maximum of the minimum between two clouds of points.

\[Hausdorff(U, V) = \max{\max_{u \in U} nndist(u, V), \max{v \in V} nndist(v, U) }\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

DirectedHausdorff(dist::PreMetric)

The directed (one-sided) Hausdorff distance from a cloud of points u to a cloud v: how far you'd have to look, starting from the point of u that is worst served by v, to find its nearest neighbor in v. Unlike Hausdorff (its symmetrized, two-sided counterpart), this is generally not symmetric: evaluate(d, u, v) != evaluate(d, v, u) in general, since swapping which cloud is "covered by" the other measures a different quantity.

\[DirectedHausdorff(U, V) = \max_{u \in U} nndist(u, V)\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

Examples

d = Dist.Cloud.DirectedHausdorff(Dist.L2())
evaluate(d, U, V)  # how far U strays from V
evaluate(d, V, U)  # how far V strays from U -- not the same value in general

Chamfer(distance)

Computes the Chamfer dissimilarity between two point clouds

\[Chamfer(U, V) = \frac{1}{|U|}\sum_{u \in U} nndist(u, V) + \frac{1}{|V|}\sum_{v \in V} nndist(v, U)\]

where $nndist(u, V)$ computes the distance of $u$ to its nearest neighbor in $V$ using the dist metric.

EMD(dist, p)

Approximates the Earth Mover's Distance (EMD) between two point clouds U and V of the same size as a greedy perfect matching: points are matched one at a time, each being paired with its nearest still-unmatched point in the other cloud (measured with dist), and the distances of the matched pairs are then combined with an $L_p$-like aggregation.

Arguments

• dist: the base distance function used to compare individual points of the clouds.
• p: the exponent used to combine the distances of the matched pairs, i.e.,

\[EMD(U, V) = \left(\sum_i evaluate(dist, u_i, v_{\pi(i)})^p \right)^{1/p}\]

where $\pi$ is the greedy matching found by the algorithm.

Note that this is a greedy approximation of the assignment problem underlying the exact EMD (optimal transport), not the exact solution, and it requires length(U) == length(V).

Examples

d = Dist.Cloud.EMD(Dist.L2(), 2f0)
evaluate(d, U, V)

NegativeDistanceHack(dist)

Evaluates as the negative of the distance function being wrapped. This is not a real distance function but a simple hack to get a similarity and use it for searching for farthest elements (farthest points / farthest pairs) on indexes that can handle this hack (e.g., ExhaustiveSearch, ParallelExhaustiveSearch, SearchGraph).

SimilarityFromDistance(dist)

Evaluates as $1/(1 + d)$ for a distance evaluation $d$ of dist. This is not a distance function and is part of the hacks to get a similarity for searching farthest elements on indexes that can handle this hack (e.g., ExhaustiveSearch, ParallelExhaustiveSearch, SearchGraph).

DistanceWithIdentifiers(distance, database)

Wraps the given database and distance with a proxy database that is accessed with integers from 1 to n

getminbatch(n::Int, nt::Int=Threads.nthreads();
            blocks_per_thread::Int=4, maxbatches::Int=n)

The official, always-valid way to compute a minbatch size for @BATCHES. Always returns a value >= 1 (or n itself when n <= 0 or nt <= 1), so callers do not need to clamp its result themselves.

maxbatches is a plain Int, deliberately with no special/sentinel value (no 0 meaning "off", no Union{Nothing,Int}) – it is simply a hard ceiling on the batch count, always in effect, and defaults to n because n is already the largest a batch count could ever sensibly be (a batch needs >= 1 element, so more than n batches is meaningless). That default is therefore a genuine no-op, not a disguised "disabled" flag: whatever blocks_per_thread * nt computes is used as-is. Pass anything smaller and it takes direct, immediate effect on the result – there is nothing else to know. This also keeps the function fully type-stable/monomorphic and total (every Int, including 0 or negative, produces a well-defined result; see below), cheap to call from performance-sensitive code.

• blocks_per_thread (default 4): the natural batch-count target is blocks_per_thread * nt – always tied to the thread count, never an independent/arbitrary number.
• maxbatches (default n, i.e. no effective restriction): a hard ceiling on the batch count, overriding the natural target above whenever it would be larger. Use this to directly bound the memory of per-batch scratch allocations (e.g. @BATCHES's @BEGIN-declared, @nbatches()-sized buffers) for very large n. When a context object is available, prefer the getminbatch(ctx::AbstractContext, n) overload (searchgraph/context.jl) instead, which derives this from ctx.maxbatches.

Arguments

• n: the number of elements to process
• nt: number of threads to use (defaults to Threads.nthreads())

Keyword Arguments

• blocks_per_thread: target batches per thread (default 8)
• maxbatches: hard cap on the total batch count, for bounding per-batch memory directly regardless of nt (defaults to n, a no-op unless set to something smaller)

getminbatch(ctx::AbstractContext, n::Int, nt::Int=Threads.nthreads(); blocks_per_thread::Int=8)

getminbatch overload that derives its maxbatches cap from ctx.maxbatches, so that any batch count computed for operations driven by ctx never exceeds the capacity of its per-batch caches (vstates/beams, for SearchGraphContext). This is the preferred way to compute minbatch for any @BATCHES loop that has a context object available.

abstract type AbstractContext end

Base type for context objects (e.g. GenericContext, SearchGraphContext): per-call configuration, hyperparameters, caches, and a logger, passed alongside an index to search, searchbatch, index!, and similar functions.

GenericContext(KnnType::Type{<:AbstractKnnQueue}=KnnSorted;
    verbose::Bool=false, reporters=InformativeLog(), observers=nothing,
    maxbatches::Integer=8Threads.nthreads(), batchid::Integer=1,
    scheduler::Symbol=get_batch_scheduler()) -> GenericContext

Lightweight AbstractContext implementation used by exact indexes (ExhaustiveSearch, ParallelExhaustiveSearch) that need no per-thread scratch caches.

Keyword Arguments

• verbose: whether the chatty, per-iteration messages (optimization progress, hint selection) are produced at all. It is a level, not an output switch – the switch is reporters.
• reporters: where progress messages go, see AbstractReporter. Accepts one reporter, a vector of them, or nothing. Pass reporters=[] to silence this context completely: with no destination, a message is not even built. Defaults to a fresh InformativeLog.
• observers: what reacts to structural events, see AbstractObserver. Same shapes. Defaults to none – the library never installs an observer of its own. Silencing the reporters leaves the observers untouched, which is the point of them being separate slots.
• maxbatches: hard cap on the batch count used by getminbatch for operations driven by this context (e.g. searchbatch!, allknn, closestpair, search). Defaults to 8 * Threads.nthreads(), matching getminbatch's own default blocks_per_thread.
• batchid: the batch slot this context is tagged with; not meaningful on the root context returned here (always 1) – per-batch copies tagging the running @batchid() are minted internally via Accessors.@set, one per batch, not per call.
• scheduler: the @BATCHES scheduler used by every @BATCHES call driven by this context (passed through as scheduler=ctx.scheduler). Defaults to whatever get_batch_scheduler currently returns, captured once at construction time (later calls to set_batch_scheduler! do not retroactively change an already-built context). Pass scheduler=:sequential to force every @BATCHES call driven by this context to run unthreaded, regardless of Threads.nthreads().
• costdists/costblocks: per-batch distance/block-evaluation counters (size maxbatches, indexed by batchid), accumulated via add_distance_evaluations!/add_block_evaluations! and read via distance_evaluations/distance_stats and their block counterparts. Never reset automatically – they accumulate for the lifetime of the context.

SearchGraphContext(KnnType::Type{<:AbstractKnnQueue}=KnnSorted,
    vstates=nothing;
    verbose=false,
    reporters=InformativeLog(dt=2.0), observers=nothing,
    neighborhood=Neighborhood(filter=SatNeighborhood()),
    hints_callback=RandomHints(; logbase=1.1),
    hyperparameters_callback=OptimizeParameters(),
    maxbatches=8Threads.nthreads(),
    parallel_block=maxbatches,
    logbase_callback=1.5,
    starting_callback=256,
    batchid=1,
    scheduler::Symbol=get_batch_scheduler(),
    beams=nothing
) -> SearchGraphContext

SearchGraphContext(ctx::SearchGraphContext; kwargs...) -> SearchGraphContext

Context object that stores configuration, callbacks, and pre-allocated caches used while building and searching a SearchGraph. It must be passed along to functions like index!, search, searchbatch, and optimize_index!.

The first method builds a new context from scratch, selecting the priority-queue implementation KnnType (e.g., KnnSorted or KnnHeap) used internally, and a per-batch vstates cache of visited-vertices buffers (one entry per batch, up to maxbatches). The second method (a copy constructor) creates a modified copy of an existing context ctx, overriding only the given keyword arguments while reusing the same KnnType and vstates.

Arguments

• KnnType: type of priority queue used for the internal knn caches (beams), defaults to KnnSorted.
• vstates: per-batch cache of visited-vertices buffers, one entry per batch (nothing builds a fresh one sized by maxbatches).

Keyword Arguments

• verbose: whether the chatty, per-iteration messages (optimization progress, hint selection) are produced at all. It is a level, not an output switch – the switch is reporters.
• reporters: where progress messages go, see AbstractReporter. Accepts one reporter, a vector of them, or nothing. Pass reporters=[] to silence this context completely: with no destination, a message is not even built. Defaults to a fresh InformativeLog with dt=2.0.
• observers: what reacts to structural events, see AbstractObserver. Same shapes. Defaults to none – the library never installs an observer of its own. Silencing the reporters leaves the observers untouched, which is the point of them being separate slots.
• neighborhood: specifies how neighborhoods are computed, see Neighborhood for more info.
• hints_callback: a callback to compute hints, please check hints.jl for more info.
• hyperparameters_callback: a callback to compute search hyperparameters, see OptimizeParameters for more info.
• logbase_callback: a log base to control when to run callbacks.
• starting_callback: when to start to run callbacks, minimum index length to do it.
• parallel_block: the size of the block that is processed in parallel.
• maxbatches: hard cap on the batch count used by getminbatch for operations driven by this context, and the capacity (number of columns/entries) of vstates/beams when they are built automatically. Defaults to 8 * Threads.nthreads().
• batchid: the batch slot this context is tagged with (indexes into vstates/beams). Not meaningful on the root context (always 1) – per-batch copies tagging the running @batchid() are minted internally via beginbatch(ctx, @batchid()), once per batch, not passed here directly.
• scheduler: the @BATCHES scheduler used by every @BATCHES call driven by this context (passed through as scheduler=ctx.scheduler). Defaults to whatever get_batch_scheduler currently returns, captured once at construction time (later calls to set_batch_scheduler! do not retroactively change an already-built context). Pass scheduler=:sequential to force every @BATCHES call driven by this context to run unthreaded, regardless of Threads.nthreads().
• beams: knn queues cache used while inserting elements (used by BeamSearch; nothing builds a fresh one sized by maxbatches).

Each of these keyword arguments is stored verbatim in the field of the same name.

Notes

• The callbacks are triggers that are called whenever the index grows enough. They keep hyperparameters and structure in shape.
• The search graph is composed of direct and reverse links; direct links are controlled with a neighborhood object, mostly used to control how neighborhoods are refined. Reverse links are created when a vertex appears in the neighborhood of another vertex.
• parallel_block: The number of elements that the multithreading algorithm processes at once, it is important to be larger that the number of available threads but not so large since the quality of the search graph could degrade (a few times the number of threads is enough). If parallel_block=1 the algorithm becomes sequential.
• beams and vstates are caches that alleviate memory allocations in SearchGraph construction and searching, indexed by batchid (race-free under every @BATCHES scheduler, unlike the Threads.threadid()-indexing used before). Relevant on multithreading scenarios where distance functions, evaluate,

can call other metric indexes that can use these shared resources (globally defined).

Examples

using SimilaritySearch

ctx = SearchGraphContext()                          # default configuration
ctx = SearchGraphContext(; verbose=true)             # per-iteration optimization detail too
ctx = SearchGraphContext(; reporters=[])             # silent
ctx2 = SearchGraphContext(ctx; parallel_block=64)    # copy overriding one keyword
ctx3 = SearchGraphContext(; maxbatches=4Threads.nthreads())  # smaller batch-cache cap

BeamSearch(; bsize::Integer=4, Δ::Real=1.0, maxvisits::Integer=10^6) -> BeamSearch

BeamSearch is an iteratively improving local search algorithm that explores the graph using blocks of bsize elements and neighborhoods at the time.

Keyword Arguments

• bsize: The size of the beam.
• Δ: Soft margin for accepting elements into the beam.
• maxvisits: Maximum number of node visits allowed while searching, useful for early stopping without convergence.

Examples

using SimilaritySearch

algo = BeamSearch(; bsize=8, Δ=1.0, maxvisits=10^6)
G = SearchGraph(Dist.SqL2(), VectorDatabase(); algo=Ref(algo))

BeamSearchSpace(; bsize=2:2:16, Δ=0.9:0.025:1.1, bsize_scale=(...), Δ_scale=(...))

Defines the search space explored by SearchModels.jl when autotuning BeamSearch's hyperparameters, used by optimize_index! (through OptimizeParameters).

Keyword Arguments

• bsize: range of candidate values for BeamSearch's bsize (beam size) hyperparameter.
• Δ: range of candidate values for BeamSearch's Δ (soft margin) hyperparameter; this strongly depends on the dataset, so it may need to be adjusted.
• bsize_scale: named tuple of scaling parameters (s, p1, p2, lower, upper) passed to SearchModels.scale to mutate bsize values.
• Δ_scale: named tuple of scaling parameters (s, p1, p2, lower, upper) passed to SearchModels.scale to mutate Δ values.

Examples

space = BeamSearchSpace(; bsize=2:2:32)
optimize_index!(index, ctx; space)

OptimizeParameters(kind=MinRecall(0.9);
    initialpopulation=16,
    maxiters=12,
    bsize=4,
    mutbsize=4bsize,
    crossbsize=2bsize,
    maxpopulation=initialpopulation,
    ksearch=10,
    queries=nothing,
    numqueries=32,
    space::BeamSearchSpace=BeamSearchSpace()
)

Creates a hyperoptimization callback using the given parameters

Arguments

• kind: The kind of error function, e.g. MinRecall(0.9).
• hints: How search hints should be computed.
• initialpopulation: Optimization argument that determines the initial number of configurations.
• maxiters: Optimization argument that determines the number of iterations.
• bsize: Optimization argument that determines how many top configurations are allowed to mutate and cross.
• mutbsize: Number of elements to be generated from mutation
• crossbsize: Number of elements to be generated from crossing
• maxpopulation: The maximum size that the population can be
• ksearch: The number of neighbors to be retrived by the optimization process.
• queries: The queryset to be used during the optimization process.
• numqueries: The number of queries to be performed during the optimization process.
• space: The cofiguration search space

See more

• See BeamSearchSpace
• SearchParams arguments of SearchModels.jl

for more details

optimize_index!(
    index::AbstractSearchIndex,
    ctx::AbstractContext,
    kind::ErrorFunction=MinRecall(0.9);
    space::AbstractSolutionSpace=optimization_space(index),
    queries=nothing,
    ksearch=10,
    radius=nothing,
    kmin=8,
    numqueries=64,
    initialpopulation=16,
    maxpopulation=16,
    bsize=4,
    mutbsize=16,
    crossbsize=8,
    maxiters=16,
    params=SearchParams(; maxpopulation, bsize, mutbsize, crossbsize, maxiters, verbose=verbose(ctx)),
    rng=Random.default_rng()
)

Tries to configure the index to achieve the specified performance (kind). The optimization procedure is an stochastic search over the configuration space yielded by kind and queries.

Arguments

• index: the index to be optimized
• ctx: index ctx (caches and general hyperparameters)
• kind: The kind of optimization to apply, it can be ParetoRecall(), ParetoRadius(), MinRecall(r) where r is the expected recall (0-1, 1 being the best quality but at cost of the search time), or MaxMatchError(; maxerror) (a smoother, distance-based alternative to MinRecall, see MaxMatchError)

Keyword arguments

• space: defines the search space
• queries: the set of queries to be used to measure performances, a validation set. It can be an AbstractDatabase or nothing.
• ksearch: the number of neighbors to retrieve for queries (k-NN workloads only; ignored when radius is given)
• radius: tune for radius-bounded (epsilon-ball) queries of this radius instead of k-NN queries. The gold standard becomes each query's true ball – of whatever size, empty included – and candidates are scored with matcherror over it, so this requires kind::MaxMatchError; the recall-based goals raise an ArgumentError, since macrorecall divides by the gold ball's size and a small radius routinely produces empty balls. What gets tuned is an ordinary BeamSearch, so the result also governs later k-NN searches on the index.
• kmin: navigation reserve used while tuning (see BallKnn); pass the value the radius searches themselves will use, since a configuration is only tuned relative to it
• numqueries: if queries===nothing then a sample of the already indexed database is used, numqueries is the size of the sample.
• rng: random number generator used to draw the sample of queries when queries===nothing.
• initialpopulation: the initial sample for the optimization procedure
• params: the parameters of the solver, see SearchParams arguments of SearchModels.jl package for more information. Alternatively, you can pass some keywords arguments to SearchParams, and use the rest of default values:
  • initialpopulation=16: initial sample
  • maxpopulation=16: population upper limit
  • bsize=4: beam size (top best elements used by select, mutate and crossing operations.)
  • mutbsize=16: number of mutated new elements in each iteration
  • crossbsize=8: number of new elements from crossing operation.
  • maxiters=16: maximum number of iterations.

Examples

ctx = SearchGraphContext()
G = SearchGraph(dist, db)
index!(G, ctx)
optimize_index!(G, ctx, MinRecall(0.95))

optimize_index!(g::AsymmetricSearchGraph, ctx::SearchGraphContext, kind=MinRecall(0.9); queries, kwargs...)

Tunes the graph's search parameters on raw queries, which are required (the index holds no raw object to sample from) and prepared once by encodequery.

MinRecall(; minrecall=0.9f0) <: ErrorFunction

Optimization goal that favors the fastest configuration among those achieving at least minrecall recall (measured against a gold standard computed with exhaustive search).

Keyword Arguments

• minrecall: minimum recall (0-1) required to be considered as fast as possible.

Examples

optimize_index!(index, ctx, MinRecall(0.95))

OptRadius(; tol=0.1) <: ErrorFunction

Optimization goal that favors the fastest configuration among those whose search radius falls within a tol-sized tolerance band, without relying on a computed gold standard.

Keyword Arguments

• tol: relative tolerance used to bucket configurations by their achieved search radius.

Examples

optimize_index!(index, ctx, OptRadius(; tol=0.05))

ParetoRecall <: ErrorFunction

Optimization goal that searches for a good trade-off between speed and recall (measured against a gold standard computed with exhaustive search), without requiring a fixed minimum recall.

ParetoRadius <: ErrorFunction

Optimization goal that searches for a good trade-off between speed and the achieved search radius, without relying on a computed gold standard.

Neighborhood(; logbase=2, minsize=2, neardup=typemin(Float32), filter=SatNeighborhood())

Determines the size of the neighborhood; it is adjusted as a callback exponentially. More detailed, the insertion algorithm searches for $log_\text{logbase}(N) + minsize)$ in the index where $N$ is the size of the index/dataset, then these neighbors are filtered with filter. The algorithms use neardup to discard proximal items to be part of a neighborhood.

Parameters

• logbase=2: logarithmic base to determine the number of neighbors to retrieve
• minsize=2: minimum number of elements to retrieve
• neardup=typemin(Float32): distance to identify an element as duplicate (neardups could be ignored from neighborhoods)
• filter=SatNeighborhood(): strategy to reduce the number of neighbors

Note: Set $logbase=Inf$ to obtain a fixed number of $in$ nodes; and set $minsize=0$ to obtain a pure logarithmic growing neighborhood.

abstract type NeighborhoodFilter end

Postprocessing of a neighborhood using some criteria. Called from find_neighborhood!, which guarantees at least two candidates: it resolves the degenerate cases (zero candidates on the very first insertion, one candidate on the second) itself, so a filter never sees them.

IdentityNeighborhood()

A NeighborhoodFilter that does not modify the given neighborhood, i.e., it passes through the candidate result set unchanged.

Examples

neighborhood = Neighborhood(filter=IdentityNeighborhood())

SatNeighborhood()

New items are connected with a small set of items computed with a SAT like scheme (cite). It starts with k near items that are filterd to a small neighborhood due to the SAT partitioning stage.

Examples

neighborhood = Neighborhood(filter=SatNeighborhood())  # the default filter

DistalSatNeighborhood()

New items are connected with a small set of items computed with a Distal SAT like scheme (cite). It starts with k near items that are filterd to a small neighborhood due to the SAT partitioning stage but in reverse order of distance.

Examples

neighborhood = Neighborhood(filter=DistalSatNeighborhood())

KCentersNeighborhood()

A NeighborhoodFilter that reduces the given candidate neighborhood res by computing a small set of k-centers over it (using a farthest-first traversal) and keeping only the resulting centers, so that the final neighborhood is diverse rather than simply the closest items.

Examples

neighborhood = Neighborhood(filter=KCentersNeighborhood())

find_neighborhood!(out::AbstractKnnQueue, index::SearchGraph, ctx::SearchGraphContext, item, tmp::AbstractKnnQueue, blockrange; hints=index.hints)

Searches for item's neighborhood in the index, i.e., if item were in the index, which items should be its neighbors (internal function).

Arguments

• out: AbstractKnnQueue object where the resulting (filtered) neighborhood is stored.
• index: The search index.
• ctx: context, neighborhood, and cache objects to be used.
• item: The item to be inserted.
• tmp: AbstractKnnQueue object used as scratch space for the raw (unfiltered) search results.
• blockrange: Extra block range for parallel insertions, defaults to an empty range.

Keyword Arguments

• hints: Search hints

RandomHints(; logbase=1.1)

A Callback that selects search hints as a random sample of the dataset. Sampled objects are only accepted as hints if they (and their neighborhood) are not already part of the neighborhood of a previously accepted hint and have a minimum degree, which tends to favor well-connected entry points for searches.

Keyword Arguments

• logbase: log base used to compute the number of hints to keep, i.e., approximately log(logbase, n) hints are kept for a dataset of n elements.

Examples

ctx = SearchGraphContext(; hints_callback=RandomHints(; logbase=1.2))

DisjointHints(; logbase=1.1)

A Callback that selects search hints as a small subsample of mutually disjoint objects, i.e., objects whose neighborhoods do not overlap with the neighborhoods of other selected hints. Candidates are visited in decreasing order of how much their degree deviates from the mean degree of the graph.

Keyword Arguments

• logbase: log base used to compute the number of hints to keep, i.e., approximately log(logbase, n) hints are kept for a dataset of n elements.

Examples

ctx = SearchGraphContext(; hints_callback=DisjointHints(; logbase=1.2))

KDisjointHints(; logbase=1.1, disjoint=3, expansion=4)

A Callback that selects search hints by randomly visiting candidate objects and greedily accepting them as hints while marking their expanded neighborhood (up to expansion hops away) as visited, so that accepted hints tend to have disjoint neighborhoods.

Keyword Arguments

• logbase: log base used to compute the number of hints to keep, i.e., approximately log(logbase, n) hints are kept for a dataset of n elements.
• disjoint: parameter reserved to control the degree of disjointness enforced among hints (not read by the current sampling procedure).
• expansion: number of hops used to expand the neighborhood of an accepted hint before marking it as visited (i.e., excluded from being selected again).

Examples

ctx = SearchGraphContext(; hints_callback=KDisjointHints(; logbase=1.2, expansion=3))

EpsilonHints(; quantile=0.01, epsilon=0.0f0, minepsilon=1e-5, samplesize=sqrt, maxsize=x->log(1.1,x))

A Callback that selects search hints as a random sample of the dataset from which near-duplicate objects (those closer than a distance threshold epsilon) have been removed, so that the resulting hints are spread out over the dataset.

Keyword Arguments

• quantile: if greater than 0, epsilon is instead estimated as this quantile of a sample of pairwise distances; use quantile<=0 to use the fixed epsilon value instead.
• epsilon: fixed near-duplicate distance threshold, used only when quantile<=0.
• minepsilon: lower bound enforced on the estimated epsilon when quantile>0.
• samplesize: function of the dataset size n used to determine how many objects are initially sampled before near-duplicate removal.
• maxsize: function of the dataset size n used to determine the maximum number of hints to keep (extra hints beyond this size are discarded at random).

Examples

ctx = SearchGraphContext(; hints_callback=EpsilonHints(; quantile=0.05))

KCentersHints(; logbase=1.1, powsample=1.5, qdiscard=0.1)

A Callback that selects search hints using a k-centers (farthest-first traversal) strategy. A random sample of candidate objects is drawn from the dataset (filtered to exclude atypically low- or high-degree vertices), and a set of k centers is computed over that sample using a farthest-first traversal. Centers that end up receiving too few nearest neighbor assignments (i.e., that look redundant or of little use as entry points) are discarded before the remaining ones are used as hints.

Keyword Arguments

• logbase: log base used to compute the number of centers/hints to search for, i.e., approximately log(logbase, n) + 1 centers are computed for a dataset of n elements.
• powsample: exponent used to determine the size of the candidate sample from which centers are computed, i.e., k^powsample candidates are sampled (k being the number of centers).
• qdiscard: quantile, over the number of nearest-neighbor assignments received by each center, used to discard the least used centers (centers below this quantile are dropped).

Examples

ctx = SearchGraphContext(; hints_callback=KCentersHints(; logbase=1.2))

AdjacentStoredHints{DB<:AbstractDatabase}(hints::DB, map::Vector{Int32})

Stores a materialized copy of the hint objects (hints) together with the identifiers (map) of the corresponding elements in the original dataset. This allows hint objects to be kept in an alternative database representation DB (e.g., a MatrixDatabase) instead of being fetched by identifier from the main dataset on every access; see matrixhints.

Fields

• hints: database holding the materialized hint objects
• map: identifiers, in the original dataset, of each corresponding hint object

matrixhints(index::SearchGraph, ::Type{DBType}=MatrixDatabase) where {DBType<:AbstractDatabase}

Materializes the objects currently referenced by index's hints (stored as a list of identifiers) into an AdjacentStoredHints object backed by DBType, which can improve cache locality when hints are repeatedly accessed while searching. Returns a copy of index with the new hints installed (index itself is not modified).

Arguments

• index: the search graph whose current hints will be materialized
• DBType: the database type used to store the materialized hint objects, defaults to MatrixDatabase

Examples

G = SearchGraph(dist, db)
index!(G, ctx)
G = matrixhints(G)  # hints are now stored using a MatrixDatabase

abstract type Callback end

Abstract type to trigger callbacks after some number of insertions. SearchGraph stores the callbacks in callbacks (a dictionary that associates symbols and callback objects); A SearchGraph object controls when callbacks are fired using callback_logbase and callback_starting

execute_callbacks!(index::SearchGraph, context::SearchGraphContext, n=length(index), m=n+1; force=false)

Runs the registered callbacks (context.hints_callback and context.hyperparameters_callback) whenever the index has grown enough to cross a context.logbase_callback-logarithmic size threshold between n and m, and n is at least context.starting_callback. Internal function, called during insertion.

Arguments

• index: the search graph index.
• context: the context environment of the graph, see SearchGraphContext.
• n: current (lower) size used to decide whether callbacks should fire.
• m: size used as the upper bound of the comparison, defaults to n+1.

Keyword Arguments

• force: if true, callbacks are executed unconditionally.

abstract type AbstractDatabase end

Base type to represent databases. A database is a collection of objects that can be accessed like a similar interface to AbstractVector. It is separated to allow SimilaritySearch methods to know what is a database and what is an object (since most object representations will look as vectors and matrices).

The basic implementations are:

• MatrixDatabase: A wrapper for object-vectors stored in a Matrix, columns are the objects. It is static.
• DynamicMatrixDatabase: A dynamic representation for vectors that allows adding new vectors.
• MMapMatrixDatabase: Like BlockMatrixDatabase but backed by a memory-mapped file on disk instead of RAM.
• VectorDatabase: A wrapper for vector-like structures. It can contain any kind of objects.
• SubDatabase: A sample of a given database

In particular, the storage details are not used by VectorDatabase and MatrixDatabase. For instance, it is possible to use matrices like Matrix, SMatrix or StrideArrays; or even use generated objects with VectorDatabase (supporting a vector-like interface).

If the storage backend support it, it is possible to use vector operations, for example:

• get the i-th element obj = db[i], elements in the database are identified by position
• get the elements list in a list of indices lst as db[lst] (also using view)
• set a value at the i-th element db[i] = obj
• random sampling rand(db), rand(db, 3)
• iterate and collect objects in the database
• get the number of elements in the database length(db)
• add new objects to the end of the database (not all internal containers will support it)
  • push_item!(db, u) adds a single element u
  • append_items!(db, lst) adds a list of objects to the end of the database

struct MatrixDatabase{M<:AbstractMatrix} <: AbstractDatabase

MatrixDatabase(matrix::AbstractMatrix)

Wraps a matrix-like object matrix into a MatrixDatabase, i.e., each column of matrix is taken as one object of the database. It is a static, fixed-size database (no push_item!/append_items! support); use BlockMatrixDatabase or VectorDatabase when incremental growth is needed. Please see AbstractDatabase for general usage.

Examples

matrix = rand(Float32, 8, 100)  # 100 objects of dimension 8
db = MatrixDatabase(matrix)
db[1]        # the first object (a view of the first column)
length(db)   # 100

struct BlockMatrixDatabase{Dim,NumType,NumBits} <: AbstractDatabase

Stores objects of dimension Dim and element type NumType in a growable collection of dense matrix blocks, each block holding 2^NumBits columns/objects. It behaves like MatrixDatabase (each column is one object, backed by contiguous matrices for fast access) but additionally supports push_item!/append_items!, allocating a new block whenever the current one fills up. This makes it a good fit when you need to incrementally append large numbers of items without paying the cost of reallocating and copying a single growing matrix.

Fields

• blocks: the list of dense matrix blocks
• len: current number of stored objects (a Ref so it can be mutated in place)

Please see AbstractDatabase for general usage.

mutable struct MMapMatrixDatabase{Dim,NumType} <: AbstractDatabase

Stores objects of dimension Dim and element type NumType in a Dim × capacity matrix that is memory-mapped onto a file, i.e., it behaves like BlockMatrixDatabase (grows with push_item!/append_items!) but its storage lives on disk instead of in RAM. This makes it a good fit for datasets that do not fit comfortably in memory, or that must survive process restarts.

The physical capacity of the file (in number of columns) is preallocated in doubling blocks – as with BlockMatrixDatabase's 2^NumBits blocks – and only grows (extending and remapping the file) when push_item!/append_items! need more room than is currently mapped; it is not remapped on every single insertion. The logical length n (i.e. length(db)) is independent from the physical capacity and is persisted in a small header at the start of the file, so it survives closing and reopening the database.

Durability is opt-in: call flush

push_item!/append_items! update n in memory (so length(db) is correct right away within the same process) and write the new columns into the mapped data, but do not msync those bytes or persist/fsync the advanced n into the header – that is exactly what flush does, and it is the caller's responsibility to call it whenever it considers durability to matter (once per batch, on a timer, before a deliberate checkpoint, ...), not something either mutating function does on your behalf. close/the finalizer call flush once as a last-resort safety net, but garbage collection timing is not a guarantee, so it is not a substitute for calling flush deliberately: a process that pushes/appends and then crashes or is killed before an explicit flush (or a clean close) loses everything added since the last flush. What flush still guarantees when you do call it: n only ever advances on disk after the corresponding bytes are themselves durable, so a crash during a flush never leaves the header pointing at data that isn't there.

Please see AbstractDatabase for general usage.

Concurrency

Concurrent push_item!/append_items! calls from multiple threads on the same database are not safe without external synchronization (e.g. a lock); they race on n and on the growth/remap logic. flush is in the same category and for the same reason – it reads db.n/db.data, both of which a concurrent push_item!/append_items! mutates – so calling it from a different thread than the one doing the writing, without synchronization, is exactly as unsafe as two writers would be; it is not a read-only operation just because it doesn't add an object. A concurrent grow/remap (triggered by a writer) racing against a reader's getindex is safe in the sense that it will not segfault – the reader either sees the old, still-valid mapped array or the new one, since old mappings are only released once nothing references them – but it is still recommended to avoid mixing growth and reads across threads without synchronization, since a getindex racing a push_item! is not guaranteed to observe a consistent n/data pair.

Examples

db = MMapMatrixDatabase("/tmp/mydb.mmapdb", 8, Float32)  # 8-dimensional Float32 objects
push_item!(db, rand(Float32, 8))
length(db)  # 1
close(db)

db2 = MMapMatrixDatabase("/tmp/mydb.mmapdb")  # reopens, restoring Dim/NumType/length from the header
length(db2)  # 1
close(db2)

struct VectorDatabase{V} <: AbstractDatabase

Wraps a vector-like object vecs (e.g., a Vector of vectors, or any structure supporting getindex, setindex!, length, push!) into an AbstractDatabase, i.e., each element of vecs is one object of the database. Unlike MatrixDatabase, it can hold objects of any type (not just columns of a matrix) and supports growth via push_item!/append_items!.

Fields

• vecs: the underlying vector-like container of objects

Please see AbstractDatabase for general usage.

Examples

db = VectorDatabase([rand(Float32, 8) for _ in 1:100])  # 100 objects of dimension 8
db[1]         # the first object
length(db)    # 100

empty_db = VectorDatabase()  # an empty VectorDatabase{Vector{Float32}}
push_item!(empty_db, rand(Float32, 8))

struct SubDatabase{DBType<:AbstractDatabase,RType} <: AbstractDatabase

A lightweight, read-only view over a subset (or a reordering, or a resampling) of a parent database, without copying its objects. The i-th element of the view is parent[map[i]]. It is what view(db, map), db[list], and rand(db, n) return for any AbstractDatabase db.

Fields

• parent: the underlying database being viewed
• map: a collection of indices into parent; map[i] gives the parent index of the i-th element of the view

Please see AbstractDatabase for general usage.

Examples

db = MatrixDatabase(rand(Float32, 8, 100))
sub = view(db, [1, 3, 5])   # a SubDatabase with 3 objects
sub[1] == db[1]             # true
sub2 = db[[2, 4]]           # getindex with a list of indices also returns a SubDatabase

abstract type AbstractAdjList{T} end

Base type for adjacency-list backends used to store the neighbors of each node in a graph-based index. The type parameter T is the element type stored per neighbor (e.g., an integer id, or an IdDist pair combining an id with a distance).

Concrete subtypes provide different storage strategies with the same read/write API (neighbors, neighbors_length, add!):

• AdjList: growable Vector{Vector{T}}-backed adjacency list, indexed by contiguous integer node ids.
• AdjDict: Dict{T,Vector{T}}-backed adjacency list, useful when node ids are sparse or non-contiguous.
• StaticAdjList: frozen, CSR-like layout for fast read-only access once the graph stops growing.

struct AdjList{T} <: AbstractAdjList{T}

Growable adjacency-list representation of a graph, backed by a Vector{Vector{T}}. Node i's neighbors are stored in end_point[i]; nodes are addressed by contiguous integer indices (1:length(adj)). This is the usual mutable backend used while a graph-based index is being built or updated.

Fields

• end_point: vector of neighbor lists, one per node (end_point[i] holds the ids of node i's neighbors).
• glock: a ReentrantLock guarding mutation (resize!, add!) for thread-safety.

Examples

adj = AdjList(Int32, 10)   # preallocate for 10 nodes
add!(adj, 1, Int32[2, 3])  # node 1 is connected to nodes 2 and 3
neighbors(adj, 1)          # => Int32[2, 3]

struct AdjDict{T} <: AbstractAdjList{T}

Dict-of-vectors adjacency-list representation of a graph, backed by a Dict{T,Vector{T}}. Node i's neighbors are stored in end_point[i]. Unlike AdjList, node ids need not be contiguous integers starting at 1, making this backend useful for sparse or non-contiguous node id spaces.

Fields

• end_point: dictionary mapping a node id to its vector of neighbor ids.
• glock: a ReentrantLock guarding mutation (add!) for thread-safety.

Examples

adj = AdjDict(Int32, 0)
add!(adj, 1, Int32[2, 3])
neighbors(adj, 1)  # => Int32[2, 3]

struct StaticAdjList{T} <: AbstractAdjList{T}

Frozen, read-only adjacency-list representation of a graph, using a CSR-like (compressed sparse row) encoding for compactness and fast access. It is typically built once from a growable AdjList or AdjDict after the graph stops growing (see the conversion constructor StaticAdjList(adj::AbstractAdjList)).

Fields

• offset: cumulative neighbor counts; offset[i] is the index (in end_point) of the last neighbor of node i, so node i's neighbors occupy end_point[offset[i-1]+1:offset[i]] (with offset[0] implicitly 0).
• end_point: flat vector holding all neighbor ids, concatenated node by node.

Examples

adj = AdjList(Int32, 0)
add!(adj, [(1, Int32[2, 3]), (2, Int32[1])])
sadj = StaticAdjList(adj)  # freeze into a compact, read-only representation
neighbors(sadj, 1)         # => view of Int32[2, 3]

AbstractMetricQueue

Abstract base type for all metric result containers. Its two direct subtypes are AbstractKnnQueue (count-bounded: keeps the k closest items) and AbstractRadiusQueue (radius-bounded: keeps every item within a fixed distance threshold, however many that turns out to be). Both share the same underlying push_item!/nearest/frontier/IdDistView interface; only how "closest"/"kept" is bounded differs.

AbstractKnnQueue

Abstract base type for k-nearest-neighbor result containers. Concrete subtypes (KnnHeap and KnnSorted) accumulate (id, dist) pairs found during a search and keep only the k closest ones. They share a common interface built around push_item!, nearest, frontier, IdDistView, covradius, and reuse!; use knnqueue to construct one. See AbstractRadiusQueue for the radius-bounded sibling family.

AbstractRadiusQueue

Abstract base type for radius-bounded result containers (RadiusSorted and RadiusHeap): accept an (id, dist) pair iff dist <= radius, growing without any count limit (backed by plain growable Vectors, never a fixed-size or view-backed buffer). Unlike AbstractKnnQueue, maxlength always returns typemax(Int32) and maximum/covradius always return the fixed radius, since the covering radius is known in advance rather than discovered as the queue fills up. Construct one directly (e.g. RadiusSorted(radius)); they are not wired into the knnqueue(T, k::Int) capacity-based constructor since "k" has no meaning here.

KnnHeap{IDS<:AbstractVector{UInt32}, DSTS<:AbstractVector{Float32}} <: AbstractKnnQueue

A k-NN result container backed by a binary max-heap (ordered by DistOrder). The root of the heap always holds the current farthest item, so once the container is full a new candidate can be accepted or discarded in O(1) amortized time by comparing it against the root, and inserted in O(log k) time.

Fields

• ids::IDS: backing storage for the identifiers (UInt32).
• dists::DSTS: backing storage for the distances (Float32), parallel to ids.
• min_id::UInt32: the id of the closest item seen so far (tracked separately).
• min_dist::Float32: the distance of the closest item seen so far.
• len::Int32: number of active items currently stored.
• maxlen::Int32: maximum number of items to keep (the k of the k-nn search).

Use knnqueue to create one instead of calling the constructor directly.

Examples

res = knnqueue(KnnHeap, 3)  # k = 3
push_item!(res, 1, 0.5f0)
push_item!(res, 2, 0.1f0)
nearest(res)     # IdDist with the smallest distance seen so far
IdDistView(res)  # view of the active items

KnnSorted{IDS<:AbstractVector{UInt32}, DSTS<:AbstractVector{Float32}} <: AbstractKnnQueue

A k-NN result container that keeps its active items always sorted by distance (ascending, DistOrder), using a bounded binary-search + block-shift on each push. It trades a slightly higher insertion cost against KnnHeap for items that are always available in sorted order without an explicit call to sortitems!.

Fields

• ids::IDS: backing storage for the identifiers (UInt32).
• dists::DSTS: backing storage for the distances (Float32), parallel to ids.
• sp::Int32: start position (index) of the active range.
• ep::Int32: end position (index) of the active range.
• maxlen::Int32: maximum number of items to keep (the k of the k-nn search).

Invariant: ids[sp:ep] / dists[sp:ep] is always sorted in ascending order by distance. sort_last_item! is the sole function responsible for maintaining this.

Use knnqueue to create one instead of calling the constructor directly.

Examples

res = knnqueue(KnnSorted, 3)  # k = 3
push_item!(res, 1, 0.5f0)
push_item!(res, 2, 0.1f0)
nearest(res)     # closest item
IdDistView(res)  # lazy view of the active items, sorted by distance

RadiusSorted <: AbstractRadiusQueue

A radius-bounded result container that keeps its items always sorted by distance (ascending), using the same bounded binary-search + block-shift insertion as KnnSorted (sort_last_item!). Unlike KnnSorted, it has no count-based capacity: it accepts every (id, dist) pair with dist <= radius, growing its backing Vectors via push! as needed.

Fields

• ids::Vector{UInt32}: backing storage for the identifiers.
• dists::Vector{Float32}: backing storage for the distances, parallel to ids.
• radius::Float32: the fixed acceptance threshold.

Invariant: ids/dists are always sorted in ascending order by distance.

Examples

res = RadiusSorted(0.3f0)
push_item!(res, 1, 0.1f0)
push_item!(res, 2, 0.5f0)  # rejected, dist > radius
nearest(res)     # closest item
IdDistView(res)  # lazy view of the active items, sorted by distance

RadiusHeap <: AbstractRadiusQueue

A radius-bounded result container that trades RadiusSorted's "always sorted" invariant for a cheap O(1) insertion: every accepted item is simply appended, with no ordering maintained on each push (there is nothing to evict, so keeping a heap invariant up to date on every insert would buy nothing). Items are only sorted lazily, once, the first time they're read after a push, via heapify!/heapsort! (the same primitives KnnHeap uses).

Fields

• ids::Vector{UInt32}: backing storage for the identifiers.
• dists::Vector{Float32}: backing storage for the distances, parallel to ids.
• radius::Float32: the fixed acceptance threshold.
• sorted::Bool: whether ids/dists are currently known to be sorted (invalidated by every push_item!, restored by sortitems!).

Examples

res = RadiusHeap(0.3f0)
push_item!(res, 1, 0.1f0)
push_item!(res, 2, 0.5f0)  # rejected, dist > radius
nearest(res)     # forces a sort, then returns the closest item

BallKnn <: AbstractKnnQueue

Internal navigation queue for radius-bounded searches over a graph index (issue #67). It keeps every item within radius, growing without a count limit like an AbstractRadiusQueue, plus a reserve of at least kmin nearest items even when those fall outside the ball.

That reserve is what makes a graph search work at all. A greedy/beam search needs two things from its result container: something to start from (nearest) and a threshold that shrinks as the search improves (maximum, the k-th distance). A plain radius container gives neither when the query's neighborhood starts outside the ball: it rejects every candidate, stays empty – so nearest reads out of bounds, which is the segfault of #67 – and its maximum is the constant radius, turning the admission test into an absolute one, so a beam that starts outside the ball has no admissible child and dies on its first expansion. That second half is why guarding the emptiness alone is not a fix: it converts the crash into silently empty balls.

Here maximum returns max(radius, dists[capacity]): the k-th distance while the reserve is what bounds the queue, flattening at radius once the ball itself holds more than kmin items. So it shrinks exactly as a k-NN queue's does, and stops shrinking where further tightening would start excluding ball members.

maxlength reports that same capacity rather than typemax(Int32), which is what lets create_error_function's coverage block (length(r) == maxlength(r)) accept these queues instead of rejecting every configuration with InvalidSetupError – see the plan for radius-aware optimize_index! in #67.

The reserve is an implementation detail of navigation, never a result: callers copy out ballview (the prefix within radius), so nothing outside the ball is ever returned.

Fields

• ids::Vector{UInt32} / dists::Vector{Float32}: parallel storage, kept sorted by distance.
• radius::Float32: the ball being answered.
• kmin::Int32: minimum reserve kept for navigation.

Items within res.radius, sorted by distance – the actual result, without the navigation reserve.

knnqueue(::Type{T}, ids::AbstractVector{UInt32}, dists::AbstractVector{Float32}) where {T<:AbstractKnnQueue}

Creates a k-NN result queue of type T using ids and dists as its parallel backing storage.

knnqueue(::Type{T}, k::Int) where {T<:AbstractKnnQueue}

Creates a k-NN result queue of concrete type T (either KnnHeap or KnnSorted) with capacity k, allocating fresh backing vectors of k zeroed UInt32 ids and Float32 distances.

Examples

res = knnqueue(KnnSorted, 3)  # capacity k = 3, freshly allocated storage

knnqueue(::Type{T}, vec::SparseVector) where {T<:AbstractKnnQueue}

Creates a k-NN queue from a SparseVector by pushing all non-zero entries. The queue will automatically reorder the elements by distance.

knnqueue(ctx::SearchGraphContext{KnnType}, arg) -> AbstractKnnQueue

Creates a knn priority queue of type KnnType (the type parameter stored in ctx), using arg to initialize it (either an integer k or a preallocated vector), see knnqueue.

nearest(res::KnnHeap)

Returns the closest item (IdDist) seen so far in res.

nearest(res::KnnSorted)

Returns the closest item (IdDist) currently stored in res.

Closest item (IdDist) currently stored in res.

Closest item (IdDist) currently stored in res, sorting res first if needed.

Closest item (IdDist) currently stored in res.

frontier(res::KnnHeap)

Returns the farthest item currently stored in res (the heap root), i.e., the item that would be evicted next when a closer candidate is pushed.

frontier(res::KnnSorted)

Returns the farthest item (IdDist) currently stored in res, i.e., the item that would be evicted next when a closer candidate is pushed.

Farthest item (IdDist) currently stored in res.

Farthest item (IdDist) currently stored in res, sorting res first if needed.

Farthest item (IdDist) currently stored in res, reserve included.

covradius(res::AbstractKnnQueue)::Float32

The covering radius of the result set, i.e., the distance to the farthest item currently kept in res. While res has not yet reached its maximum capacity (maxlength) it returns typemax(Float32), since any candidate should still be accepted.

reuse!(res::KnnHeap, maxlen=length(res.ids))

Resets res to a fresh initial state (empty, with capacity maxlen), reusing its existing memory buffers instead of allocating a new result set.

reuse!(res::KnnHeap, ids, dists, maxlen=length(ids))

Like reuse!(res, maxlen), but also replaces the backing storage of res with ids and dists before resetting its state.

reuse!(res::KnnSorted, maxlen=length(res.ids))

Resets res to a fresh initial state (empty, with capacity maxlen), reusing its existing memory buffers instead of allocating a new result set.

reuse!(res::KnnSorted, ids, dists, maxlen=length(ids))

Like reuse!(res, maxlen), but also replaces the backing storage of res with ids and dists before resetting its state.

reuse!(res::RadiusSorted, radius::Real=res.radius)

Resets res to a fresh, empty state with acceptance threshold radius, truncating its backing storage (unlike KnnSorted.reuse!, which keeps a fixed-size buffer, RadiusSorted must actually free the grown storage to avoid leaking memory from previously-reused, larger result sets).

reuse!(res::RadiusHeap, radius::Real=res.radius)

Resets res to a fresh, empty state with acceptance threshold radius, truncating its backing storage to avoid leaking memory from previously-reused, larger result sets.

reuse!(res::BallKnn, radius::Real=res.radius)

Resets res to a fresh, empty state answering radius, truncating its backing storage (it grows with the ball, like RadiusSorted).

reuse!(B::AbstractVector{UInt64}, n::Integer)

Resets (zeroes out) the bit-vector B so that it can be reused to track up to n visited vertices, resizing it if needed.

reuse!(v::Set{UInt32}, n::Integer)

Empties the set v so that it can be reused to track visited vertices, pre-sizing it for a dataset of n elements.

sortitems!(res::KnnHeap)

Sort items and returns an IdDistView of the active items; this operation destroys the internal heap structure. It is possible to restore the heap structure without calling heapify! by applying reverse! on the returned view.

sortitems!(res::KnnSorted)

For KnnSorted items are always sorted; returns the IdDistView view immediately.

For RadiusSorted items are always sorted; returns the IdDistView view immediately.

sortitems!(res::RadiusHeap)

Sorts res's items by distance (ascending) if they aren't already known to be sorted, and returns the resulting IdDistView view.

For BallKnn items are always sorted; returns the IdDistView view immediately.

sort_last_item!(ids, dists, sp, ep)

Inserts the item at position ep into its correct sorted place within ids[sp:ep] / dists[sp:ep]. Relies on the invariant that ids[sp:ep-1] / dists[sp:ep-1] is already sorted in ascending order by distance.

The algorithm:

1. Early exit: if dists[ep] >= dists[ep-1] the array is already sorted.
2. Binary search on dists[sp:ep-1] to find the insertion point lo (first index where dists[lo] > item_dist).
3. Block shift via copyto! to move ids[lo:ep-1] → ids[lo+1:ep] (and likewise for dists), which the compiler/CPU can vectorize as a single memmove.
4. Write item_id/item_dist into position lo.

maxlength(res::KnnHeap)

The maximum allowed cardinality (the k of knn)

maxlength(res::KnnSorted)

The maximum allowed cardinality (the k of knnSorted)

isheap(lt::Function, X, i, n)

Checks whether the subtree rooted at position i satisfies the binary-heap property with respect to lt up to n items (only the immediate children of i are checked).

isheap(lt::Function, X, n)

Checks whether X[1:n] fully satisfy the binary-heap property with respect to lt.

heapsort!(lt::Function, swap::Function, X, n)

Sorts X[1:n] in place using the heap it already contains (built with heapify!), repeatedly moving the root to the end and restoring the heap on the remaining prefix.

heapfix_down!(lt::Function, swap::Function, X, n)

Restores the heap property by moving the item at the root (position 1) downwards while it violates lt with respect to its children, considering only the first n elements of X.

pop_min!(res::KnnSorted)

Removes and returns the closest item from res, shrinking its active range from the start.

pop_max!(res::KnnHeap)

Removes and returns the farthest item (the heap root) from res, shrinking its length by one.

pop_max!(res::KnnSorted)

Removes and returns the farthest item from res, shrinking its active range from the end.

IdDist(id, dist)

A lightweight pair (id::UInt32, dist::Float32) representing a single search result: the identifier of an object together with its distance to the query. It is the basic item type stored in KnnHeap and KnnSorted result containers.

Examples

item = IdDist(3, 0.25f0)
item.id    # 3
item.dist  # 0.25f0

IdOrder

Singleton Ordering (from Base.Order) that compares items by id in ascending order. Pass it to the heap/sort routines when the desired order is by object identifier instead of by distance.

DistOrder

Singleton Ordering (from Base.Order) that compares items by dist in ascending order (nearest first). This is the ordering used internally by KnnHeap and KnnSorted to keep the closest neighbors found so far.

RevDistOrder

Singleton Ordering (from Base.Order) that compares items by dist in descending order (farthest first).

IdView{ARR}

A zero-copy view over the identifier column of a collection. Indexing returns UInt32.

Supported wrappable types: AbstractVector{UInt32}, AbstractMatrix{UInt32}, AbstractVector{IdDist}, AbstractMatrix{IdDist}, KnnSorted, KnnHeap.

DistView{ARR}

A zero-copy view over the distance column of a collection. Indexing returns Float32.

Supported wrappable types: AbstractVector{Float32}, AbstractMatrix{Float32}, AbstractVector{IdDist}, AbstractMatrix{IdDist}, KnnSorted, KnnHeap.

IdDistView(res::AbstractMetricQueue)
IdDistView(ids, dists)
IdDistView(ids, dists, sp, ep)

A lazy, zero-copy view over a range of parallel ids/dists arrays or a metric result queue that presents elements as a sequence of IdDist pairs without allocating.

knn_matrices(mat::SparseMatrixCSC, k::Integer) -> (ids, dists)

Converts a SparseMatrixCSC into a batch result representation (dense matrices ids and dists of size (k, m)). The elements in each column are reordered by distance.

ScalarQuant

Uniform scalar quantization of vector databases at 2, 4 and 8 bits per coordinate, in two families that differ in where the quantization range comes from:

• Global (SQgu2, SQgu4, SQgu8, and GlobalQuantDatabase): a single min/scale pair shared by the whole database, estimated once from a sample of all coordinate values. Codes of different vectors are directly comparable, so the distances consume them with SIMD and nothing is stored per vector.
• Per-vector (SQu2, SQu4, SQu8): every stored vector carries its own min/scale (SQMinC), taken from that vector's own extrema. Nothing is ever clipped, and a vector living on a different scale than the rest is quantized as faithfully as any other; the price is 8 bytes per vector and a distance that must fold both vectors' parameters in (see SQu8's dotu8).

Choosing a family

Use a global quantizer when what you will quantize – the database, the queries, and whatever arrives after the index is built – comes from the same distribution as the sample the range was estimated from. That is the common case for normalized embeddings out of a single model, and it is the cheaper family at query time.

Use a per-vector quantizer when coordinates may move outside what that sample showed: several embedding models or preprocessing pipelines mixed into one database, unnormalized data, scales that drift as the collection grows. A global range is an assumption about the whole database, and a vector that breaks it saturates against the ends of the range, losing precisely the large coordinates distances depend on. A per-vector range cannot be broken, because it is derived from the vector itself.

The trade has a second edge. A per-vector range is set by that vector's own extrema, so one outlying coordinate stretches the range and costs resolution for every other coordinate of that vector. Per-vector adapts to scale differences between vectors; it does not help against a heavy-tailed coordinate distribution, which costs resolution in both families.

Choosing the range of a global quantizer

The range is a real parameter, and its best value depends on the code width, not only on the data. Clipping at ±L (in units of the coordinate standard deviation) trades two errors against each other: the step is 2L / levels, so a wider range coarsens every code, while a narrower one saturates more mass. More levels make the step cheap, so the optimal L grows with the width. For a Gaussian marginal, minimizing quantization error over sqglobalscale's own reconstruction grid gives

Those factors are specific to this grid, and at 2 bits that matters. sqglobalscale places levels + 1 reconstruction points spanning [min, max] inclusive, 2L / levels apart – not the 2^bits cells of width 2L / 2^bits that textbook tables assume. At 2 bits the two differ by a third in step size (2L/3 against 2L/4), which moves the optimum from the textbook 2.0σ to 1.50σ; at 8 bits they agree to within 0.4% (255 points against 256 cells), which is why the difference is easy to miss.

The default policy here (quant=[0.025, 0.975], i.e. ±1.96σ under a Gaussian) is therefore too wide for SQgu2 and too tight for SQgu8. Measured against the benchmarks' own gold standards on three ANN datasets (600K-3M vectors, 384 dimensions, coordinate kurtosis 3.04-3.05, so Gaussian to measurement precision), moving from the default to the optimal range gained 0.033 to 0.057 of recall@10 at 2 bits and 0.005 to 0.010 at 4 bits; at 8 bits, on five datasets, the same fix was worth 0.027 to 0.079.

Three practical notes on estimating it:

• Prefer passing minmax as an interior quantile times a width-dependent factor over asking for an extreme quantile directly. The default sample holds sqrt(length(X)) values (~15K for a 600K x 384 database), which puts the 8-bit optimum's 99.99th percentile beyond anything the sample can resolve, while the 98th is stable.
• Anchor the range on the median, not on the origin or on the quantile interval's midpoint, and widen each side by its own distance to the median. All three agree on a symmetric centered marginal, and each of the other two breaks on a different shape: scaling both quantiles by one factor displaces a shifted marginal as it widens it (measured at 1.3-1.4x the error of the best range), while scaling about the midpoint drags min below zero on one-signed data such as ReLU outputs, spending levels where there is no data (2.6x the error, -0.046 of recall at 4 bits).
• Never take the range from the extrema. One outlier fixes it for the whole database and the codes collapse onto the middle: over the same datasets, min/max cost 0.15 at 2 bits where the extremes sat at 5.9σ, and 0.67 where a single vector pushed them to 11.7σ. It is also not reproducible, since the sample maximum grows like σ sqrt(2 ln n).
• The factors above assume a near-Gaussian marginal, which a random rotation upstream guarantees and ordinary text embeddings satisfy. Under heavier tails the optimum moves out fast – near 7σ at 8 bits for a Laplace marginal – so when the data has not been Gaussianized, pick L by minimizing quantization error over the sample rather than trusting the table. That search costs milliseconds and tracked the recall optimum closely here, though at 2 bits it lands slightly wide: recall peaked a little tighter than the error did.

SQMinC(min::Float32, c::Float32)

Internal helper struct that stores the per-vector dequantization parameters used by the scalar quantization schemes in ScalarQuant (i.e., SQu2, SQu4, SQu8). Given a quantized (integer) coordinate q, the corresponding approximate original value is recovered as q * c + min.

SQVec{B,VEC<:AbstractVector{UInt8}}

SQVec{B}(v::AbstractVector)
SQVec{B}(E::SQMinC, V::AbstractVector{UInt8})
SQVec{B}(E::SQMinC, V::AbstractVector{UInt8}, Sa, Saa)

A single vector quantized to B bits per coordinate (2, 4 or 8): the packed codes V (codesperbyte(B) coordinates to a byte, low bits first), the affine dequantization parameters E (coordinate i is code * E.c + E.min), and the two code sums Sa = Σ codes and Saa = Σ codes² that let every distance in this module be computed from one integer pass over the codes (see the note above codesums in codes.jl). Indexing (qvec[i]) dequantizes coordinate i to a Float32.

It is the element type of every quantized database here, in both families: a globally quantized vector is a per-vector one whose E happens to be shared with the rest of its database. SQu8Vec, SQu4Vec and SQu2Vec are aliases for SQVec{8}, SQVec{4} and SQVec{2}.

The first constructor quantizes v on its own extrema (quantvector!). length(v) must be a multiple of codesperbyte(B) (2 at 4 bits, 4 at 2 bits), or an ArgumentError is thrown: pad v if needed, and then pad any plain vector later compared against the result the same way, since the mixed distances index it positionally. The other two take stored codes back as they are, recomputing the sums from the codes when they are not given.

quantvector!(::Val{B}, vout::AbstractVector{UInt8}, v::AbstractVector; eps=1f-6) -> SQMinC

Quantizes v into vout on its own extrema, the per-vector family's rule: the whole range [min, max] maps onto the codes 0:levels(B), so nothing is clipped and a vector on a different scale from the rest is encoded as faithfully as any other. Returns the SQMinC that dequantizes it; eps keeps a constant vector's range from collapsing.

QuantDatabase{B,P,DB<:AbstractDatabase} <: AbstractDatabase

QuantDatabase{B}(E, Q; dim=nothing, Sa=nothing, Saa=nothing)

An AbstractDatabase of vectors quantized to B bits per coordinate (2, 4 or 8): the packed codes live in any database of UInt8 vectors, Q::DB, next to what dequantizes them, E::P, which is either one SQMinC per vector (P a Vector{SQMinC}: the per-vector family, SQu8Database and its siblings) or a single one shared by the whole database (P == SQMinC: the global family, GlobalQuantDatabase). Indexing yields an SQVec, so every distance in this module applies to both families alike. See the module docstring for how to choose between them, and the aliases above for the constructors that quantize a matrix.

Storage

Q decides what the database can do, exactly as it does for unquantized vectors:

• MatrixDatabase, the default of every constructor that quantizes a matrix: static and fastest;
• BlockMatrixDatabase: grows a block at a time. push_item!/append_items! quantize each incoming vector with the database's own parameters and push its codes, so a SearchGraph can be built over a quantized database one item at a time;
• MMapMatrixDatabase: grows too, on disk, and outlives the process. Reopen the file and hand it back to the constructor with the parameters to get the same database;
• a VectorDatabase of Vector{UInt8}, or anything else indexable: whatever a custom store needs.

A constructor that quantizes a matrix takes storage, a function from the Matrix{UInt8} of codes to the database that will hold them (MatrixDatabase, BlockMatrixDatabase, or a closure that fills an mmap file). The constructor above takes codes back as they are – a matrix, wrapped in a MatrixDatabase, or any database – and an empty database of the right row size is how a growable one starts:

julia> using SimilaritySearch, SimilaritySearch.ScalarQuant

julia> X = randn(Float32, 64, 1000);

julia> db = GlobalQuantDatabase(8, BlockMatrixDatabase(64, UInt8), extrema(X));   # empty

julia> append_items!(db, MatrixDatabase(X)); length(db)
1000

julia> db == GlobalQuantDatabase(8, X; minmax=extrema(X))      # same codes, byte for byte

Growth is serial, like every other database here: concurrent push_item!s need a lock.

Fields

• E, Q: the two that make a database, and the two that have to be persisted;
• dim: the dimension of the vectors, a multiple of the coordinates packed per byte (2 at 4 bits, 4 at 2 bits). A dimension that does not fill its last byte is rejected: pad the vectors, and then pad every plain vector compared against the database the same way, since the mixed distances index it positionally;
• Sa, Saa: per vector, Σ codes and Σ codes², which every distance reads (see the note above codesums in codes.jl). They are sums of the codes, measured when a vector is quantized: sums of the original Float32 vector, though more accurate, lost 0.01 to 0.41 of recall@10 on the SISAP 2025 benchmarks, because quantization rescales each vector slightly and only the code sums carry that rescaling (issue #87). Being derived from the codes they are recomputed on reconstruction unless passed in, which skips one pass over the codes when an mmap-backed database is reopened.

Arguments

• E: a Vector{SQMinC} with one entry per stored vector, or one SQMinC for all
• Q: the codes, as an AbstractMatrix{UInt8} (one column per vector) or an AbstractDatabase of UInt8 vectors

Keyword Arguments

• dim: the vector dimension; read off Q when not given, which an empty VectorDatabase cannot provide
• Sa, Saa: the code sums, when the caller kept them; recomputed from Q otherwise

quantize(db::QuantDatabase, v::AbstractVector) -> SQVec

Quantizes v the way db's vectors are: with db's shared parameters in the global family, so the result is comparable with what it stores; on v's own extrema in the per-vector one, where db only fixes the dimension. This is what push_item! stores, and what a query must go through to be compared as codes against codes (a Float32 query needs no quantization: the mixed distances take it as it is).

Whether every stored vector shares one min/scale pair (the global family).

The code width of q, in bits.

The code width of the stored vectors, in bits.

SqL2()

The squared Euclidean distance between two quantized vectors (SQVec), or between a quantized vector and a plain vector, avoiding the square root computed by L2.

Between two quantized vectors it never dequantizes: with equal scales it is one exact integer pass over the codes, and otherwise the expansion of Σ (a·cA + mA - b·cB - mB)² into one integer dot product plus the per-vector sums. Against a plain Float32 vector it unpacks the codes to floats with SIMD and accumulates (â - b)².

L2()

The Euclidean ($L_2$) distance between two quantized vectors (SQVec), or between a quantized vector and a plain vector: the square root of SqL2.

L1()

The Manhattan ($L_1$) distance between two quantized vectors (SQVec), or between a quantized vector and a plain one. evaluate dequantizes coordinate by coordinate and accumulates the absolute value of the differences.

NormCosine()

Similar to Dist.NormCosine but for quantized vectors (SQVec): it assumes that the original (pre-quantization) vectors were already normalized, and therefore reduces to one minus the dot product,

\[1 - \sum_i {u_i v_i}\]

Between two quantized vectors the dot product comes from the integer expansion behind Cosine; against a plain vector it is accumulated coordinate by coordinate. When the data may have drifted off the unit sphere through quantization, Cosine corrects for it and ranks better at every width.

Cosine()

Cosine dissimilarity (1 - cos) between two quantized vectors, computed from their codes: the dot product of the dequantized vectors divided by their dequantized norms.

Both halves of that need per-vector quantities the codes alone do not carry, and both are already stored by every SQVec (Sa = Σ codes, Saa = Σ codes²):

• the dot product expands to cA·cB·Σab + cA·mB·Σa + cB·mA·Σb + n·mA·mB, so dropping everything but Σab – as a raw-code dot product does – only preserves order when the offsets are zero. On centered data (any ordinary embedding) it does not: measured over 20k unit-norm vectors in dim 128, ranking by the raw code dot product gave recall@10 of 0.005 against exact cosine, while the full expansion gave 0.97 (issue #77);
• the norms, ‖â‖² = c²·Saa + 2·c·m·Sa + n·m², correct the drift quantization leaves in a vector that was normalized before being quantized. Against a plain vector the query's norm is computed on the spot. That matters more the fewer bits there are: on non-negative data, recall@10 went 0.9685 -> 0.979 at 8 bits, 0.590 -> 0.666 at 4 bits, and 0.111 -> 0.126 at 2 bits.

Both must come from the codes, not from the original vector: on the SISAP 2025 benchmarks, norms measured from the Float32 vector instead lost 0.01-0.05 of recall@10 and sums of the original vector in the dot product lost 0.01-0.41, because quantization rescales each vector slightly and the code sums carry exactly that rescaling (issue #87).

SQu2

Per-vector (per-column) 2-bit scalar quantization: quantize stores four 2-bit codes packed per UInt8, each column keeping its own min/scale computed from its extrema. Accessed as ScalarQuant.SQu2.quantize, etc.

The vector type, the database and the distances are the module-wide SQVec, QuantDatabase and SqL2/L2/L1/ NormCosine; the names here are aliases kept for the per-width API.

quantize(X::AbstractMatrix; storage=MatrixDatabase)

Scalar-quantizes each column (vector) of X to 2 bits per coordinate, four 2-bit codes packed per UInt8. This reduces the memory footprint of a database of vectors by roughly a factor of 16 with respect to Float32 at the cost of precision. Each column is quantized independently using its own minimum and scale factor, computed from the extrema of the column so that its whole range [min, max] maps onto the codes; size(X, 1) must be a multiple of 4.

Returns an SQu2Database, an AbstractDatabase whose db[i] is an SQu2Vec that can be indexed to retrieve dequantized Float32 coordinates; storage chooses the database that holds the codes (see QuantDatabase).

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu2.quantize(X);

julia> db[1][1]  # dequantized approximation of X[1, 1]

quantize(db::SQu2Database, v::AbstractVector)

Quantizes a single vector v to 2 bits per coordinate, the same way as the vectors already stored in db, returning an SQu2Vec. Each vector's own min/scale comes from its own extrema, so this does not read db's parameters; db only fixes the (padded) dimension v must have. It is what push_item! stores, and how a query is quantized to be compared as codes against codes with L1/L2/SqL2/NormCosine.

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu2.quantize(X);

julia> qv = ScalarQuant.SQu2.quantize(db, rand(Float32, 8));  # quantized the same way as db's vectors

SQu2Database(X::AbstractMatrix; storage=MatrixDatabase)
SQu2Database(E::AbstractVector{SQMinC}, Q; dim=nothing, Sa=nothing, Saa=nothing)

The per-vector 2-bit QuantDatabase: four 2-bit codes packed per UInt8, each stored vector carrying its own min/scale pair (E[i]) computed from that vector's own extrema. Indexing yields an SQu2Vec, which the distances consume without dequantizing.

The first constructor quantizes X (it is what quantize calls) into the storage storage builds from the matrix of codes. The second takes the two fields back as they are, quantizing nothing – that is the one to use after reading E/Q from storage, and, with an empty growable Q, the one that starts a database push_item! can grow: see QuantDatabase for the storage choices and the growth interface. The two must agree: exactly one SQMinC per stored vector.

SQu4

Per-vector (per-column) 4-bit scalar quantization: quantize stores two 4-bit codes packed per UInt8, each column keeping its own min/scale computed from its extrema. Accessed as ScalarQuant.SQu4.quantize, etc.

The vector type, the database and the distances are the module-wide SQVec, QuantDatabase and SqL2/L2/L1/ NormCosine; the names here are aliases kept for the per-width API.

quantize(X::AbstractMatrix; storage=MatrixDatabase)

Scalar-quantizes each column (vector) of X to 4 bits per coordinate, two 4-bit codes packed per UInt8. This reduces the memory footprint of a database of vectors by roughly a factor of 8 with respect to Float32 at the cost of precision. Each column is quantized independently using its own minimum and scale factor, computed from the extrema of the column so that its whole range [min, max] maps onto the codes; size(X, 1) must be a multiple of 2.

Returns an SQu4Database, an AbstractDatabase whose db[i] is an SQu4Vec that can be indexed to retrieve dequantized Float32 coordinates; storage chooses the database that holds the codes (see QuantDatabase).

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu4.quantize(X);

julia> db[1][1]  # dequantized approximation of X[1, 1]

quantize(db::SQu4Database, v::AbstractVector)

Quantizes a single vector v to 4 bits per coordinate, the same way as the vectors already stored in db, returning an SQu4Vec. Each vector's own min/scale comes from its own extrema, so this does not read db's parameters; db only fixes the (padded) dimension v must have. It is what push_item! stores, and how a query is quantized to be compared as codes against codes with L1/L2/SqL2/NormCosine.

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu4.quantize(X);

julia> qv = ScalarQuant.SQu4.quantize(db, rand(Float32, 8));  # quantized the same way as db's vectors

SQu4Database(X::AbstractMatrix; storage=MatrixDatabase)
SQu4Database(E::AbstractVector{SQMinC}, Q; dim=nothing, Sa=nothing, Saa=nothing)

The per-vector 4-bit QuantDatabase: two 4-bit codes packed per UInt8, each stored vector carrying its own min/scale pair (E[i]) computed from that vector's own extrema. Indexing yields an SQu4Vec, which the distances consume without dequantizing.

The first constructor quantizes X (it is what quantize calls) into the storage storage builds from the matrix of codes. The second takes the two fields back as they are, quantizing nothing – that is the one to use after reading E/Q from storage, and, with an empty growable Q, the one that starts a database push_item! can grow: see QuantDatabase for the storage choices and the growth interface. The two must agree: exactly one SQMinC per stored vector.

SQu8

Per-vector (per-column) 8-bit scalar quantization: quantize stores one UInt8 code per coordinate, each column keeping its own min/scale computed from its extrema. Accessed as ScalarQuant.SQu8.quantize, etc. See also SQgu8 for a variant that shares a single pair of quantization parameters across all columns.

The vector type, the database and the distances are the module-wide SQVec, QuantDatabase and SqL2/L2/L1/ NormCosine; the names here are aliases kept for the per-width API.

quantize(X::AbstractMatrix; storage=MatrixDatabase)

Scalar-quantizes each column (vector) of X to 8 bits per coordinate, one UInt8 code per coordinate. This reduces the memory footprint of a database of vectors by roughly a factor of 4 with respect to Float32 at the cost of precision. Each column is quantized independently using its own minimum and scale factor, computed from the extrema of the column so that its whole range [min, max] maps onto the codes.

Returns an SQu8Database, an AbstractDatabase whose db[i] is an SQu8Vec that can be indexed to retrieve dequantized Float32 coordinates; storage chooses the database that holds the codes (see QuantDatabase).

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu8.quantize(X);

julia> db[1][1]  # dequantized approximation of X[1, 1]

quantize(db::SQu8Database, v::AbstractVector)

Quantizes a single vector v to 8 bits per coordinate, the same way as the vectors already stored in db, returning an SQu8Vec. Each vector's own min/scale comes from its own extrema, so this does not read db's parameters; db only fixes the (padded) dimension v must have. It is what push_item! stores, and how a query is quantized to be compared as codes against codes with L1/L2/SqL2/NormCosine.

Examples

julia> using SimilaritySearch

julia> X = rand(Float32, 8, 1000);

julia> db = ScalarQuant.SQu8.quantize(X);

julia> qv = ScalarQuant.SQu8.quantize(db, rand(Float32, 8));  # quantized the same way as db's vectors

SQu8Database(X::AbstractMatrix; storage=MatrixDatabase)
SQu8Database(E::AbstractVector{SQMinC}, Q; dim=nothing, Sa=nothing, Saa=nothing)

The per-vector 8-bit QuantDatabase: one UInt8 code per coordinate, each stored vector carrying its own min/scale pair (E[i]) computed from that vector's own extrema. Indexing yields an SQu8Vec, which the distances consume without dequantizing.

The first constructor quantizes X (it is what quantize calls) into the storage storage builds from the matrix of codes. The second takes the two fields back as they are, quantizing nothing – that is the one to use after reading E/Q from storage, and, with an empty growable Q, the one that starts a database push_item! can grow: see QuantDatabase for the storage choices and the growth interface. The two must agree: exactly one SQMinC per stored vector.

sqglobalscale(levels::Integer, min, max)

The scale factor shared by every global quantizer (SQgu2/SQgu4/SQgu8): maps the range [min, max] onto the levels + 1 integer codes 0:levels as code = round(clamp((x - min) * c, 0, levels)). The 1e-6 in the denominator keeps a degenerate (min == max) range from producing Inf.

Arguments

• levels: the largest code the target width can hold (3, 15 or 255)
• min, max: the global value range being mapped

sqautorange(V, levels; samplesize=0, factors=0.30f0:0.05f0:3.0f0, passes=3)

Picks the (min, max) a global quantizer of levels + 1 codes should use for V, by minimizing sqdistortion over a sample of V itself. Returns a (Float32, Float32) pair, ready for minmax.

The search runs over each side separately: the range is anchored at the median and each end is placed at its own multiple of that side's distance to the [0.02, 0.98] quantiles, (min, max) = (med - a(med - q02), med + b(q98 - med)), with a and b found by coordinate descent over factors. Three properties come out of that parametrization, and all three were measured to matter: