API, core

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 and prepares the query for the mixed kernels: an SQQuery of the encoder's width, with the sums and the integer image the factored distances take (issue #110). It is still an AbstractVector{Float32}, the rotated query, for whatever reads the coordinates.

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.

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

AbstractSearchIndex

The supertype of every index in this package. An index answers a k nearest neighbor query or a radius query over a database, under a distance function.

Three functions give access to what an index is made of: database returns the objects it indexes, distance returns the distance function it uses, and length returns how many objects it holds. Queries go through search for one query and searchbatch for many. Indexes that accept new objects implement push_item! and append_items!.

The concrete types are ExhaustiveSearch, ParallelExhaustiveSearch, SearchGraph, AsymmetricSearchGraph and the inverted files of the InvertedFiles submodule.

InsertionSource(dist, db, items, offset)

What the insertion loops query the graph with, when that is not the database itself: object i is encodequery(dist, items[i - offset]) when it was just appended (its raw form, prepared once for the query side of dist), and db[i] otherwise (what the database stores). It is how an AsymmetricSearchGraph inserts raw objects into a graph over their transformed storage; a SearchGraph always queries with the database. Indexing only; the loops never iterate it, and each object is read once, so the preparation runs once per inserted item.

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. It is both an input and an output: what the caller marked is masked (rebuild's selfid, the optimizer's clusters), and what the search evaluated stays marked (allknn skips the hints already covered). Below SMALLINDEX items the search scans everything through enqueue_item!, so the scan keeps the same contract, members included (issue #125).

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

allknn!(index::AbstractSearchIndex, ctx::AbstractContext, ids, dists; sort::Bool=true, progress=nothing) -> (ids, dists)

In-place variant of allknn that receives preallocated (k, n) matrices as output, where n == length(index). Useful to reuse memory across calls or to resume/replace previously computed results.

Arguments

• index: the index
• ctx: the index's context (caches, hyperparameters, logger, etc)
• ids: an output (k, n) matrix of UInt32, n == length(index)
• dists: an output (k, n) matrix of Float32, parallel to ids

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

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 – and is raised to NEARDUP_NUMERICAL_ZERO, since two identical objects often do not evaluate to exactly 0f0 and a literal zero would collapse only the pairs that happened to round there. 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; exponent=1, maxdeviation=1, spreadfloor=1f-2) -> Float64
matcherror(golddist, res, err::MaxMatchError) -> Float64

Per-query MatchError (see MaxMatchError): the distances actually returned in res against the exact gold distances golddist, rank by rank, each position's excess measured in units of the gold neighborhood's own spread. For k' = length(golddist) gold distances d*_1 ≤ … ≤ d*_k' and the r returned distances d_1 ≤ … ≤ d_r:

