Tree-based indexes

struct Sat{DT<:Dist.SemiMetric,DBT<:AbstractDatabase} <: AbstractSearchIndex
    dist::DT
    db::DBT
    root::UInt32
    children::Vector{Union{Nothing,Vector{UInt32}}}
    cov::Vector{Float32}
end

Spatial Access Tree data structure. Please see Sat constructor for the high level entry point, and index! to build the tree once constructed.

cov[i] is always non-negative: for an internal node (children[i] !== nothing) it is the covering radius (the max distance from i to any of its children); for a leaf node (children[i] === nothing) it is simply the distance from i to its actual tree parent. The sign of cov does not distinguish leaf/inner status – use children[i] === nothing for that.

SatContext(KnnType::Type{<:AbstractKnnQueue}=KnnSorted; kwargs...) -> SatContext

Context object for the approximate/autotuned SAT search variants (BeamSearchSat, PruningSat, BeamSearchMultiSat, PrunParSat, BeamSearchParSat). Provides per-batch (ctx.batchid-indexed) scratch caches, so every @BATCHES-driven search is race-free regardless of scheduler:

• beam_ids/beam_dists: backing storage for a KnnSorted beam queue, retrieved via getbeam.
• queues: a plain Vector{UInt32} used as a DFS stack, retrieved via getqueue.
• vstates: a visited-vertices bitset, retrieved via getvstate.

Keyword Arguments

• maxbeam: capacity of the per-batch beam cache. Must be >= the largest bsize explored by whatever optimization_space is used with optimize_index! – getbeam clamps rather than resizing/erroring on mismatch.
• maxbatches, batchid, scheduler, costdists, costblocks: same meaning as in GenericContext/SearchGraphContext.

getcontext(sat::Sat; kwargs...) -> GenericContext

Convenience constructor for a plain GenericContext suitable for Sat's exact construction/search. Not part of the formal AbstractSearchIndex interface (see SatContext for the approximate variants, which need richer per-batch caches).

BeamSearchSat(sat::Sat; bsize=8, Δ=1f0, maxvisits=typemax(Int))

Approximate SAT search via aggressive beam pruning; adapted from Chávez & Navarro (2001). Autotunes via optimize_index! using the existing BeamSearchSpace/combine/ mutate hooks already defined for BeamSearch (SearchGraph's tuning machinery).

BeamSearchParSat(sat::Sat; α=1f0, bsize=4, Δ=1.0, maxvisits=typemax(Int))

allknn-oriented beam search: each query that is one of sat's own indexed points climbs its ancestor chain, running a beam search rooted at each ancestor in turn until the result stops improving. Queries that are not one of sat's own points fall back to a plain root-rooted beam search.

BeamSearchMultiSat(sat::Vector{<:Sat}; bsize=8, Δ=1f0, maxvisits=typemax(Int))

Beam search over a forest of Sat partitions of the same underlying database (e.g. built via RandomInitialPartition). A node internal in any tree of the forest is expanded through all trees where it is internal, increasing the chance of finding a good descent path even when it's a leaf in some particular tree.

PruningSat(sat::Sat; factor=0.9)

Aggressive-pruning approximate SAT search ("probabilistic spell", Chávez & Navarro 2001). factor==1 recovers exact search. Autotunes via optimize_index! using PruningSatSpace.

PrunParSat(sat::Sat; depth=3, factor=0.95)

allknn-oriented pruning search: each query that is one of sat's own indexed points starts its search from its depth-th ancestor instead of the tree root, drastically reducing cost for the all-vs-all setting. Queries that are not one of sat's own points (plain search) fall back to exact SAT search, since no ancestor is known for them.

PruningSatSpace(; factor=0.2:0.1:0.9, factor_scale=(...)) <: AbstractSolutionSpace

Autotuning search space for PruningSat's pruning factor.

permutesat(sat::Sat, π=satpermutation(sat), π′=invperm(π); DBType=MatrixDatabase)

Permute sat to optimize cache access patterns; the database is copied (materialized via DBType) and permuted. The permuted index is stored in a PermutedSearchIndex to allow plug-and-play index interchange with the unpermuted sat.

Arguments

• sat: input Sat index.
• π: permutation.
• π′: inverse permutation.
• DBType: database type used to materialize the permuted copy (defaults to MatrixDatabase; use VectorDatabase for non-vector object types).

satpermutation(sat::Sat) -> Vector{UInt32}

The breadth-first order of sat's identifiers, allocating the result. See satpermutation!.

satpermutation!(π, sat::Sat) -> π

Fill π with the identifiers of sat in breadth-first order from the root. Objects close in the tree end close in π, which is what makes the permutation useful for storing the database in an order that follows the tree.

SatInitialPartition()

Build one tree from one root. This is the plain spatial access tree.

RandomInitialPartition(; nparts=max(4, Threads.nthreads()), shuffle=false)

Split the dataset into nparts parts at random and build one tree over each one, which gives a forest instead of a single tree. The parts are built in parallel, and a query visits all of them. shuffle randomizes the order of the objects before the split.

ProximalSortSat()

Order the children of a node by distance to it, nearest first. This is the classical construction of a spatial access tree.

DistalSortSat()

Order the children of a node by distance to it, farthest first. This is the more recent construction, and it produces different covering radii than ProximalSortSat.

RandomSortSat()

Order the children of a node at random. This is the default for Sat.

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

getcontext(bkt::BKT; kwargs...)

A GenericContext – a BKT search allocates no scratch of its own, so it needs no dedicated context type. Not part of the formal AbstractSearchIndex interface, a convenience.