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

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

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

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

Why integer-valued distances only

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

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

Why a Metric and not a SemiMetric

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

Searching by Damerau-Levenshtein

Two routes, both useful, neither free:

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

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

When a BK-tree pays off

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

Keyword Arguments

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

Examples

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

distance(index)

Gets the distance function used in the 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(sat::Sat, ctx::AbstractContext, q, res::AbstractKnnQueue) -> res

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

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

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

Arguments

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

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

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

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

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

Arguments

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

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

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

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

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

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

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

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

Arguments

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

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

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

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

Arguments

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

Keyword arguments

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

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

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

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

Arguments

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

Examples

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

module Selection

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

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

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

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

abstract type AbstractSelection end

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

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

Why assign holds positions and not identifiers

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

Which center an object is assigned to

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

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

Based on enet.jl from KCenters.jl

Note: fft is well-defined for metric distances

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

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

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

Arguments

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

Keyword Arguments

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

Returns

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

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

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

Fields beyond the shared ones

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

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

covering and separation are different numbers

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

Examples

using SimilaritySearch

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

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

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

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

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

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

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

Arguments

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

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

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

• X: The input dataset

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

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

Keyword Arguments

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

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

Notes

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

Examples

using SimilaritySearch

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

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

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

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

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

Fields beyond the shared ones

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

There is no separation here, on purpose

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Keyword Arguments

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

Returns

A tuple (hsp_ids, hsp_dists, hsp) where:

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Returns

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

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

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

Arguments

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

Returns

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

Examples

using SimilaritySearch

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

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

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

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

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

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

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

Arguments

• dist: distance function
• X: input database

Keyword Arguments

• samplesize: the size of the sample

Examples

using SimilaritySearch

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

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

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

Arguments

• dist: distance function
• X: input database

Keyword Arguments

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

Examples

using SimilaritySearch

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

recallscore(gold, res) -> Float64

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

Arguments

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

Examples

using SimilaritySearch

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

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

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

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

Arguments

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

Examples

using SimilaritySearch

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

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

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

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

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

Arguments

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

Examples

using SimilaritySearch

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

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

@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 = beginbatch(ctx, @batchid())
    tmp = knnqueue(bctx, view(qcache, 1:ksearch, 2 * @batchid() - 1))
    N = knnqueue(bctx, view(qcache, 1:ksearch, 2 * @batchid()))
@LOOP for objID in 1:n
    find_neighborhood!(N, g, ctx, database(g, objID), tmp, 1:-1; hints=...)  # bug: ctx, not bctx
end

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

Examples

julia> using SimilaritySearch

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

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

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

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

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

@BEGIN

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

@BEGINBATCH

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

@LOOP for i in range ... end

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

@ENDBATCH

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

@END

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

@batchid()