spread      = d*_k' − min(d*_1, d_1) + spreadfloor + ε
deviation_i = min(max(0, d_i − d*_i) / spread, maxdeviation)   for i ≤ r
deviation_i = maxdeviation                                     for i > r   (a missing position)
matcherror  = mean(deviation_i ^ exponent  for i in 1:k')

• exponent: 1 averages the deviations (an MAE), 2 squares them first, which forgives small ones and amplifies large ones.
• maxdeviation: the most one position can cost, and what a missing position costs: a returned neighbor farther than maxdeviation spreads beyond its gold counterpart is as bad as no neighbor at all. The score is therefore in [0, maxdeviation ^ exponent], which is what keeps its mean over queries meaningful: measured on SISAP 2025 ccnews, without this cap ten queries whose gold neighbors were all exact duplicates at distance 0 (spread 0, the search returning items at distance 1.4, 143 per position) made 85% of the mean over 10,500 queries, and the mean moved by its own size from one tuning run to the next.
• spreadfloor: added to the spread so a gold neighborhood of tied distances (routine on real data with near-duplicates) does not divide by ≈ε; pick it on the scale of the distance (1f-2 suits a cosine-family distance in [0, 2]; Hamming over bits wants about 1f0).

macromatcherror is its mean over the queries, and the third form takes the three parameters from a MaxMatchError.

matcherror(golddist::AbstractVector{Float32}, res::BallKnn; exponent=1, maxdeviation=1, spreadfloor=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 maxdeviation, 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 exponent, maxdeviation and spreadfloor 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; exponent=1, maxdeviation=1, spreadfloor=1f-2) -> Float64
macromatcherror(golddists, reslist, err::MaxMatchError) -> 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 (the second form 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, maxdeviation ^ exponent the worst.

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)          # exponent 1, maxdeviation 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; exponent=2), or a user's.

perqueryscores(recallscore, goldI, resI)                       # what macrorecall averages
perqueryscores(matcherror, 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.

beginbatch(lev::Levenshtein)

A copy owning private scratch buffers, for use inside a single @BATCHES batch. See Levenshtein and beginbatch.

beginbatch(dl::DamerauLevenshtein)

A copy owning private scratch buffers, for use inside a single @BATCHES batch. See Levenshtein and beginbatch.

beginbatch(ctx::AbstractContext, id::Integer) -> ctx
beginbatch(dist::PreMetric) -> dist

Announces that a @BATCHES batch is starting, and returns whatever that batch should use in place of the object handed in. Call it once per batch, in @BEGINBATCH, and use only the returned value inside that batch:

@BEGINBATCH
    bctx = beginbatch(ctx, @batchid())
    bdist = beginbatch(distance(index))

The point is that a batch is single-tasked: whatever it gets back is its own for the duration, so it needs no synchronization of any kind – no lock, no Threads.threadid() assumption, and therefore no dependence on which @BATCHES scheduler is in play.

• For a context, the default is what every call site used to write by hand (@set ctx.batchid = id): the batch id is what per-batch caches index by (getvstate/getbeam/...). A context that keeps richer per-batch state can specialize this to refresh it instead of indexing it.
• For a distance, the default is to return it unchanged, which is right for the vast majority: a distance without mutable state is already safe to share. One that keeps scratch buffers (Dist.Seqs.Levenshtein, Dist.Seqs.DamerauLevenshtein) returns a copy owning private buffers.

Total distance evaluations across all batch slots (1-arg: lifetime; 2-arg: diffed against snapshot, see distance_stats).

distance_stats(ctx::AbstractContext) -> (; min, mean, max)
distance_stats(ctx::AbstractContext, snapshot::Vector{Int}) -> (; min, mean, max)

Min/mean/max distance evaluations across ctx's active batch slots, at batch granularity (not query granularity). The 1-arg form reads ctx.costdists as-is: since it's never reset, this is a lifetime statistic (since ctx was created). The 2-arg form measures a single operation instead: pass a snapshot = copy(ctx.costdists) taken before that operation, and this diffs the raw vectors (ctx.costdists .- snapshot) before computing stats on the result – not the other way around. Diffing precomputed stats instead is mathematically wrong for min/max (only mean/sum commute with subtraction) and would also break "active slot" detection, since a slot's raw value is cumulative garbage from every prior call – only the delta reliably reflects whether that slot was touched during the snapshot window.

A slot adds up every query its batch ran, so these are per-query figures only when each batch held one query. For a per-query cost, take the difference of ctx.costdists[ctx.batchid] around each query inside the batch, as optimize_index! does (issue #128).

Note: reads ctx.costdists with no synchronization – only call this once every @BATCHES region writing into ctx has already joined (i.e. from sequential code).

Total block evaluations across all batch slots (1-arg: lifetime; 2-arg: diffed against snapshot, see block_stats).

Block-evaluations counterpart of distance_stats (1-arg or 2-arg form).

set_page_spread!(on::Bool)

Whether large stores are written by all threads (true, the default since 1.6.5) or by the calling one (false, the behavior up to 1.6.4).

With true:

• bulk append_items! into a BlockMatrixDatabase or a quantized database fills the new items in parallel, in contiguous stretches, so the first write of each page comes from a different thread and the pages spread over the NUMA nodes;
• StaticAdjList fills its arrays the same way;
• a new BlockMatrixDatabase defaults to blocks of at least 32 MB, which the kernel backs with huge pages almost entirely.

With false, all of that runs on the calling thread and blocks default to 256 columns, as before. It applies to structures built after the call. It never changes results, only where the memory lies.

page_spread() -> Bool

See set_page_spread!.

spreadcopy(x)

A copy of x whose memory is written by all threads, so its pages spread over the NUMA nodes (and, for large arrays, over 2 MB huge pages). Same contents, same results; meant for structures that were written by one thread, e.g. an index read back from disk, or one built with set_page_spread!(false). It runs whatever page_spread() says.

Methods: arrays of plain values, MatrixDatabase, BlockMatrixDatabase (rebuilt with blocks of at least 32 MB), quantized databases, AdjList, StaticAdjList, SearchGraph and AsymmetricSearchGraph (database and adjacency; the rest is copied as is).

spreadcopy(G::SearchGraph) -> SearchGraph

The same graph with its database and adjacency copied by all threads (see spreadcopy): e.g. G = spreadcopy(JLD2.load(file, "G")) for an index read back from disk, whose arrays the reader wrote from one thread. Hints, search parameters and members are copied as they are.

Like spreadcopy(::SearchGraph), on the wrapped graph.

defaultblockbits(Dim, NumType) -> Int

The default NumBits of a BlockMatrixDatabase: blocks of at least 32 MB, so that at least 15 of every 16 of their bytes sit on 2 MB huge pages whatever the block's alignment (an 8 MB block measured 66%), or 256 columns when page_spread is off (the layout up to 1.6.4). The last block holds only what it needs, so a small database does not pay for the size.

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, making room in the last block or allocating a new one.

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. An indexable B (a vector, eachcol, a database) with many items is copied by all threads (see set_page_spread!).

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; many items into block storage are encoded and stored by all threads (see set_page_spread!).

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, as push_item! would. Many indexable items into block storage are quantized and written by all threads (see set_page_spread!).

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.

verbose(ctx::SearchGraphContext) -> Bool

Returns whether ctx is configured to emit verbose output.

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().
• visited: the kind of visited-vertices set each vstates entry is, as a prototype (AutoVisited by default: a bitset up to 2^20 vertices, an exact hash table beyond; BitVisited, ByteVisited, HashVisited, LossyHashVisited); used only when vstates is not given.
• 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 goal, MinRecall(r) with r the target recall (0-1) or MaxMatchError(; maxerror), its distance-based counterpart; both minimize goalvalue, the log cost plus a smooth hinge on the target

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.

• queries_identifiers: where those queries live inside index, which is what makes them internal and so what gets masked from both the gold and the search (see tuningmask). Four combinations, and the fourth is the one the other three cannot express:

  queries	queries_identifiers	what happens
  nothing	nothing	numqueries ids sampled at random; the queries are those objects
  nothing	ids	the queries are database(index)[ids]
  objects	nothing	external, unless they are a SubDatabase of this index's own database
  objects	ids	taken on trust: these objects are those ids, and are masked as internal

  The last row is what a quantized index needs. database(index) holds codes, so raw tuning objects cannot be named by position in it; handing over the pair is the only way to tune with raw queries that the index still knows to mask. It is what an AsymmetricSearchGraph has to do, since tuning it with external queries measures a different problem and tuning it with its own stored codes measures the symmetric one.

  Note on folding: a held-out set of ids is fixed in name but not in effect. With a neardup radius the mask takes each query's whole cluster, and a query whose cluster swallows its gold is dropped (see the empty-gold handling below), so the same list yields fewer usable queries on a heavily duplicated collection than on a clean one.

• 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: how many queries one optimization uses, whatever the source – a sample of the already indexed database when none is given, or a draw from the pool when queries or queries_identifiers name one. A pool smaller than this is used whole, and numqueries=length(queries) is how a given set is used whole on purpose. Drawing rather than using everything matters because this also runs from a construction callback, once every so many insertions: the whole pool each time would cost its size times the number of callbacks. Identifiers the pool names may not be inserted yet; those count as external queries for that call, since their objects exist and none of them is its own vertex yet.

• 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; tradeoff=1.5, width=nothing, transition=(-1, 1)) <: ErrorFunction

Optimization goal: the cheapest configuration whose recall (against a gold standard computed with exhaustive search) reaches minrecall, and, below it, the one whose saving pays for its shortfall. The value minimized is goalvalue,

log(visits) + tradeoffrate · hinge(minrecall − recall)

a smooth hinge on the target rather than a threshold. Far above minrecall only the cost counts; far below, every unit of recall missing costs tradeoffrate = log(tradeoff) / 0.01 nats of cost, and the cost still counts; across a transition zone on the scale of the measurement's own noise, width, the hinge is quadratic, so a configuration a hair short of the target is priced at that hair instead of discarded, and the ranking does not flip with the noise of the recall estimate. (The threshold it replaces ranked anything below the target behind anything above it, whatever the costs, and with 64 tuning queries the estimate's standard error is about 0.04, so the test was a coin toss for every configuration within that of the target.) The hinge has finite support: it is exactly zero before the transition zone, so the goal never pushes the recall further above the target than that zone reaches – a softplus hinge was measured to overshoot the target by two to three widths, growing with tradeoff, because its tail never reaches zero.

Arguments

• minrecall: the target recall (0-1).

• tradeoff: the cost factor accepted per 1% of recall near the target: 1.5 reads "up to 50% more visits for each 1% of recall". Must be finite and > 1. Above the slope of the cost-against-recall front – 10-20 nats per unit of recall on typical graphs, a cost that doubles between recall 0.90 and 0.95 – the minimum is the one a hard constraint would pick; 1.5 is 40. With the default zone the result barely moves between 1.2 and 3 (measured on SISAP 2025 ccnews: recall 0.900-0.913 for a target of 0.9).

• width: the unit of the transition zone, in recall units. nothing (the default) derives it from the data in optimize_index!: the standard error of the macro recall over the tuning queries, as the median over the initial population of std(per-query recall) / sqrt(numqueries), so the zone spans exactly what the measurement cannot tell apart. A small explicit width shrinks the zone to a hard threshold.

• transition: the transition zone (lo, hi), as multipliers of width, in shortfall units s = minrecall − recall (positive below the target). The hinge charges nothing for s ≤ lo · width, a quadratic across the zone, and the shortfall itself, up to a constant, from hi · width on; it is continuous with a continuous derivative for any lo ≤ hi, and lo == hi is a hard threshold at lo · width. Measured on SISAP 2025 ccnews, a target of 0.9, 64 or 256 tuning queries, width derived:

  transition	zone, in widths	at the target	tuned recall lands
  (-1, 1), the default	one width on each side	width / 4	within a width above the target: 0.900-0.913
  (0, 2)	starts at the target	0	like a hard threshold, at or a little under the target with few queries: 0.877-0.901
  (-2, 0)	ends at the target	width (already linear)	one to two widths above: for a target that is a floor to hold on unseen queries

  Any other pair works the same way: (-0.5, 0.5) trusts the measurement more than its own standard error, (-1, 3) is lenient below the target and strict above it.

Arguments

• minrecall: the target recall (0-1).
• tradeoff: the cost factor accepted per 1% of recall near the target: 1.5 reads "up to 50% more visits for each 1% of recall". Must be finite and > 1. Above the slope of the cost-against-recall front – 10-20 nats per unit of recall on typical graphs, a cost that doubles between recall 0.90 and 0.95 – the minimum is the one a hard constraint would pick; 1.5 is 40.
• width: the half-width of the smooth transition, in recall units. nothing (the default) derives it from the data in optimize_index!: the standard error of the macro recall over the tuning queries, as the median over the initial population of std(per-query recall) / sqrt(numqueries), so the objective is flat exactly where the measurement cannot tell configurations apart. A small explicit width recovers a hard threshold.

Examples

optimize_index!(index, ctx, MinRecall(0.95))
optimize_index!(index, ctx, MinRecall(0.95; tradeoff=3.0))        # a shortfall is cheaper to accept
optimize_index!(index, ctx, MinRecall(0.95; transition=(-2, 0)))  # 0.95 is a floor, land above it

MaxMatchError(; maxerror=0.1f0, exponent=1f0, maxdeviation=1f0, spreadfloor=1f-2, tradeoff=1.5, width=nothing, transition=(-1, 1)) <: ErrorFunction

Optimization goal: the cheapest configuration whose MatchError stays at or below maxerror, and, above it, the one whose saving pays for the excess – the same smooth hinge as MinRecall, goalvalue with matcherror − maxerror as the shortfall and width in match-error units. Unlike MinRecall (which compares result and gold identifiers as sets), MatchError compares the distances of the returned neighbors against the distances of the true neighbors at the same rank, so a substitute neighbor tied in distance with the gold one scores as a perfect match even if its identifier differs (relevant e.g. under Hamming, where many candidates share the same integer distance).

For a query q, with k' = min(k, |gold|), gold distances d*_1 <= ... <= d*_k' and the r distances actually returned d_1 <= ... <= d_r (both ascending):

spread(q)     = d*_k' - min(d*_1, d_1) + spreadfloor + ε
deviation_i   = min(max(0, d_i - d*_i) / spread(q), maxdeviation)   for i <= r
deviation_i   = maxdeviation                                        for i > r   (missing position)
matcherror(q) = mean(deviation_i .^ exponent for i in 1:k')

spread(q) is the spread of the gold neighborhood (not just its outer radius), so maxerror reads as a fraction of that spread regardless of how dense or sparse this particular query's neighborhood is — e.g. maxerror=0.1 means "on average, within 10% of the neighborhood's own spread beyond where results should be". 0 is a perfect match. A position never costs more than maxdeviation, what a missing position costs: a returned neighbor farther beyond its gold counterpart than that many spreads is as bad as none, and the score stays in [0, maxdeviation ^ exponent]. That cap is what keeps the mean over queries, and everything built on it (the goal, its width, bootstrapscore), meaningful: measured on SISAP 2025 ccnews without it, ten queries whose gold neighbors were all exact duplicates at distance 0 (spread 0, the search returning items at distance 1.4: 143 per position) made 85% of the mean over 10,500 held-out queries, the mean moved by its own size from one tuning run to the next, and two different maxerror targets tuned to the same configuration.

min(d*_1, d_1) in spread(q) is a deliberate robustness choice: a returned distance below the gold's own minimum is impossible in theory under a consistent distance function, and in practice is usually floating-point noise between the exhaustive (gold) pass and the evaluated index — rather than failing on it (which floating-point noise would trigger often), the range just absorbs it. A d_1 far enough below d*_1 to not be explained by floating-point noise is instead a sign of a real bug (e.g. a distance function inconsistent with the one used for the gold standard); this is not currently asserted/validated, only documented here.

spreadfloor guards against a genuinely degenerate query: with k=1, or whenever the gold neighborhood's k' distances are all tied (routine on real data with near-duplicate/ syndicated items – e.g. ~2% of queries on a real ccnews slice), the true spread d*_k' - min(d*_1, d_1) is exactly 0, and without a real floor spread(q) collapses to ≈ε (machine epsilon) – dividing by that inflates any ordinary, non-buggy distance mismatch by a factor of ~10^6-10^7. spreadfloor should be picked relative to the typical scale of the distance function in use (e.g. 1f-2 is reasonable for a [0, 2]-ranged cosine-family distance, but Hamming over nbits codes wants something more like 1f0, one bit); the default is not universally correct, tune it to your distance. maxdeviation is the second guard, for the queries the floor does not rescue.

Keyword Arguments

• maxerror: the target MatchError (0 is perfect, maxdeviation ^ exponent the worst).
• exponent: the exponent applied to each position's deviation before averaging: 1 for a linear (MAE-like) error, 2 for a quadratic (MSD-like) one that suppresses small deviations and amplifies large ones (missing positions, already at maxdeviation).
• maxdeviation: the most one position can cost, in spreads, and what a missing position (the algorithm returned fewer than k' items) costs.
• spreadfloor: absolute floor added to the gold neighborhood's spread, so a fully degenerate (zero-spread) query doesn't blow up the aggregate error; see above.
• tradeoff: the cost factor accepted per 0.01 of match error near maxerror; must be finite and > 1 (see MinRecall).
• width: the unit of the hinge's transition zone, in match-error units; nothing derives it in optimize_index! as the standard error of the macro match error over the tuning queries (the median over the initial population of std(per-query matcherror) / sqrt(numqueries)).
• transition: the zone (lo, hi) as multipliers of width, placed on maxerror (see MinRecall; here the shortfall is matcherror − maxerror).

Examples

optimize_index!(index, ctx, MaxMatchError(; maxerror=0.1f0, exponent=2f0))

goalvalue(kind::MinRecall, visits::Real, recall::Real; width=kind.width) -> Float64
goalvalue(kind::MaxMatchError, visits::Real, matcherror::Real; width=kind.width) -> Float64

The number optimize_index! minimizes for a configuration that visited visits objects per query and measured the given quality:

log(visits) + tradeoffrate · hinge(shortfall)

with tradeoffrate = log(kind.tradeoff) / 0.01 and shortfall how far the quality falls short of the goal's target, minrecall − recall or matcherror − maxerror. The cost is in nats, so a difference of log(2) is "twice the visits" at any scale and no normalization is needed. The hinge has finite support: with the transition zone a = lo · width to b = hi · width from kind.transition, it is exactly 0 before the zone, a quadratic across it, and the shortfall up to a constant beyond it, continuous with a continuous derivative:

hinge(s) = 0                        for s ≤ a
         = (s − a)² / (2 (b − a))   for a < s < b
         = s − (a + b) / 2          for s ≥ b

For the default (-1, 1) that is (s + width)² / (4 width) across [−width, width] and s beyond.

width must be resolved: given to the goal, passed here, or derived by optimize_index! from the initial population before the first ranking.

abstract type ErrorFunction end

Abstract type for the optimization goals (kind argument) accepted by optimize_index!. It determines how candidate hyperparameter configurations are scored/compared while autotuning the index. Concrete subtypes are MinRecall and MaxMatchError.

Three goals were removed in 1.6. ParetoRecall/ParetoRadius were a weighted sum of squares normalized by the initial population's maximum cost, not a Pareto front, and the trade-off they picked at construction did not carry over to the search; a bi-objective goal, when it returns, will be a smooth, explicitly weighted combination. OptRadius targeted a covering radius within a tolerance, which asked for a look at the distances beforehand to be set at all; MaxMatchError is the same idea with the scale read off each query's own neighborhood.

abstract type LocalSearchAlgorithm end

Base type for the local search algorithms used to solve queries over a SearchGraph. Concrete subtypes (e.g., BeamSearch) implement the strategy used to traverse the graph while looking for the near neighbors of a query object.

AbstractVisited

The set of vertices a graph search has already reached, one per batch slot of a SearchGraphContext (its vstates). Each search starts with reuse!(vstate, n) and then asks check_visited_and_visit!, visited and visit!. The implementations:

• BitVisited: one bit per vertex of the graph, zeroed at every reuse! (the original representation; reuse! costs n/8 bytes of writes per search).
• ByteVisited: one byte per vertex with the generation of the search that reached it (FAISS's VisitedTable); zeroed only every 255 searches, 8 times the bitset's memory.
• HashVisited: an exact open-addressing table of the vertices reached by the current search, tagged with a generation number; reuse! only advances the generation, and the table grows with the largest search seen, not with n.
• LossyHashVisited: a fixed-size table that may forget a vertex (it is then evaluated again) but never reports one that was not reached; it never grows, so it stays in cache. The search guards the result queue against the duplicates a forgotten vertex brings.
• AutoVisited (the default): a bitset up to 2^20 vertices, a HashVisited beyond, in one buffer.

The plain Vector{UInt64} (a bitset) and Set{UInt32} keep working as vstates entries.

AutoVisited(; maxbits=2^20, capacity=2^12)

The default visited set: a bitset while the graph has at most maxbits vertices and a HashVisited table beyond, chosen at every reuse! – a graph under construction crosses the threshold midway. Both live in one buffer of cld(maxbits, 64) words (128 KB by default): the bitset uses its first cld(n, 64) words, and the table its first capacity slots (32 KB, 2K visits before it doubles), growing inside the buffer without clearing it and beyond it only when a search needs more. Below the threshold the bitset's reset (at most maxbits/8 bytes per search) is cheaper than hashing; above it the reset grows with n and the table only with the visit.

BitVisited(nbits=2^21)

One bit per vertex: reuse!(v, n) resizes the bitset to n bits and zeroes it, so its cost per search is n/8 bytes of writes whatever the search visits (2.85 MB at 24M vertices).

ByteVisited(n=0)

One byte per vertex holding the generation of the search that reached it (FAISS's VisitedTable): "visited" is tags[i] == gen. reuse! advances the generation and zeroes the table only when it wraps, every 255 searches; it costs 8 times the memory of BitVisited (n bytes per batch slot) but no per-search reset and no bit manipulation.

HashVisited(; capacity=2^12)

An exact visited set: an open-addressing table (linear probing) of UInt64 slots, each holding the vertex id and the generation of the search that inserted it. reuse! advances the generation instead of clearing (the table is zeroed only when the 32-bit generation wraps), so entries left by earlier searches read as empty. The table doubles when the current search fills half of it and keeps its size for the following searches; its size follows the largest visit, not the graph. Vertex ids must fit in 32 bits.

LossyHashVisited(; capacity=2^15)

A fixed-size visited set that may forget: capacity UInt64 slots (256 KB by default, within a core's L2) in buckets of 8 (one cache line), each slot holding the vertex id and the generation of its search, as in HashVisited. A vertex goes to a stale slot of its bucket, or, when all 8 belong to the current search, overwrites one of them. A lookup finds a vertex only if it is still there, so the set never reports a vertex that was not reached; a forgotten one is evaluated again, which costs a distance evaluation and is counted as one. reuse! advances the generation.

Use it with a finite maxvisits. A forgotten vertex that is still in the result queue is neither pushed nor expanded again, but one that already left it can re-enter the beam whenever Δ > 1 admits it, and the search may then cycle through the same vertices; only the visit cap ends it. With the uncapped BeamSearch a small table can loop indefinitely (measured: 2^11 slots on ccnews, 600K vertices).

mayforget(vstate) -> Bool

Whether vstate can report an already reached vertex as not visited (LossyHashVisited). The search then checks the result queue before pushing a vertex into it.

newvisited(proto::AbstractVisited) -> AbstractVisited

A fresh, empty visited set configured like proto (one per batch slot of a context).

check_visited_and_visit!(vstate, i_::Integer)::Bool

Checks that i_ is already visited: - returns true if already visited - returns false if is not visited yet, but marks it as visited before return

visited(vstate::AbstractVector{UInt64}, i_::UInt64)::Bool

Checks whether vertex i_ is marked as visited in the bit-vector vstate.

visited(vstate::Set{UInt32}, i::Integer)::Bool

Checks whether vertex i is a member of the visited-vertices set vstate.

visit!(vstate::AbstractVector{UInt64}, i_::UInt64)

Marks vertex i_ as visited in the bit-vector vstate.

visit!(vstate::Set{UInt32}, i::Integer)

Marks vertex i as visited by adding it to the set vstate.

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): the near-duplicate distance. An object whose nearest indexed object lies within it becomes a member of that object's cluster instead of a node: one edge to the representative, no edge towards it, never visited by a search, which answers with one representative per cluster; expand/expand! give back the raw neighbors. 0f0 folds exact duplicates, a small positive value near ones (distances re-evaluated on expansion); the default, typemin(Float32) (-Inf32), disables it and every object is a node. The threshold is on the scale of the distance in use, and a value that is not typemin is raised to NEARDUP_NUMERICAL_ZERO, since the distance between two identical objects is often not exactly 0f0 and a literal zero would fold only the pairs that rounded there. The default is left exactly as it is: raising typemin would turn a mechanism that never fires into one that fires on every single-entry neighborhood. Rejected are NaN, which compares false with everything and would silently disable the mechanism; +Inf, which would fold every object into the first node; and any negative threshold. A negative one is rejected because the distances that reach below zero are the ones wrapped to search for farthest objects – Dist.Hacks.NegativeDistanceHack, range (-Inf, 0], and SimilarityFromDistance, range (0, 1] – and under either of them identical objects land at the end of the range that means farthest, so folding near duplicates would fold what by construction never resembles anything. In such a graph neardup is not applicable at any threshold, and the default disables it. Measured on SISAP 2025 ccnews, where 27% of the points are exact duplicates: without it the duplicates of a point form a clique the search walks through, and the queries with ten copies in the database reach recall 0.72-0.75 against 0.86-0.96 overall (see the SearchGraph tutorial's section on near duplicates).
• 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
• selfid: the id of item when it is already a node of the index (rebuild), masked from the search so that it is not its own nearest neighbor – nor, under neardup, its own twin

Members()

The near-duplicate members of a SearchGraph. When a graph is built with Neighborhood(neardup=ϵ), an object whose nearest indexed object lies within ϵ does not become a node of its own: it is a member of that object's cluster, its adjacency is the single edge to the cluster's representative, no node links to it, and the search never visits it. The search therefore answers with representatives – one per cluster – and expand/expand! turn those into the raw neighbors through this table. Members still count in length(G) and keep their database ids; only the navigation changes.

Two maps, kept consistent by addmember!: lists gives a representative's members and representative a member's representative. A representative is never a member.

members(G, id) -> AbstractVector{UInt32}

The members of the cluster id represents: empty for a node without members, and for a member itself – ask its representative (see Members).

representative(G, id) -> UInt32

The representative of id's near-duplicate cluster: id itself when it is a node (see Members).

ismember(G, id) -> Bool

Whether id is a near-duplicate member of a cluster (see Members). Every index answers it; only a SearchGraph built with Neighborhood(neardup=ϵ) has members.

expand(G, q, res) -> iterator of IdDist
expand(G, q, ids::AbstractVector{UInt32}, dists::AbstractVector{Float32})
expand(G, ctx, q, res)
expand(G, ctx, q, ids, dists)

Iterates the result res of a search for q – a queue, or the (ids, dists) pair of one column of searchbatch's matrices – giving each item back followed by the members of its cluster (see Members), each member with its distance to q evaluated by the index's distance. Nothing is modified and nothing is trimmed: a result of k representatives yields k items plus every member they have. For a result cut back to k raw neighbors, use expand!. An index without members yields res as it is.

Given the context the graph was built with, a graph folded at distance zero (Neighborhood(neardup=0f0), see sharesdistance) gives each member its representative's distance without evaluating it: the members are exact copies, so nothing is read for them but their ids. The context must be the one whose Neighborhood built the graph; one claiming distance zero over a graph folded with a larger radius would hand the members their representative's distance.

expand!(G, q, res::AbstractMetricQueue) -> res
expand!(G, q, ids::AbstractVector{UInt32}, dists::AbstractVector{Float32}) -> (ids, dists)
expand!(G, Q::AbstractDatabase, knns::AbstractMatrix{UInt32}, dists::AbstractMatrix{Float32}) -> (knns, dists)
expand!(G, ctx, q, res)
expand!(G, ctx, q, ids, dists)
expand!(G, ctx, Q, knns, dists)

In place: pushes the members of every cluster in the result into it, each with its distance to the query evaluated by the index's distance, and lets the result's own rule trim – a k-nn queue keeps its k nearest, a radius queue what falls within its radius, a column of searchbatch's matrices its k rows. The first stage, search, answered with one representative per cluster; after this the result holds raw neighbors, duplicates included, which is what macrorecall against an exhaustive gold expects. The matrix form runs the columns in parallel. An index without members returns the result untouched.

With the context the graph was built with, a graph folded at distance zero (Neighborhood(neardup=0f0)) gives each member its representative's distance instead of evaluating it, as expand does; the context must be the one whose Neighborhood built the graph.

sharesdistance(ctx) -> Bool

Whether the members a graph built with ctx holds are at distance zero from their representative – Neighborhood(neardup=0f0), raised to NEARDUP_NUMERICAL_ZERO – so that a member is at its representative's distance from any query and the expansion copies that distance instead of evaluating it. Read from the context because the graph does not record the radius it was folded with; a later version is meant to store it in the graph, at the price of changing what a stored graph holds. A context that is not a SearchGraphContext says nothing about the folding, and the members are evaluated.

NEARDUP_NUMERICAL_ZERO

The floor a near-duplicate radius is raised to – Neighborhood's neardup and neardup's ϵ alike: what counts as "distance zero" once floating-point arithmetic has had its say. The distance between two bit-identical vectors is often not 0f0, so a literal neardup=0 folds only the pairs that happened to round there. Measured on SISAP 2025 ccnews and yahooaq (384-dim Float32 under CastF32.NormCosine), half of the bit-identical pairs evaluate to exactly 0f0, a sixth come out negative, and the error never exceeds 6 ulps – so a radius-0 threshold misses about a third of them, the positive third, since the comparison is <=.

1f-5 is an order of magnitude above that largest observed error and three to four orders below any real distance on those datasets (median neighborhood spread 0.081 and 0.096), so it separates cleanly. It is a constant, not a derived bound: a distance whose own scale sits near 1f-5 would be mis-served by it, and deriving the floor from the distance, the numeric type and the dimension is the general answer. Integer code distances need none of this – src/sq/dist.jl makes the equal-scale path exact, so identical codes give exactly 0f0.

addmember!(M::Members, rep, id)

Registers id as a member of rep, which must be a node (not a member itself): the callers resolve chains before calling. A member is never registered twice.

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 (the last one may hold fewer columns, and grows as items arrive). 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)

prefetch_item(db::AbstractDatabase, i::Integer)

Asks the hardware to start bringing the storage of item i into the caches, without touching it: the graph search calls it on the unvisited neighbours of a vertex before it evaluates any of them, so their cache misses overlap instead of being paid one after another (beamsearch_inner_beam). The default does nothing; databases with contiguous storage prefetch the first PREFETCH_LINES cache lines of the item (the hardware streamer follows from there) and whatever per-item side data their distance reads.

prefetchable(db::AbstractDatabase) -> Bool

Whether prefetch_item does anything for db. The graph search skips its prefetch pass when it does not, so a database without contiguous storage pays nothing.

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

database(index)

Gets the entire indexed database

database(index, i)

Gets the i-th object from the indexed database

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]

neighbors(adj::AdjList, i) -> Vector or Nothing

Returns the list of neighbors of node i in adj, i.e., adj.end_point[i]. Returns nothing if node i has never been assigned a neighbor list (it is the caller's responsibility to ensure i refers to an initialized node when a list is expected).

Examples

adj = AdjList(Int32, 3)
add!(adj, 1, Int32[2, 3])
neighbors(adj, 1)  # => Int32[2, 3]
neighbors(adj, 2)  # => nothing (never assigned)

neighbors(adj::StaticAdjList, i::Integer) -> AbstractVector

Returns a view onto the neighbors of node i in adj, computed from the CSR-like offset encoding as end_point[offset[i-1]+1:offset[i]] (with an implicit offset[0] == 0).

Examples

neighbors(sadj, 1)  # view of node 1's neighbor ids

neighbors(adj::AdjDict, i) -> Vector or Nothing

Returns the list of neighbors of node i in adj, or nothing if node i has no entry in adj.end_point (it is the caller's responsibility to ensure i refers to an initialized node when a list is expected).

Examples

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

neighbors_length(adj::AdjList, i) -> Int

Returns the number of neighbors stored for node i in adj, or 0 if node i has never been assigned a neighbor list.

neighbors_length(adj::StaticAdjList, i::Integer) -> Int

Returns the number of neighbors stored for node i in adj, computed from the offset encoding (offset[i] - offset[i-1], with an implicit offset[0] == 0).

neighbors_length(adj::AdjDict, i) -> Int

Returns the number of neighbors stored for node i in adj, or 0 if node i has no entry.

add!(adj::AdjList{T}, n::Integer, N) where T -> AdjList

Adds the neighbors in N (an iterable of ids convertible to T) to node n's neighbor list. Grows adj first (via resize!) if n exceeds its current length. If node n already has a neighbor list, N is appended to it; otherwise a new list is created from N. Thread-safe via adj.glock.

Examples

adj = AdjList(Int32, 2)
add!(adj, 1, Int32[2])
add!(adj, 1, Int32[3])   # appends to node 1's existing list
neighbors(adj, 1)        # => Int32[2, 3]

add!(adj::AdjList{T}, iter) where T -> AdjList

Bulk version of add!: iter yields (i, N) pairs, each adding neighbor set N to node i. Grows adj if needed to accommodate length(iter) nodes. Thread-safe via adj.glock.

Examples

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

add!(adj::StaticAdjList, n, N)

Not supported: StaticAdjList is an immutable, frozen adjacency-list representation. Build the graph with AdjList or AdjDict and convert it with StaticAdjList(adj) once construction is complete.

add!(adj::StaticAdjList, N)

Not supported: StaticAdjList is an immutable, frozen adjacency-list representation. Build the graph with AdjList or AdjDict and convert it with StaticAdjList(adj) once construction is complete.

add!(adj::AdjDict{K,T}, n, N) where {K,T} -> AdjDict

Adds the neighbors in N (an iterable of ids convertible to T) to key n's neighbor list. If key n already has an entry, N is appended to it; otherwise a new list is created from N. Thread-safe via adj.glock.

add!(adj::AdjDict{K,T}, iter) where {K,T} -> AdjDict

Bulk version of add!: iter yields (n, N) pairs, each adding neighbor set N to key n. Thread-safe via adj.glock.

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.

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

Rearranges X[1:n] in place so that it satisfies the binary-heap property with respect to lt.

Number of items currently within res.radius (a prefix, since the queue is sorted by distance).

heapfix_up!(lt::Function, swap::Function, X, i)

Restores the heap property by moving the item at position i upwards (towards the root) while it violates lt with respect to its parent. X is the backing array (or data structure), lt checks the heap property, and swap swaps two items.