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

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

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, π)

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

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

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

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

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

Examples

using SimilaritySearch

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

search(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(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(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
• progress: a ProgressMeter.Progress object used to report the progress of the computation, or nothing to disable it

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

bichromatic_metricjoin(idxA::AbstractSearchIndex, ctx::AbstractContext, B::AbstractDatabase;
                        k::Int, rank::Int=1, q::Float64=0.9, mingroup::Int=8) -> 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.

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

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)

neardup(idx::AbstractSearchIndex, ctx::AbstractContext, X::AbstractDatabase, ϵ::Real; k::Int=8, blocksize::Int=256, filterblocks=true, verbose=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 OptimizeParametes(MinRecall(recall)).

The function returns a named tuple (idx, map, nn, dist, costdists, costblocks, centers) where:

• idx: the index of the non duplicated elements
• map: a mapping from 1:length(idx) to its positions in X
• nn: an array where each element in $x \in X$ points to its covering element (previously indexed element u such that $d(u, x_i) \leq ϵ$)
• dist: an array of distance values to each covering element (corresponds to each element in nn)
• costdists: distance_evaluations for this call (ctx diffed against a snapshot taken before the call)
• costblocks: block_evaluations for this call, same diffing
• centers: the identifiers of X that survived as non-duplicates (i.e., the $ϵ$-net); sorted for the idx-based method, in construction order for the dist-based convenience method

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
• ϵ: Real value to cut, if negative, then ϵ will be computed using the quantile value at 'abs(ϵ)' in a small sample of nearest neighbor distances; the quantile method should be used only for applications that need some vague approximations to ϵ

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).
• verbose: controls the verbosity of the function
• recall: (only for the dist-based method) target recall used to decide between an exact (recall=1.0) or approximate index

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)
• You can access the set of elements being 'ϵ-non duplicates (the $ϵ-net$) using database(idx) or where nn[i] == i

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.map, D.nn, D.dist, D.centers
D.costdists, D.costblocks  # cost of this call

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

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 (: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.

fft(dist::SemiMetric, X::AbstractDatabase, k::Integer; start::Int=0, verbose::Bool=true, 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: controls the verbosity of the function
• scheduler: the @BATCHES scheduler used for the per-pivot distance update (:default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A named tuple with the following fields:

• centers: the list of the selected centers (identifiers into $X$)
• nn: the id of the nearest selected center of each object (in $X$ order, identifiers between 1 and length(X))
• dists: the distance from each object in the database to its nearest center (in $X$ order)
• ε: the smallest distance among the (k) selected centers, i.e., the separation achieved by the traversal
• costdists: total number of distance evaluations performed by this call (k * length(X)), counted locally (no ctx involved)
• costblocks: always 0 for fft (no block-evaluation concept applies here)

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.nn           # nearest selected center for each object of X
R.dists        # distance to the nearest selected center
R.ε            # separation radius achieved by the traversal
R.costdists    # distance evaluations performed by this call

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

Selects numcenters points far from each other based on density nets. It behaves similarly to fft, returning a similar named tuple so they are interchangeable.

Arguments

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

Keyword Arguments

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

Returns

A named tuple with the following fields:

• centers: the list of the selected centers (identifiers into $X$)
• nn: the id of the nearest selected center of each object (in $X$ order, identifiers between 1 and length(X))
• dists: the distance from each object in the database to its nearest center (in $X$ order)
• costdists: total number of distance evaluations performed by this call
• costblocks: always 0 for dnet

Note: unlike fft/multirandsel, dnet's selection isn't a greedy farthest-point traversal, so there's no well-defined minimum-separation-among-centers quantity to report here – no dmax field is returned.

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

Selects k centers randomly and computes the exact same properties as fft or dnet (such as nn and dists) for the rest of the database X against these centers.

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 (:default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A named tuple with the following fields:

• centers: the list of the selected centers (identifiers into $X$)
• nn: the id of the nearest selected center of each object (in $X$ order, identifiers between 1 and length(X))
• dists: the distance from each object in the database to its nearest center (in $X$ order)
• costdists: total number of distance evaluations performed by this call
• costblocks: always 0 for randsel

multirandsel(dist::SemiMetric, X::AbstractDatabase, k::Integer; m::Int=ceil(Int, log2(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 the exact same properties as fft or randsel for the entire database.

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)))); 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 (:default, :static, :greedy, or :sequential to disable threading entirely). Defaults to get_batch_scheduler.

Returns

A named tuple with the following fields:

• centers: the list of the selected centers (identifiers into $X$)
• nn: the id of the nearest selected center of each object (in $X$ order, identifiers between 1 and length(X))
• dists: the distance from each object in the database to its nearest center (in $X$ order)
• ε: the smallest distance among the k selected centers, i.e., the separation achieved (typemax(Float32) if fewer than 2 centers were selected)
• costdists: total number of distance evaluations performed by this call
• costblocks: always 0 for multirandsel

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

@BATCHES minbatch [scheduler=: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 :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 = @set ctx.batchid = @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 (:static/:default/: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:

• :static (the default): one task per thread, never migrates mid-execution. 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. :static remains the default for its simpler, more predictable scheduling, not because anything in this package still depends on it for correctness. Trade-off: throws immediately if a @BATCHES call is ever nested inside another already-threaded region, or invoked from a non-main thread.
• :dynamic/:default: whatever Threads.@threads itself currently defaults to (currently :dynamic; passed through as :default here so this package does not hard- code a name that Julia itself reserves the right to change).
• :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 :default, :static, :greedy, :sequential. See set_batch_scheduler! for what each means and how to change it.

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

Appends an item into the result set

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

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

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

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

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

Appends an item into the result set

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

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

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

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

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

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

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

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

push_item!(db::MatrixDatabase, v)

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

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

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

push_item!(db::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!(idx::AbstractInvertedFile, ctx::InvertedFileContext, obj)

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

Arguments

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

append_items!(a::MatrixDatabase, b)

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

append_items!(db::BlockMatrixDatabase, B)

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

append_items!(db::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!(idx, ctx, items)

Appends all items elements into the index idx. It work in parallel using all available threads.

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,
    verbose::Bool=true
)

Computes the knr projection matrix using numrefs references and calls index!(idx, ctx, Val(:knr), knr).

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.

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).

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

Base type for logging backends. A logger is stored (e.g., as ctx.logger) in a context object (a subtype of AbstractContext) and is passed to LOG by index operations (push_item!, append_items!, index!, etc.) so that they can report their progress without depending on any particular logging backend. Concrete subtypes must implement:

LOG(log::MyLog, event::Symbol, index::AbstractSearchIndex, ctx::AbstractContext, sp::Integer, ep::Integer)

LogList(list::Vector{AbstractLog}=AbstractLog[InformativeLog()])

An AbstractLog backend that fans a single log event out to every logger in list, in order – use it to attach more than one logger (e.g. the default InformativeLog plus a custom one) to the same context at once.

InformativeLog(; dt::Float64=1.0, prompt::String="LOG")

An AbstractLog backend that prints a short status line to stderr reporting the current size of the index, available/used memory, and a timestamp, throttled so that it prints at most once every dt seconds (i.e., calls happening less than dt seconds after the previous printed message are silently skipped). This avoids flooding the output when logging happens inside tight or highly parallel loops.

Keyword Arguments

• dt: minimum number of seconds between two consecutive printed messages
• prompt: a string prefix printed at the beginning of every logged line (useful to tell apart loggers of different indexes/stages)

Examples

using SimilaritySearch

logger = InformativeLog(; dt=2.0, prompt="[my-index]")
ctx = GenericContext(; logger)

LOG(log::LogList, event::Symbol, index::AbstractSearchIndex, ctx::AbstractContext, sp::Integer, ep::Integer)

Forwards the log event to every logger contained in log.list. See LOG for the general contract.

LOG(log::InformativeLog, event::Symbol, index::AbstractSearchIndex, ctx::AbstractContext, sp::Integer, ep::Integer)

Prints, at most once every log.dt seconds, a status line to stderr with event, the type of index, the given range sp:ep (the start and end positions of the operation being logged, e.g., of an append_items! call), the current index size, memory usage, and a timestamp. Calls that arrive before the throttling interval has elapsed since the previous printed message do nothing.

LOG(log::InformativeLog, event::Symbol, index::SearchGraph, ctx::SearchGraphContext, sp::Integer, ep::Integer)

Internal logging hook, invoked during insertion to report memory usage and neighborhood-size statistics (when event === :add!) for the vertex range sp:ep, throttled by log's timer.

L1()

The manhattan distance or $L_1$ is defined as

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

L2()

The euclidean distance or $L_2$ is defined as

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

SqL2()

The squared euclidean distance is defined as

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

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

LInfty()

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

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

Lp(p)
Lp(p, pinv)

The general Minkowski distance $L_p$ distance is defined as

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

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

Cosine()

The cosine is defined as:

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

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

NormCosine()

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

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

Angle()

The angle distance is defined as:

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

NormAngle()

Similar to Angle but suppose that input vectors are already normalized

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

Jaccard()

The Jaccard distance is defined as

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

Dice()

The Dice distance is defined as

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

Intersection()

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

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

CosineSet()

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

RogersTanimoto(σ)

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

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

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

Access via Dist.Sets.RogersTanimoto.

Examples

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

Hamming()

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

RogersTanimoto()

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

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

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

Examples

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

RussellRao()

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

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

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

Examples

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

CommonPrefix()

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

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

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

evaluate(::Levenshtein, a, b) uses a small pool of scratch buffers (Cpool, a Channel{Vector{Int16}}): each call take!s a buffer, uses it, and put!s it back (inside a try/finally, so a thrown exception can't leak it). This has no dependency on thread identity at all – unlike Threads.threadid()-indexing, it is safe under every @BATCHES scheduler (:static/:default/:greedy), and under any other concurrency model too (e.g. calling evaluate from a user's own Threads.@spawn code), since correctness never relies on which thread/task happens to run a given call. A smaller pool only ever costs throughput (a take! blocks until another call returns a buffer), never correctness.

ctx (a GenericContext/SearchGraphContext, anything with a .maxbatches field) is accepted so the pool's size can be driven by the same maxbatches knob used everywhere else in this package, instead of a bare Threads.maxthreadid(); either way the pool is clamped to at least 1 buffer (a zero-sized pool would deadlock on the first call).

Hamming()

The hamming distance counts the differences between two equally sized strings

LCS()
LCS(ctx)

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

Hausdorff(dist::PreMetric)

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

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

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

DirectedHausdorff(dist::PreMetric)

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

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

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

Examples

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

Chamfer(distance)

Computes the Chamfer dissimilarity between two point clouds

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

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

EMD(dist, p)

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

Arguments

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

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

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

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

Examples

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

NegativeDistanceHack(dist)

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

SimilarityFromDistance(dist)

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

DistanceWithIdentifiers(distance, database)

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

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

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

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

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

Arguments

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

Keyword Arguments

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

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

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

abstract type AbstractContext end

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

GenericContext(KnnType::Type{<:AbstractKnnQueue}=KnnSorted;
    verbose::Bool=true, logger=InformativeLog(),
    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: controls the number of output messages.
• logger: how to handle and log events.
• 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;
    logger=LogList(AbstractLog[InformativeLog(dt=2.0)]),
    verbose=false,
    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

• logger: how to handle and log events, mostly for insertions for now.
• verbose: controls the number of output messages.
• 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 @set ctx.batchid = @batchid(), once per batch, not passed here directly.
• scheduler: the @BATCHES scheduler used by every @BATCHES call driven by this context (passed through as scheduler=ctx.scheduler). Defaults to whatever get_batch_scheduler currently returns, captured once at construction time (later calls to set_batch_scheduler! do not retroactively change an already-built context). Pass scheduler=:sequential to force every @BATCHES call driven by this context to run unthreaded, regardless of Threads.nthreads().
• beams: knn queues cache used while inserting elements (used by BeamSearch; nothing builds a fresh one sized by maxbatches).

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

Notes

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

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

Examples

using SimilaritySearch

ctx = SearchGraphContext()                          # default configuration
ctx = SearchGraphContext(; verbose=true)             # verbose logging
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,
    numqueries=64,
    initialpopulation=16,
    maxpopulation=16,
    bsize=4,
    mutbsize=16,
    crossbsize=8,
    maxiters=16,
    params=SearchParams(; maxpopulation, bsize, mutbsize, crossbsize, maxiters, verbose=verbose(ctx)),
    rng=Random.default_rng()
)

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

Arguments

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

Keyword arguments

• space: defines the search space
• queries: the set of queries to be used to measure performances, a validation set. It can be an AbstractDatabase or nothing.
• ksearch: the number of neighbors to retrieve for queries
• numqueries: if queries===nothing then a sample of the already indexed database is used, numqueries is the size of the sample.
• rng: random number generator used to draw the sample of queries when queries===nothing.
• initialpopulation: the initial sample for the optimization procedure
• params: the parameters of the solver, see SearchParams arguments of SearchModels.jl package for more information. Alternatively, you can pass some keywords arguments to SearchParams, and use the rest of default values:
  • initialpopulation=16: initial sample
  • maxpopulation=16: population upper limit
  • bsize=4: beam size (top best elements used by select, mutate and crossing operations.)
  • mutbsize=16: number of mutated new elements in each iteration
  • crossbsize=8: number of new elements from crossing operation.
  • maxiters=16: maximum number of iterations.

Examples

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

MinRecall(; minrecall=0.9f0) <: ErrorFunction

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

Keyword Arguments

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

Examples

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

OptRadius(; tol=0.1) <: ErrorFunction

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

Keyword Arguments

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

Examples

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

ParetoRecall <: ErrorFunction

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

ParetoRadius <: ErrorFunction

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

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

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

Parameters

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

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

abstract type NeighborhoodFilter end

Postprocessing of a neighborhood using some criteria. Called from find_neighborhood!

IdentityNeighborhood()

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

Examples

neighborhood = Neighborhood(filter=IdentityNeighborhood())

SatNeighborhood()

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

Examples

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

DistalSatNeighborhood()

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

Examples

neighborhood = Neighborhood(filter=DistalSatNeighborhood())

KCentersNeighborhood()

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

Examples

neighborhood = Neighborhood(filter=KCentersNeighborhood())

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

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

Arguments

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

Keyword Arguments

• hints: Search hints

RandomHints(; logbase=1.1)

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

Keyword Arguments

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

Examples

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

DisjointHints(; logbase=1.1)

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

Keyword Arguments

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

Examples

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

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

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

Keyword Arguments

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

Examples

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

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

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

Keyword Arguments

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

Examples

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

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

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

Keyword Arguments

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

Examples

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

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

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

Fields

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

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

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

Arguments

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

Examples

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

abstract type Callback end

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

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

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

Arguments

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

Keyword Arguments

• force: if true, callbacks are executed unconditionally.

abstract type AbstractDatabase end

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

The basic implementations are:

• MatrixDatabase: A wrapper for object-vectors stored in a Matrix, columns are the objects. It is static.
• DynamicMatrixDatabase: A dynamic representation for vectors that allows adding new vectors.
• VectorDatabase: A wrapper for vector-like structures. It can contain any kind of objects.
• SubDatabase: A sample of a given database

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

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

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

struct MatrixDatabase{M<:AbstractMatrix} <: AbstractDatabase

MatrixDatabase(matrix::AbstractMatrix)

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

Examples

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

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

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

Fields

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

Please see AbstractDatabase for general usage.

struct VectorDatabase{V} <: AbstractDatabase

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

Fields

• vecs: the underlying vector-like container of objects

Please see AbstractDatabase for general usage.

Examples

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

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

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

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

Fields

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

Please see AbstractDatabase for general usage.

Examples

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

abstract type AbstractAdjList{T} end

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

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

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

struct AdjList{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

struct AdjDict{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

struct StaticAdjList{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

AbstractMetricQueue

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

AbstractKnnQueue

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

AbstractRadiusQueue

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

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

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

Fields

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

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

Examples

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

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

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

Fields

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

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

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

Examples

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

RadiusSorted <: AbstractRadiusQueue

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

Fields

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

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

Examples

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

RadiusHeap <: AbstractRadiusQueue

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

Fields

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

Examples

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

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.

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.

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!(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.

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

IdIntDist(id, dist)

Stores a pair of objects to be accessed. Similar to IdDist but it stores an integer dist

Examples

item = IdIntDist(3, 5)
item.id    # 3
item.dist  # 5

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.

SQu2

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

quantize(X::AbstractMatrix)

Scalar-quantizes each column (vector) of X to 2 bits per coordinate, packing four codes into each UInt8. This reduces the memory footprint of a database of vectors by roughly a factor of 16 with respect to Float32 at the cost of precision. Each column is quantized independently using its own minimum and scale factor, computed from the extrema of the column so that the whole range [min, max] is mapped to the \{0,1,2,3\} codes.

quantize wraps SQu2Database that implements the AbstractDatabase interface, i.e., length(db) gives the number of vectors and db[i] returns the i-th vector as a SQu2Vec that can be indexed to retrieve dequantized Float32 coordinates.

Arguments

• X: a matrix whose columns are the vectors to be quantized; size(X, 1) (the dimension) must be a multiple of 4 (throws ArgumentError otherwise), since 4 coordinates are packed into each UInt8. Pad X with extra rows to the next multiple of 4 if needed.

Examples

julia> using SimilaritySearch

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

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

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

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

Quantizes a single vector v to 2 bits per coordinate, the same way as the vectors already stored in db, returning a SQu2Vec. Since SQu2 computes each vector's own min/scale independently from its own extrema (see quantize(X::AbstractMatrix)), this does not read or depend on db's stored data or parameters; db is only used to validate that v has the expected (padded) dimension. This is convenient, e.g., to quantize a query vector the same way as the vectors stored in db, so that it can be compared against them with L1/L2/SqL2.

Arguments

• db: the database v should be dimensionally consistent with
• v: the vector to quantize; length(v) must equal db's (padded) vector dimension

Examples

julia> using SimilaritySearch

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

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

julia> q = rand(Float32, 8);

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

SQu2Vec(v::AbstractVector)

A single vector quantized to 2 bits per coordinate. It stores the packed codes (four 2-bit codes per UInt8, V) along with the linear dequantization parameters (E::SQMinC) computed from the extrema of v. Indexing a SQu2Vec (qvec[i]) unpacks and dequantizes the i-th coordinate back to a Float32 approximation of the original value.

This type is the element produced by indexing a SQu2 database; it is normally not created directly by users.

Arguments

• v: the input vector to quantize; length(v) must be a multiple of 4 (throws ArgumentError otherwise), since 4 coordinates are packed into each UInt8. Pad v with extra coordinates to the next multiple of 4 if needed.

L1()

A Manhattan-like ($L_1$) distance for SQu2Vec (2-bit quantized) vectors. evaluate dequantizes both codes coordinate by coordinate and accumulates their difference af - bf.

Note: unlike the general L1 distance, this implementation does not take the absolute value of the per-coordinate difference before accumulating, so the result is not guaranteed to be non-negative; it should be understood as an approximation intended for relative ranking of 2-bit quantized vectors rather than a true metric.

L2()

The Euclidean ($L_2$) distance between two 2-bit quantized vectors (SQu2Vec), or between a SQu2Vec and a plain vector. evaluate dequantizes coordinate by coordinate, accumulates the squared differences (see SqL2), and returns its square root.

SqL2()

The squared Euclidean distance between two 2-bit quantized vectors (SQu2Vec), or between a SQu2Vec and a plain vector. evaluate dequantizes coordinate by coordinate and accumulates the squared differences (af - bf)^2, avoiding the square root computed by L2.

SQu4

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

quantize(X::AbstractMatrix)

Scalar-quantizes each column (vector) of X to 4 bits per coordinate, packing two codes into each UInt8. This reduces the memory footprint of a database of vectors by roughly a factor of 8 with respect to Float32 at the cost of precision. Each column is quantized independently using its own minimum and scale factor, computed from the extrema of the column so that the whole range [min, max] is mapped to the codes \{0, 1, \ldots, 15\}.

quantize wraps SQu4Database that implements the AbstractDatabase interface, i.e., length(db) gives the number of vectors and db[i] returns the i-th vector as a SQu4Vec that can be indexed to retrieve dequantized Float32 coordinates.

Arguments

• X: a matrix whose columns are the vectors to be quantized; size(X, 1) (the dimension) must be a multiple of 2 (throws ArgumentError otherwise), since 2 coordinates are packed into each UInt8. Pad X with an extra row if needed.

Examples

julia> using SimilaritySearch

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

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

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

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

Quantizes a single vector v to 4 bits per coordinate, the same way as the vectors already stored in db, returning a SQu4Vec. Since SQu4 computes each vector's own min/scale independently from its own extrema (see quantize(X::AbstractMatrix)), this does not read or depend on db's stored data or parameters; db is only used to validate that v has the expected (padded) dimension. This is convenient, e.g., to quantize a query vector the same way as the vectors stored in db, so that it can be compared against them with L1/L2/SqL2.

Arguments

• db: the database v should be dimensionally consistent with
• v: the vector to quantize; length(v) must equal db's (padded) vector dimension

Examples

julia> using SimilaritySearch

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

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

julia> q = rand(Float32, 8);

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

SQu4Vec(v::AbstractVector)

A single vector quantized to 4 bits per coordinate. It stores the packed codes (two 4-bit codes per UInt8, V) along with the linear dequantization parameters (E::SQMinC) computed from the extrema of v. Indexing a SQu4Vec (qvec[i]) unpacks and dequantizes the i-th coordinate back to a Float32 approximation of the original value.

This type is the element produced by indexing a SQu4 database; it is normally not created directly by users.

Arguments

• v: the input vector to quantize; length(v) must be a multiple of 2 (throws ArgumentError otherwise), since 2 coordinates are packed into each UInt8. Pad v with an extra coordinate if needed.

L1()

The Manhattan ($L_1$) distance between two 4-bit quantized vectors (SQu4Vec). evaluate dequantizes both codes coordinate by coordinate and accumulates the absolute value of their difference.

L2()

The Euclidean ($L_2$) distance between two 4-bit quantized vectors (SQu4Vec), or between a SQu4Vec and a plain vector. evaluate dequantizes coordinate by coordinate, accumulates the squared differences (see SqL2), and returns its square root.

SqL2()

The squared Euclidean distance between two 4-bit quantized vectors (SQu4Vec), or between a SQu4Vec and a plain vector. evaluate dequantizes coordinate by coordinate and accumulates the squared differences (af - bf)^2, avoiding the square root computed by L2.

SQu8

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

quantize(X::AbstractMatrix)

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

quantize creates a SQu8Database struct that follows the AbstractDatabase interface, i.e., length(db) gives the number of vectors and db[i] returns the i-th vector as a SQu8Vec that can be indexed to retrieve dequantized Float32 coordinates.

See also SQgu8's quantize for a variant that shares a single pair of quantization parameters across all columns instead of computing them per column.

Arguments

• X: a matrix whose columns are the vectors to be quantized

Examples

julia> using SimilaritySearch

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

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

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

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

Quantizes a single vector v to 8 bits per coordinate, the same way as the vectors already stored in db, returning a SQu8Vec. Since SQu8 computes each vector's own min/scale independently from its own extrema (see quantize(X::AbstractMatrix)), this does not read or depend on db's stored data or parameters; db is only used to validate that v has the expected dimension. This is convenient, e.g., to quantize a query vector the same way as the vectors stored in db, so that it can be compared against them with L1/L2/SqL2/NormCosine.

Arguments

• db: the database v should be dimensionally consistent with
• v: the vector to quantize; length(v) must equal db's vector dimension

Examples

julia> using SimilaritySearch

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

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

julia> q = rand(Float32, 8);

julia> qv = ScalarQuant.SQu8.quantize(db, q);  # quantized the same way as db's vectors

SQu8Vec(v::AbstractVector)

A single vector quantized to 8 bits per coordinate (one UInt8 code per coordinate, stored in V), along with the linear dequantization parameters (E::SQMinC) computed from the extrema of v. Indexing a SQu8Vec (qvec[i]) dequantizes the i-th coordinate back to a Float32 approximation of the original value.

This type is the element produced by indexing a SQu8 database; it is normally not created directly by users.

Arguments

• v: the input vector to quantize

L1()

The Manhattan ($L_1$) distance between two 8-bit quantized vectors (SQu8Vec). evaluate dequantizes both codes coordinate by coordinate and accumulates the absolute value of their difference.

L2()

The Euclidean ($L_2$) distance between two 8-bit quantized vectors (SQu8Vec). evaluate dequantizes coordinate by coordinate, accumulates the squared differences (see SqL2), and returns its square root.

SqL2()

The squared Euclidean distance between two 8-bit quantized vectors (SQu8Vec). evaluate dequantizes coordinate by coordinate and accumulates the squared differences (af - bf)^2, avoiding the square root computed by L2.

NormCosine()

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

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

evaluate dequantizes coordinate by coordinate (either between two SQu8Vec, or between a SQu8Vec and a plain vector) and accumulates the products before computing the final 1 - dot.

SQgu4

Global (database-wide) 4-bit scalar quantization: quantize maps every coordinate of every vector using a single shared min/scale pair, packing two 4-bit codes per UInt8, and NormCosine/SqL2 compare the resulting codes directly with SIMD. Accessed as ScalarQuant.SQgu4.quantize, etc.

quantize(X::AbstractMatrix; minmax=nothing, quant=[0.025, 0.975], samplesize=0)

Scalar-quantizes every entry of X to 4 bits using a single, global pair of dequantization parameters shared by all columns, unlike SQu4's quantize which computes an independent min/scale per column. As with SQgu8's quantize, this is useful when the columns of X share a comparable value range, since a single global range provides enough precision while being cheaper to compute and store.

Codes are packed two per UInt8 (low nibble, high nibble), exactly like SQu4's, so the returned matrix has ceil(Int, size(X, 1) / 2) rows. Packing pairs of dimensions into a single byte, combined with a global (rather than per-column) min/scale, lets SqL2 and NormCosine operate directly on the packed codes with SIMD, without any per-element dequantization: since every column shares the same affine mapping, comparisons and (squared) differences computed in code space are already proportional to the ones in the original space.

The global [min, max] range is estimated by sampling entries of X and taking quantiles of the sample (to be robust to outliers), unless it is provided explicitly via minmax. Every entry x is then mapped as round(clamp((x - min) * c, 0, 15)) with c = 15 / (max - min + 1e-6).

Arguments

• X: the matrix to quantize; each entry is quantized independently but using shared min/max values
• minmax: an optional (min, max) tuple giving the value range to use; when nothing (the default) the range is estimated from a random sample of the entries of X using quant
• quant: the lower and upper quantiles (of the sampled entries of X) used to estimate min and max when minmax is not given
• samplesize: the number of entries sampled (with replacement) from X to estimate the quantiles; when 0 (the default) it is set to ceil(Int, length(X)^0.5)

Examples

julia> using SimilaritySearch

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

julia> Q = ScalarQuant.SQgu4.quantize(X; minmax=(0f0, 1f0));  # explicit range

julia> size(Q), eltype(Q)  # (4, 1000), UInt8

quantize(v::AbstractVector; minmax=nothing, quant=[0.025, 0.975], samplesize=0)

Scalar-quantizes a single vector v to 4 bits, using the same global scheme as quantize(X::AbstractMatrix), producing a Vector{UInt8} (nibble-packed, two codes per byte) of length ceil(Int, length(v) / 2), instead of a Matrix{UInt8}.

Arguments

• v: the vector to quantize
• minmax: an optional (min, max) tuple giving the value range to use; when nothing (the default) the range is estimated from a random sample of v's entries using quant. Must match the dataset's minmax if v is to be compared against an existing quantized dataset.
• quant: the lower and upper quantiles (of the sampled entries of v) used to estimate min and max when minmax is not given
• samplesize: the number of entries sampled (with replacement) from v to estimate the quantiles; when 0 (the default) it is set to ceil(Int, length(v)^0.5)

Examples

julia> using SimilaritySearch

julia> minmax = (0f0, 1f0);

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

julia> Q = ScalarQuant.SQgu4.quantize(X; minmax);  # dataset, using an explicit range

julia> q = rand(Float32, 8);

julia> qv = ScalarQuant.SQgu4.quantize(q; minmax);  # query, using the *same* range

julia> length(qv), eltype(qv)  # (4, UInt8)

NormCosine()

Dissimilarity between two vectors quantized with quantize (nibble-packed, globally-scaled 4-bit codes), computed as the negative dot product of the raw packed codes. Since both vectors share the same global min/scale, the dot product of codes is an affine, order-preserving proxy of the dot product of the original (typically pre-normalized) vectors, so no per-element dequantization is needed. evaluate unpacks each byte into its low and high nibble and accumulates their products with SIMD.

SqL2()

Squared Euclidean distance between two vectors quantized with quantize (nibble-packed, globally-scaled 4-bit codes). Since both vectors share the same global min/scale, the squared difference of the raw codes is proportional to the squared difference of the original values, so evaluate accumulates squared code differences directly, unpacking each byte's low and high nibble with SIMD, without any per-element dequantization.

SQgu8

Global (database-wide) 8-bit scalar quantization: quantize maps every coordinate of every vector using a single shared min/scale pair, and NormCosine/SqL2 compare the resulting codes directly with SIMD. Accessed as ScalarQuant.SQgu8.quantize, etc.

quantize(X::AbstractMatrix; minmax=nothing, quant=[0.025, 0.975], samplesize=0)

Scalar-quantizes every entry of X to 8 bits (UInt8) using a single, global pair of dequantization parameters shared by all columns, unlike SQu8's quantize which computes an independent min/scale per column. This is useful, e.g., when the columns of X are known to share a comparable value range and a single global range provides enough precision while being cheaper to compute and store.

The global [min, max] range is estimated by sampling entries of X and taking quantiles of the sample (to be robust to outliers), unless it is provided explicitly via minmax. Every entry x is then mapped as round(clamp((x - min) * c, 0, 255)) with c = 255 / (max - min + 1e-6).

Arguments

• X: the matrix to quantize; each entry is quantized independently but using shared min/max values
• minmax: an optional (min, max) tuple giving the value range to use; when nothing (the default) the range is estimated from a random sample of the entries of X using quant
• quant: the lower and upper quantiles (of the sampled entries of X) used to estimate min and max when minmax is not given
• samplesize: the number of entries sampled (with replacement) from X to estimate the quantiles; when 0 (the default) it is set to ceil(Int, length(X)^0.5)

Examples

julia> using SimilaritySearch

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

julia> Q = ScalarQuant.SQgu8.quantize(X; minmax=(0f0, 1f0));  # explicit range

julia> size(Q), eltype(Q)  # (8, 1000), UInt8

quantize(v::AbstractVector; minmax=nothing, quant=[0.025, 0.975], samplesize=0)

Scalar-quantizes a single vector v to 8 bits (UInt8), using the same global scheme as quantize(X::AbstractMatrix), producing a Vector{UInt8} (one code per coordinate) instead of a Matrix{UInt8}.

Arguments

• v: the vector to quantize
• minmax: an optional (min, max) tuple giving the value range to use; when nothing (the default) the range is estimated from a random sample of v's entries using quant. Must match the dataset's minmax if v is to be compared against an existing quantized dataset.
• quant: the lower and upper quantiles (of the sampled entries of v) used to estimate min and max when minmax is not given
• samplesize: the number of entries sampled (with replacement) from v to estimate the quantiles; when 0 (the default) it is set to ceil(Int, length(v)^0.5)

Examples

julia> using SimilaritySearch

julia> minmax = (0f0, 1f0);

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

julia> Q = ScalarQuant.SQgu8.quantize(X; minmax);  # dataset, using an explicit range

julia> q = rand(Float32, 8);

julia> qv = ScalarQuant.SQgu8.quantize(q; minmax);  # query, using the *same* range

julia> length(qv), eltype(qv)  # (8, UInt8)

NormCosine()

Dissimilarity between two vectors quantized with quantize (globally-scaled 8-bit codes), computed as the negative dot product of the raw codes. Since both vectors share the same global min/scale, the dot product of codes is an affine, order-preserving proxy of the dot product of the original (typically pre-normalized) vectors, so no per-element dequantization is needed. evaluate accumulates the products with SIMD, widening each UInt8 code to UInt32 to avoid overflow.

SqL2()

Squared Euclidean distance between two vectors quantized with quantize (globally-scaled 8-bit codes). Since both vectors share the same global min/scale, the squared difference of the raw codes is proportional to the squared difference of the original values, so evaluate accumulates squared code differences directly with SIMD, widening each UInt8 code to Int32 to safely represent negative differences, without any per-element dequantization.

RandomProjections(map::M) where {M<:AbstractMatrix}

Wraps a projection matrix map of size (indim, outdim) used to reduce the dimension of vectors from indim to outdim via a linear projection (v -> map' * v). This is a standard dimensionality-reduction technique for similarity search: projecting onto a lower-dimensional space reduces both memory usage and distance-computation cost, while approximately preserving relative distances (see the Johnson-Lindenstrauss lemma).

Use gaussian or qr to build a RandomProjections map, and transform/transform! to apply it to vectors or matrices of vectors.

Arguments

• map: the projection matrix, with indim rows and outdim columns

Examples

julia> using SimilaritySearch

julia> rp = SimilaritySearch.Projections.gaussian(128, 32);  # random gaussian projection 128 -> 32

julia> rp2 = SimilaritySearch.Projections.qr(128, 32);  # QR-orthogonalized projection 128 -> 32

gaussian(rng::AbstractRNG, FloatType::Type, indim::Int, outdim::Int)
gaussian(indim::Int, outdim::Int=indim)

Builds a RandomProjections whose map is a dense indim × outdim matrix with entries drawn independently from a Normal distribution with mean zero and standard deviation 1/outdim, whose columns are then normalized to unit norm. This is a Gaussian random projection: unlike qr, the resulting columns are not orthogonal to each other, but generating and applying it is cheaper.

Arguments

• rng: the random number generator to use (defaults to Random.default_rng())
• FloatType: the floating point type of the projection matrix (defaults to Float32)
• indim: the dimension of the input vectors
• outdim: the dimension of the projected vectors (defaults to indim)

Examples

julia> using SimilaritySearch

julia> rp = SimilaritySearch.Projections.gaussian(128, 32);

julia> size(SimilaritySearch.Projections.getmap(rp))
(128, 32)

qr(rng::AbstractRNG, FloatType::Type, indim::Int, outdim::Int)
qr(indim::Int, outdim::Int=indim)

Builds a RandomProjections whose map is the (first outdim columns of the) Q factor of the QR decomposition of a random indim × indim matrix. Unlike gaussian, the resulting projection matrix has orthonormal columns, which makes the projection an isometry up to the subspace it projects onto (distances between projected vectors are not shrunk by non-orthogonality), at the extra cost of computing the QR factorization.

Arguments

• rng: the random number generator to use (defaults to Random.default_rng())
• FloatType: the floating point type of the projection matrix (defaults to Float32)
• indim: the dimension of the input vectors
• outdim: the dimension of the projected vectors (defaults to indim)

outdim(rp::RandomProjections)

Returns the output dimension of the projection rp, i.e., the dimension of the vectors produced by transform/transform!.

outdim(hp::HadamardProjection)

Returns the output dimension of the projection hp, i.e., the dimension of the vectors produced by transform/transform!. Always equal to indim(hp), since HadamardProjection does not reduce dimensionality.

indim(rp::RandomProjections)

Returns the input dimension of the projection rp, i.e., the dimension that vectors passed to transform/transform! are expected to have.

indim(hp::HadamardProjection)

Returns the input dimension of the projection hp, i.e., the dimension that vectors passed to transform/transform! are expected to have.

transform(rp::RandomProjections, v::AbstractVector)

Projects the vector v (of length indim(rp)) using rp, returning a new vector of length outdim(rp). Each output coordinate is the dot product of v with the corresponding column of the projection map.

Arguments

• rp: the projection to apply
• v: the input vector to project

transform(rp::RandomProjections, X::AbstractMatrix; minbatch::Int=4)

Projects every column (vector) of X using rp, returning a new matrix with outdim(rp) rows and the same number of columns as X. Columns are projected in parallel using @BATCHES.

Arguments

• rp: the projection to apply
• X: a matrix whose columns are the vectors to project, each of length indim(rp)
• minbatch: minimum number of columns processed per parallel task (see @BATCHES)

Examples

julia> using SimilaritySearch

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

julia> rp = SimilaritySearch.Projections.gaussian(128, 32);

julia> Y = SimilaritySearch.Projections.transform(rp, X);

julia> size(Y)
(32, 1000)

transform(hp::HadamardProjection, v::AbstractVector)

Projects the vector v (of length indim(hp)) using hp, returning a new vector of the same length. Computed as the fast Walsh-Hadamard transform of v (sequency-ordered).

Arguments

• hp: the projection to apply
• v: the input vector to project

transform(hp::HadamardProjection, X::AbstractMatrix; minbatch::Int=4)

Projects every column (vector) of X using hp, returning a new matrix of the same size as X. Columns are projected in parallel using @BATCHES.

Arguments

• hp: the projection to apply
• X: a matrix whose columns are the vectors to project, each of length indim(hp)
• minbatch: minimum number of columns processed per parallel task (see @BATCHES)

Examples

julia> using SimilaritySearch

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

julia> hp = Projections.HadamardProjection(128);

julia> Y = Projections.transform(hp, X);

julia> size(Y)
(128, 1000)

transform!(rp::RandomProjections, out::AbstractVector, v::AbstractVector)

In-place version of transform: projects v using rp and stores the result in out, which must have length outdim(rp). Returns out.

Arguments

• rp: the projection to apply
• out: the output vector where the projected vector is stored
• v: the input vector to project, of length indim(rp)

transform!(rp::RandomProjections, O::AbstractMatrix, X::AbstractMatrix; minbatch::Int=4)

In-place version of transform(rp, X): projects every column of X using rp and stores the result in O, which must have outdim(rp) rows and the same number of columns as X. Returns O.

Arguments

• rp: the projection to apply
• O: the output matrix where the projected vectors are stored
• X: a matrix whose columns are the vectors to project, each of length indim(rp)
• minbatch: minimum number of columns processed per parallel task (see @BATCHES)

transform!(hp::HadamardProjection, out::AbstractVector, v::AbstractVector)

In-place version of transform: projects v using hp and stores the result in out, which must have length indim(hp) (== outdim(hp)). Returns out.

Arguments

• hp: the projection to apply
• out: the output vector where the projected vector is stored, of length indim(hp)
• v: the input vector to project, of length indim(hp)

transform!(hp::HadamardProjection, O::AbstractMatrix, X::AbstractMatrix; minbatch::Int=4)

In-place version of transform(hp, X): projects every column of X using hp and stores the result in O, which must have the same size as X. Returns O.

Arguments

• hp: the projection to apply
• O: the output matrix where the projected vectors are stored
• X: a matrix whose columns are the vectors to project, each of length indim(hp)
• minbatch: minimum number of columns processed per parallel task (see @BATCHES)

HadamardProjection(indim::Int)
HadamardProjection(indim::Int, outdim::Int)

Wraps a fast Walsh-Hadamard transform (FWHT), used as an orthogonal change of basis (via transform/transform!), analogous in purpose to RandomProjections but computed with the $O(n \log n)$ FWHT (via Hadamard.fwht) instead of a dense matrix-vector product, and requiring no random matrix to be generated or stored.

Unlike RandomProjections, HadamardProjection does not reduce dimensionality: transform always returns as many coordinates as it received (outdim(hp) == indim(hp)), since fwht computes a full, exact (up to normalization), orthogonal transform of its input, in the sequency ordering (i.e., ordered by number of sign changes, roughly analogous to increasing frequency in a Fourier transform). The two-argument constructor exists only to make outdim explicit at call sites that already pass one to other projection types (e.g. RandomProjections); it requires outdim == indim and raises ArgumentError otherwise.

Arguments

• indim: the dimension of the input vectors; must be a power of two (fwht requirement), otherwise an ArgumentError is thrown
• outdim: if given, must equal indim (otherwise an ArgumentError is thrown), since this projection does not support dimensionality reduction/truncation

Examples

julia> using SimilaritySearch

julia> hp = Projections.HadamardProjection(128);

julia> Projections.indim(hp), Projections.outdim(hp)
(128, 128)

Spherical

Implements the spherical embedding of Neyshabur & Srebro, "On Symmetric and Asymmetric LSHs for Inner Product Search" (2015): a dataset-dependent transform that turns Maximum Inner Product Search (MIPS) into ordinary nearest-neighbor search under a standard metric (e.g. squared Euclidean or NormCosine).

The scheme is asymmetric: the dataset and the queries are mapped with two different functions, transform/transform! (data-side, P) and transform_query/transform_query! (query-side, Q):

\[P(x) = \left[\frac{x}{M}, \sqrt{1 - \left\|\frac{x}{M}\right\|^2}\right] \qquad Q(q) = \left[\frac{q}{\|q\|}, 0\right]\]

where $M$ is the maximum norm over the fitted dataset. Both P(x) and Q(q) land exactly on the unit sphere, and for any fixed query, ranking data points by increasing ||P(x) - Q(q)|| (or decreasing dot product) recovers exactly the ranking by decreasing inner product $x \cdot q$ – M and \|q\| are constants w.r.t. x, so they do not affect the ordering. See SphericalEmbedding for how M is fitted and stored, and its docstring for the caveat that matters when the underlying database keeps growing.

Both dense (AbstractVector/AbstractMatrix/MatrixDatabase) and sparse (Special.Sparse.SparseVecView/SparseDatabase, and plain SparseArrays.SparseVector/ SparseMatrixCSC) representations are supported.

SphericalEmbedding(X::AbstractMatrix; pad::Bool=true, padmultiple::Int=8, maxnorm=nothing)
SphericalEmbedding(db::MatrixDatabase; pad::Bool=true, padmultiple::Int=8, maxnorm=nothing)
SphericalEmbedding(X::SparseMatrixCSC; maxnorm=nothing)
SphericalEmbedding(db::Special.Sparse.SparseDatabase; maxnorm=nothing)

Fits a spherical embedding (Neyshabur & Srebro) over a dataset, storing the metadata needed by transform/transform!/transform_query/ transform_query!: the dataset's maximum norm maxnorm (M), its input dimension indim, and (dense only) an optional number of extra zero-padding coordinates pad. The embedded (output) dimension is indim + pad + 1 (the +1 is the residual-norm coordinate appended by transform); see outdim.

Since maxnorm is computed once, from the dataset given here, this struct is exactly the "fitted state" that must be saved and reused: apply the SAME SphericalEmbedding to the dataset (via transform) and to every later query (via transform_query) – never re-fit a new one per query.

Arguments

• X/db: the dataset to fit against; dense forms accept an AbstractMatrix (columns are objects) or a MatrixDatabase; sparse forms accept a SparseMatrixCSC (columns are objects) or a Special.Sparse.SparseDatabase.

Keyword Arguments

• pad: dense only. When true (the default), pads the embedded dimension up to the next multiple of padmultiple with extra zero coordinates – zero-valued coordinates do not change any dot product/norm, so this is purely a memory-layout knob (e.g. for SIMD-friendly alignment), never a correctness one. Sparse inputs do not support padding (there is nothing to align; padding a sparse vector would just mean storing explicit zeros).
• padmultiple: dense only, the multiple to pad indim + 1 up to when pad=true (default 8).
• maxnorm: an optional precomputed maximum norm to use instead of scanning X/db (e.g. to reuse a previously-fitted value, or to deliberately fit a looser bound that tolerates some future growth without going stale).

Examples

julia> using SimilaritySearch, SimilaritySearch.Special.Spherical

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

julia> se = SphericalEmbedding(X);

julia> outdim(se)  # 8 + pad + 1
16

julia> P = transform(se, X);       # embed the dataset

julia> q = rand(Float32, 8);

julia> Qq = transform_query(se, q); # embed a query the SAME way

julia> length(Qq) == outdim(se)
true

outdim(se::SphericalEmbedding) -> Int

Output (embedded) dimension produced by transform/transform_query: indim(se) + pad + 1 (the +1 is the appended coordinate – the residual norm for transform, always 0 for transform_query).

indim(se::SphericalEmbedding) -> Int

Input dimension expected by transform/transform_query: the dimension of the original vectors, not counting any padding or the appended residual coordinate.

transform(se::SphericalEmbedding, x::AbstractVector) -> Vector{Float32}

Out-of-place version of transform!: returns a freshly allocated Vector{Float32} of length outdim(se).

transform(se::SphericalEmbedding, X::AbstractMatrix; minbatch::Int=4) -> Matrix{Float32}

Embeds every column (object) of X using transform, returning a new Matrix{Float32} with outdim(se) rows and the same number of columns as X.

transform(se::SphericalEmbedding, db::MatrixDatabase; minbatch::Int=4) -> MatrixDatabase

Embeds every object of db using transform, returning a new MatrixDatabase wrapping a freshly allocated Matrix{Float32}.

transform(se::SphericalEmbedding, x::Special.Sparse.SparseVecView) -> SparseVecView

Sparse-vector version of transform: scales the stored nonzero entries of x by 1/se.maxnorm and appends one explicit (outdim(se), residual) entry, reusing Special.Sparse's existing distance machinery unchanged (the appended index is always the largest, so the result stays sorted). se must have been fitted without padding (se.pad == 0, the default for sparse inputs).

transform(se::SphericalEmbedding, x::SparseArrays.SparseVector) -> SparseArrays.SparseVector

Version of transform for a plain SparseArrays.SparseVector (as opposed to Special.Sparse.SparseVecView); same semantics.

transform(se::SphericalEmbedding, X::SparseMatrixCSC) -> SparseMatrixCSC

Embeds every column of the sparse matrix X (see transform), returning a new SparseMatrixCSC with outdim(se) rows and the same number of columns as X.

transform(se::SphericalEmbedding, db::Special.Sparse.SparseDatabase) -> SparseDatabase

Embeds every object of db using transform, returning a new SparseDatabase.

transform!(se::SphericalEmbedding, out::AbstractVector, x::AbstractVector) -> out

In-place data-side spherical embedding (P(x), see Spherical): scales x by 1/se.maxnorm, fills any padding coordinates with zero, and appends the residual-norm coordinate sqrt(1 - ||x/maxnorm||^2), so that out lands exactly on the unit sphere. out must have length outdim(se).

transform!(se::SphericalEmbedding, O::AbstractMatrix, X::AbstractMatrix; minbatch::Int=4) -> O

In-place version of transform(se, X): embeds every column of X (see transform!) into the corresponding column of O, which must have outdim(se) rows and the same number of columns as X. Columns are embedded in parallel using @BATCHES.

transform_query(se::SphericalEmbedding, q::AbstractVector) -> Vector{Float32}

Out-of-place version of transform_query!.

transform_query(se::SphericalEmbedding, Q::AbstractMatrix; minbatch::Int=4) -> Matrix{Float32}

Embeds every column (query) of Q using transform_query, returning a new Matrix{Float32} with outdim(se) rows and the same number of columns as Q.

transform_query(se::SphericalEmbedding, q::Special.Sparse.SparseVecView) -> SparseVecView
transform_query(se::SphericalEmbedding, q::SparseArrays.SparseVector) -> SparseArrays.SparseVector

Sparse-vector version of transform_query. Unlike transform's sparse methods, no extra entry is appended – the query's appended coordinate is always exactly 0, and sparse formats already represent unlisted entries as 0 implicitly.

transform_query!(se::SphericalEmbedding, out::AbstractVector, q::AbstractVector) -> out

In-place query-side spherical embedding (Q(q), see Spherical): unlike transform!, q is scaled by its OWN norm (not se.maxnorm), and every padding coordinate together with the final appended coordinate is set to 0 (there is no residual term to compute on the query side – it is always exactly 0, by construction). out must have length outdim(se). A zero q maps to an all-zero out.

Must be applied with the SAME se used to transform the dataset being searched – se only contributes indim/outdim bookkeeping here (maxnorm is not used at all), so, unlike transform!, this function itself never goes stale as the dataset grows; only re-fitting se (which changes outdim) would require re-embedding queries.

transform_query!(se::SphericalEmbedding, O::AbstractMatrix, Q::AbstractMatrix; minbatch::Int=4) -> O

In-place version of transform_query(se, Q).

transform_query!(se::SphericalEmbedding, q::Special.Sparse.SparseVecView) -> SparseVecView
transform_query!(se::SphericalEmbedding, q::SparseArrays.SparseVector) -> SparseArrays.SparseVector

In-place version of transform_query for sparse vectors. This method modifies the input vector's values in-place (avoiding allocations for the values), but it returns a new vector/view object because the output dimensionality is outdim(se) (typically dim + 1).

SparseVecView(n, nzind, nzval)

A read-only view of a single sparse vector of length n, given as parallel arrays of non-zero indices nzind and non-zero values nzval (as produced by, e.g., rowvals/nonzeros on a column of a SparseMatrixCSC).

SparseDatabase(M::MType) where {MType<:SparseMatrixCSC}

An AbstractDatabase wrapping a sparse matrix M (in CSC format); each column of M is treated as a stored vector, and indexing the database (db[i]) returns the i-th column as a SparseVecView.

sparsedot(a, b; small_threshold::Int=30, ratio_threshold::Float32=3.0f0)

Adaptive dot product between two SparseVectors or SparseVecViews:

• both sides have fewer than small_threshold stored entries, or their sizes are within ratio_threshold of each other: a plain linear merge.
• otherwise (one side much larger than the other): a Hwang-Lin/galloping merge.

abstract type AbstractInvertedFile <: AbstractSearchIndex end

Abstract inverted file; the concrete data structure is InvertedFile.

struct InvertedFile{DistType<:PreMetric, AdjType<:AbstractAdjList, DbType<:AbstractDatabase} <: AbstractInvertedFile

A general-purpose inverted index: a sparse matrix-like representation mapping component dimensions (or set elements/tokens) to identifiers (AdjType's element type is UInt32, plain token/set membership; other concrete adjacency element types, e.g. a compressed encoding, can be added by extending getcontainer, internal_push!, and sort_postinglist!). It always keeps the original indexed object in db.

Fields

• dist: distance function used at search time (e.g. Dist.Sets.Jaccard(), Dist.NormCosine()).
• adj: posting lists (non-zero id-elements, in rows).
• sizes: number of non-zero values in each element (non-zero values in columns).
• db: the original indexed objects, one per identifier; always populated by push_item!/append_items!.

For a handful of distances (the set metrics in Dist.Sets, see InvertedFiles.has_exact_fastpath) the score computed while merging posting lists is already exact, at O(1) cost. For any other distance (including Dist.NormCosine), every merge candidate is instead scored by evaluating dist directly against the objects stored in db, so results for that path are exact too — the number of such evaluations (hence cost) is controlled by the t-threshold parameter of search; raise t above the default 1 to bound the number of real evaluations per query.

const DictInvertedFile{DistType, KeyType, DbType} = InvertedFile{DistType, AdjDict{KeyType, UInt32}, DbType}

A dictionary-backed inverted file mapping posting list keys of type KeyType (e.g., String, Vector{UInt8}, NTuple, Int) to document identifiers (UInt32). Empty or non-existent posting lists are never stored in memory or disk, enabling use over arbitrary or massive key spaces.

Constructors

• DictInvertedFile(::Type{KeyType}, dist::PreMetric=Dist.Sets.Jaccard(); db::AbstractDatabase=VectorDatabase(Any[]), hint_size::Integer=0)
• DictInvertedFile(dist::PreMetric=Dist.Sets.Jaccard(); KeyType::Type=Any, db::AbstractDatabase=VectorDatabase(Any[]), hint_size::Integer=0)

search_invfile(idx::InvertedFile, ctx::InvertedFileContext, q, Q, res::AbstractKnnQueue, t)

Find candidates for solving query Q using idx. It calls callback on each candidate (objID, dist)

Arguments

• idx: inverted index
• q: the query object, only used for distances without an exact fast path (see InvertedFiles.has_exact_fastpath)
• Q: the set of involved posting lists, see select_posting_lists
• t: threshold (t=1 union, t > 1 solves the t-threshold problem); for distances without an exact fast path, t also bounds how many real evaluate calls happen per query — raise it to reduce cost.

select_posting_lists(idx::AbstractInvertedFile, ctx::InvertedFileContext, q)

Fetches and prepares the involved posting lists to solve q

bk!(output, L, P, findpos::Function=doublingsearch) -> int. size

Computes the intersection of a list of posting lists using the Barbay and Kenyon algorithm.

See umerge! if you need to change how matches are captured (onmatch! function).

bkt!(output, L, [P,], [findpos::Function=doublingsearch]; t::Int=length(L)) -> num. matches

Barybay & Kenyon t-thresholds

See umerge! if you need to change how matches are captured (onmatch! function).

 umerge!(output, L, P=ones(Int32, length(L_)); t::Int=1) -> num. matches

Merges posting lists in L and saves the union in output. The merge result is stored into output array. You can customize how to do this specializing the onmatch!(output, L, P, t::Int) function.

Arguments:

• L: The array of posting lists, the array can be destroyed in the process.

• P: The array of current positions in posting lists, i.e., initial state as an array of ones of size $|L|$.

• t: Computes t-thresholds, i.e., t from 1 (union) to |L| (intersection) of posting lists in L using findpos storing the result set in output.

About the callback function

output, L and P are the arguments same than the input, while t is the actual number of lists having the match. Note 1: you should access L[i][P[i]] to get the entry of the ith list, i.e., $1 \leq t \leq |P|$. Note 2: L and P as container lists will be also modified, the contained lists remain untouched.

xmerge!(output, L, P=ones(Int32, length(L_)); t::Int=1) -> num. matches

Solves t-threshold set operation using other algorithms choosing among them by given t

Arguments:

• output: vector like to store the t-threshold set
• L: the list of posting lists to be merged. The posting lists are left untouched but the container is modified.
• P: indices of the current merging-state (idem to L)
• t: the threshold, i.e., t=1 (union) ... t=|L| performs intersection)

Simple wrapper around other specific operations depending on t value

See umerge! if you need to modify the output behaviour.