Inside a @BATCHES call's @BEGINBATCH, @LOOP, or @ENDBATCH section, expands to the current batch's fixed, 1-based ordinal index (stable for the whole lifetime of that batch's task). Since batch ids are disjoint – no two concurrently-running batches ever share one – indexing a shared, @nbatches()-sized array by @batchid() is race-free by construction, regardless of scheduler (: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::MMapMatrixDatabase, v::AbstractVector)

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

push_item!(db::VectorDatabase, v)

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

push_item!(S::SubDatabase, v)

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

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

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

Arguments:

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

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

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

Arguments

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

append_items!(a::MatrixDatabase, b)

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

append_items!(db::BlockMatrixDatabase, B)

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

append_items!(db::MMapMatrixDatabase, B)

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

append_items!(db::VectorDatabase, B)

Appends every object in B to the end of db.

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

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

Arguments:

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

Examples

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

append_items!(idx, ctx, items)

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

Arguments:

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

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

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

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

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

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

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

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

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

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

Keyword Arguments

• method: the bit-sketch generator: :gaussian (default), :qr, :adh (AnchoredDistantHyperplanes, built with its own defaults – construct one directly first if it needs tuning), or :external (use a sketch computed outside this package – e.g. another binarization method entirely – passed via sketch) – see SimilaritySearch.Projections.bitsketch; see the vector-space warning above.
• sketch: only used when method=:external. A precomputed (nbits÷64, n) UInt64 matrix (one nbits-bit sketch per column, n == length(database(idx))), used as-is instead of computing B internally – lets any external binarization method (not just :gaussian/:qr/:adh) bootstrap the topology the same way.
• nbits: sketch width in bits, must be a multiple of 64 (default 256, i.e. 4 UInt64 words). A wider sketch costs more memory/compute per comparison but tends to improve recall; see issue #52 for measurements across 64-1536 bits on real embeddings.
• kind: the ErrorFunction OptimizeParameters/optimize_index! tunes the sketch-space construction towards (default MaxMatchError(; maxerror=0.01f0), calibrated to roughly match MinRecall(0.9)'s achieved quality on real embeddings while building noticeably faster and far more consistently run-to-run – see issue #52's measurements). Pass MinRecall(...) to use the more familiar identifier-set-based criterion instead.
• logbase: log base for the sketch-space Neighborhood's size growth, see Neighborhood.
• parallel_block: forwarded as the sketch-space construction's own parallel_block (size of the batch processed in parallel at a time), see SearchGraphContext.

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

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

Arguments:

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

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

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

Arguments

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

Keyword arguments

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

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

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

Keyword Arguments

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

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

abstract type AbstractLog end

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

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

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

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

Rules

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

abstract type AbstractReporter <: AbstractLog end

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

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

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

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

See InformativeLog for the reference implementation.

abstract type AbstractObserver <: AbstractLog end

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

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

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

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

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

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

Keyword Arguments

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

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

The event contract

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

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

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

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

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

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

Examples

using SimilaritySearch

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

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

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

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

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

CallbackLog(callback::Function)

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

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

Examples

using SimilaritySearch

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

LOG(args...)

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

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

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

L1()

The manhattan distance or $L_1$ is defined as

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

L2()

The euclidean distance or $L_2$ is defined as

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

SqL2()

The squared euclidean distance is defined as

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

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

LInfty()

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

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

Lp(p)
Lp(p, pinv)

The general Minkowski distance $L_p$ distance is defined as

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

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

Cosine()

The cosine is defined as:

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

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

NormCosine()

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

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

Angle()

The angle distance is defined as:

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

NormAngle()

Similar to Angle but suppose that input vectors are already normalized

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

Jaccard()

The Jaccard distance is defined as

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

Dice()

The Dice distance is defined as

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

Intersection()

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

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

CosineSet()

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

RogersTanimoto(σ)

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

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

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

Access via Dist.Sets.RogersTanimoto.

Examples

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

Hamming()

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

RogersTanimoto()

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

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

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

Examples

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

RussellRao()

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

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

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

Examples

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

CommonPrefix()

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

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

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

Scratch buffers, and why there is no lock

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

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

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

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

AbstractString inputs (String, SubString, ...)

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

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

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

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

AbstractString inputs (String, SubString, ...)

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

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

Hamming()

The hamming distance counts the differences between two equally sized strings

LCS()
LCS(ctx)

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

Hausdorff(dist::PreMetric)

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

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

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

DirectedHausdorff(dist::PreMetric)

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

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

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

Examples

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

Chamfer(distance)

Computes the Chamfer dissimilarity between two point clouds

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

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

EMD(dist, p)

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

Arguments

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

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

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

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

Examples

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

NegativeDistanceHack(dist)

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

SimilarityFromDistance(dist)

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

DistanceWithIdentifiers(distance, database)

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

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

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

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

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

Arguments

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

Keyword Arguments

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

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

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

abstract type AbstractContext end

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

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

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

Keyword Arguments

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

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

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

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

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

Arguments

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

Keyword Arguments

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

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

Notes

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

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

Examples

using SimilaritySearch

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

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

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

Keyword Arguments

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

Examples

using SimilaritySearch

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

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

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

Keyword Arguments

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

Examples

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

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

Creates a hyperoptimization callback using the given parameters

Arguments

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

See more

• See BeamSearchSpace
• SearchParams arguments of SearchModels.jl

for more details

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

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

Arguments

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

Keyword arguments

• space: defines the search space
• queries: the set of queries to be used to measure performances, a validation set. It can be an AbstractDatabase or nothing.
• ksearch: the number of neighbors to retrieve for queries
• 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.
• MMapMatrixDatabase: Like BlockMatrixDatabase but backed by a memory-mapped file on disk instead of RAM.
• VectorDatabase: A wrapper for vector-like structures. It can contain any kind of objects.
• SubDatabase: A sample of a given database

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

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

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

struct MatrixDatabase{M<:AbstractMatrix} <: AbstractDatabase

MatrixDatabase(matrix::AbstractMatrix)

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

Examples

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

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

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

Fields

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

Please see AbstractDatabase for general usage.

mutable struct MMapMatrixDatabase{Dim,NumType} <: AbstractDatabase

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

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

Durability is opt-in: call flush

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

Please see AbstractDatabase for general usage.

Concurrency

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

Examples

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

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

struct VectorDatabase{V} <: AbstractDatabase

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

Fields

• vecs: the underlying vector-like container of objects

Please see AbstractDatabase for general usage.

Examples

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

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

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

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

Fields

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

Please see AbstractDatabase for general usage.

Examples

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

abstract type AbstractAdjList{T} end

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

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

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

struct AdjList{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

struct AdjDict{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

struct StaticAdjList{T} <: AbstractAdjList{T}

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

Fields

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

Examples

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

AbstractMetricQueue

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

AbstractKnnQueue

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

AbstractRadiusQueue

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

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

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

Fields

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

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

Examples

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

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

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

Fields

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

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

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

Examples

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

RadiusSorted <: AbstractRadiusQueue

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

Fields

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

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

Examples

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

RadiusHeap <: AbstractRadiusQueue

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

Fields

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

Examples

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

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

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.

outdim(p::PCAProjection)

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

outdim(m::DistantHyperplanes)

Returns the number of output bits (hyperplanes) of m.

outdim(m::AnchoredDistantHyperplanes)

Returns the number of output bits (hyperplanes) of m.

outdim(B::RandomHyperplanes)

Returns the number of output bits (reference pairs) of B.

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.

indim(p::PCAProjection)

Returns the input dimension of the projection p, 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. Computed as a single Walsh-Hadamard transform batched over every column at once (see transform!), not as a per-column loop.

Arguments

• hp: the projection to apply
• X: a matrix whose columns are the vectors to project, each of length indim(hp)
• minbatch: accepted for interface symmetry with other transform methods, but unused (see transform!)

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(p::PCAProjection, v::AbstractVector)

Projects the vector v (of length indim(p)) onto p's principal directions, returning a new vector of length outdim(p).

transform(p::PCAProjection, X::AbstractMatrix)

Projects every column (vector) of X onto p's principal directions, returning a new matrix with outdim(p) rows and the same number of columns as X. Unlike RandomProjections/HadamardProjection, this is a single call into MultivariateStats (already a vectorized BLAS matrix-matrix product), so there is no minbatch to parallelize over.

Examples

julia> using SimilaritySearch

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

julia> p = SimilaritySearch.Projections.PCAProjection(X, 32);

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

julia> size(Y)
(32, 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.

Applies a single Walsh-Hadamard transform to the whole matrix at once (Hadamard's FFTW plan is built with the n columns as a "howmany" batch dimension, along the lines of Hadamard.fwht_natural!'s region argument), rather than looping n times over one column each – looping would rebuild an FFTW plan under FFTW's global planning lock on every single column, which is both unamortized (paying full plan-construction overhead per vector instead of once for the batch) and unparallelizable (every thread serializes on that lock); see issue #54.

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: accepted for interface symmetry with other transform! methods (e.g. RandomProjections), but unused: a single batched FWHT call already processes every column without needing to be split across tasks

transform!(p::PCAProjection, out::AbstractVector, v::AbstractVector)
transform!(p::PCAProjection, O::AbstractMatrix, X::AbstractMatrix)

In-place versions of transform: projects v/X using p and stores the result in out/O, which must have length/row-count outdim(p). Returns out/O.

bitsketch(R::AbstractMatrix{<:AbstractFloat}, v::AbstractVector{<:AbstractFloat}) -> Vector{UInt64}
bitsketch(R::AbstractMatrix{<:AbstractFloat}, X::AbstractMatrix{<:AbstractFloat}; minbatch::Int=4) -> Matrix{UInt64}

Computes a random-rotation bit sketch (a SimHash-style binary locality-sensitive hash): rotates the input by R (the same convention as RandomProjections, i.e. v -> R' * v) and encodes the sign of each of the size(R, 2) resulting coordinates as one bit – non-negative maps to 1, negative maps to 0 (see packsigns) – packed into UInt64 words (64 bits per word, cld(size(R, 2), 64) words per sketch). Vectors whose rotated coordinates fall on the same side of the random hyperplanes defined by the columns of R hash to the same bit pattern, so the Hamming distance between two sketches approximates the angular distance between the corresponding original vectors.

Arguments

• R: the rotation matrix, of size (indim, outdim); build one with gaussian or qr (pass its .map), or use bitsketch(method, outdim, data) to build and apply a fresh one in a single step
• v/X: the vector, or matrix (one vector per column), to sketch; must be given as Float32/Float64 (or another AbstractFloat subtype)
• minbatch: (matrix method only) minimum number of columns processed per parallel task

Examples

julia> using SimilaritySearch

julia> R = SimilaritySearch.Projections.gaussian(128, 256).map;

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

julia> B = SimilaritySearch.Projections.bitsketch(R, X);

julia> size(B), eltype(B)  # (4, 1000), UInt64  -- cld(256, 64) == 4 words per sketch

bitsketch(rp::RandomProjections, v::AbstractVector{<:AbstractFloat}) -> Vector{UInt64}
bitsketch(rp::RandomProjections, X::AbstractMatrix{<:AbstractFloat}; minbatch::Int=4) -> Matrix{UInt64}

Computes a bit sketch (see bitsketch(R::AbstractMatrix, data)) using an already-built RandomProjections rotation rp, equivalent to bitsketch(getmap(rp), data). Reuse the same rp to sketch a query the same way as an already-sketched dataset, so that the resulting sketches are comparable.

Examples

julia> using SimilaritySearch

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

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

julia> B = SimilaritySearch.Projections.bitsketch(rp, X);

julia> q = rand(Float32, 128);

julia> bq = SimilaritySearch.Projections.bitsketch(rp, q);  # same rotation, comparable to B's columns

bitsketch(method::Symbol, outdim::Int, data::AbstractVecOrMat{<:AbstractFloat};
          rng::AbstractRNG=Random.default_rng(), FloatType::Type=Float32, minbatch::Int=4)
    -> (bitsketch, R)

Convenience bitsketch that builds a fresh rotation matrix R – using gaussian (method = :gaussian) or qr (method = :qr) – applies it in a single step, and returns both the resulting sketch(es) and R as a tuple (bitsketch, R), so that the very same rotation can be reused afterwards (e.g. via bitsketch(R, data)) to sketch further vectors comparable to this one (e.g. queries against an already-sketched dataset).

Arguments

• method: :gaussian or :qr, selecting which of gaussian/qr builds the rotation matrix; any other value raises ArgumentError
• outdim: the number of sketch bits (i.e., the output dimension of the rotation)
• data: the vector or matrix (one vector per column) to sketch
• rng, FloatType: forwarded to the chosen rotation-matrix generator
• minbatch: (matrix method only) minimum number of columns processed per parallel task

Examples

julia> using SimilaritySearch

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

julia> B, R = SimilaritySearch.Projections.bitsketch(:gaussian, 256, X);

julia> size(B), eltype(B)  # (4, 1000), UInt64

julia> q = rand(Float32, 128);

julia> bq = SimilaritySearch.Projections.bitsketch(R, q);  # reuse R, comparable to B's columns

bitsketch(hp::HadamardProjection, v::AbstractVector{<:AbstractFloat}) -> Vector{UInt64}
bitsketch(hp::HadamardProjection, X::AbstractMatrix{<:AbstractFloat}; minbatch::Int=4) -> Matrix{UInt64}

Computes a bit sketch the same way as bitsketch(R::AbstractMatrix, data), but using the fast Walsh-Hadamard transform (HadamardProjection) instead of a dense random rotation matrix: it encodes the sign of each of the indim(hp) transformed coordinates into UInt64-packed bits (see packsigns).

Arguments

• hp: the HadamardProjection to apply
• v/X: the vector, or matrix (one vector per column), to sketch
• minbatch: (matrix method only) minimum number of columns processed per parallel task

Examples

julia> using SimilaritySearch

julia> hp = SimilaritySearch.Projections.HadamardProjection(128);  # 128 is a power of two

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

julia> B = SimilaritySearch.Projections.bitsketch(hp, X);

julia> size(B), eltype(B)  # (2, 1000), UInt64  -- cld(128, 64) == 2 words per sketch

bitsketch(p::PCAProjection, v::AbstractVector{<:AbstractFloat}) -> Vector{UInt64}
bitsketch(p::PCAProjection, X::AbstractMatrix{<:AbstractFloat}; minbatch::Int=4) -> Matrix{UInt64}

Computes a bit sketch the same way as bitsketch(R::AbstractMatrix, data), but using a fitted PCAProjection instead of a random rotation: it encodes the sign of each of the outdim(p) transformed coordinates into UInt64-packed bits (see packsigns). As with the random-rotation forms, reuse the same p to sketch a query and the dataset it will be compared against, so their sketches are comparable.