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.

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

The auto-tuned nearest neighbor index (ANNI) of Tellez, Ruiz and Chávez, Singleton indexes for nearest neighbor search, Information Systems 60 (2016) 50–68: an exact index for metrics. A set of objects of the database are its centers, and every other object keeps two numbers, the center nearest to it and its distance to that center. The centers induce a Dirichlet (Voronoi) partition of the database, and the index is a pivot table where each object is filtered by a single pivot, its own center.

A search evaluates every center, then visits the objects in database order and evaluates an object u only when the triangle inequality cannot discard it, |d(q, c(u)) - d(u, c(u))| <= r, with r the covering radius of the result. The search is therefore a scan of two arrays plus the evaluations that survive the filter: cheap internal work, which is what makes the index fast in practice even where it evaluates more distances than heavier indexes.

index! builds it incrementally. Random objects are promoted to centers in steps, each new center stealing the objects that are now nearer to it (the only distances computed are those the triangle inequality cannot rule out), and after every step the mean cost of a sample of queries is measured. The construction stops when a step no longer lowers that cost, so the number of centers is tuned to the data and to the queries, with no parameter to set by hand. NANNI stores the same partition by cluster, and adds the covering-radius and hyperplane rules to discard whole cells.

When it pays off

Like every metric index, it prunes when the query's covering radius is small next to the spread of the distances: low intrinsic dimension, or costly distances (edit distances over strings, for example), where a scan with few evaluations wins. In high intrinsic dimension the filter discards little and the search approaches an exhaustive scan with the cost of the centers on top; there an approximate index such as SearchGraph is the right tool.

Why a Metric and not a SemiMetric

The filter, the stealing rule of the construction and the Dirichlet partition all rely on the triangle inequality. The constructor rejects a non-Metric distance; checkmetric=false overrides it when the distance is a metric typed loosely, or when an approximate index is acceptable.

Arguments

• dist: the distance function, a metric
• db: the database to index

Keyword Arguments

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

Examples

using SimilaritySearch

db = MatrixDatabase(rand(Float32, 4, 10_000))
anni = ANNI(Dist.L2(), db)
ctx = GenericContext()
index!(anni, ctx)
search(anni, ctx, rand(Float32, 4), knnqueue(KnnSorted, 5))

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

The node auto-tuned nearest neighbor index (NANNI) of Tellez, Ruiz and Chávez, Singleton indexes for nearest neighbor search, Information Systems 60 (2016) 50–68: the Dirichlet partition of an ANNI stored by cluster, an exact index for metrics. Every center keeps its cell (the objects nearer to it than to any other center), the covering radius of the cell, and each member's distance to the center.

A search evaluates every center, then visits the cells by increasing distance from the query to their centers. A cell is skipped when the query ball misses its covering ball, d(q, c) > cov(c) + r, and the search stops at the first cell beyond the hyperplane rule, d(q, c) > d(q, c*) + 2r with c* the center nearest to q (every member x of the cell of c has d(x, c) <= d(x, c*); the rule holds for every later cell too, since the cells come in increasing d(q, c) and r only shrinks). Inside a cell the members are sorted by their distance to the center, so the ones the pivot filter |d(q, c) - d(x, c)| <= r keeps form a contiguous run found by binary search. With no sequential scan of the database, NANNI is the member of the family that scales best with the size of the database.

index! builds it as ANNI is built, promoting random centers in steps, but measures NANNI's own search to decide when to stop.

Arguments

• dist: the distance function, a metric
• db: the database to index

Keyword Arguments

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

Examples

using SimilaritySearch

db = MatrixDatabase(rand(Float32, 4, 10_000))
nanni = NANNI(Dist.L2(), db)
ctx = GenericContext()
index!(nanni, ctx)
search(nanni, ctx, rand(Float32, 4), knnqueue(KnnSorted, 5))

getcontext(anni::ANNI; kwargs...)
getcontext(nanni::NANNI; kwargs...)

A GenericContext: these indexes need no dedicated context type. Not part of the formal AbstractSearchIndex interface, a convenience.

annipermutation(anni::ANNI) -> Vector{UInt32}

The order that stores anni's database cell by cell: the centers first, in the order of anni.centers, then the members of every cell, cells in center order and members by increasing distance to their center. See permuteanni.

permuteanni(anni::ANNI, π=annipermutation(anni), π′=invperm(π); permutedb=_permutedb)

A PermutedSearchIndex over a copy of anni whose database is stored in the order π (by default cell by cell, see annipermutation), answering with the original identifiers. The scan then meets the members of a cell together, so the objects it evaluates in a cell sit next to each other in memory, and the center lookup of consecutive objects repeats. permutedb(db, π) makes the copy of the database.

nannipermutation(nanni::NANNI) -> Vector{UInt32}

The order that stores nanni's database as its search visits it: the centers first, then the members cell by cell, each cell by increasing distance to its center. See permutenanni.

permutenanni(nanni::NANNI, π=nannipermutation(nanni), π′=invperm(π); permutedb=_permutedb)

A PermutedSearchIndex over a copy of nanni whose database is stored in the order π (by default the centers and then the cells, see nannipermutation), answering with the original identifiers. The centers are then evaluated from contiguous memory, and so is every run of members a cell evaluates. permutedb(db, π) makes the copy of the database.

EPTable(dist::Dist.Metric, db::AbstractDatabase; groups::Integer=4, checkmetric::Bool=true)
EPTable(db::AbstractDatabase; dist::Dist.Metric, groups::Integer=4, checkmetric::Bool=true)

The extreme pivot table (EPT) of Ruiz, Chávez, Ruiz and Tellez, Extreme pivots: a pivot selection strategy for faster metric search, Knowledge and Information Systems (2020), doi:10.1007/s10115-019-01423-5: an exact index for metrics.

A classic pivot table stores the distance from every object to every pivot, yet for a given object a single pivot ends up discarding it: the one that sees it far from the bulk of its distances, since a query lands near that bulk. The EPT keeps only that pivot. Each of the groups pivot groups is a set of pivots, and every object is associated, in each group, with the pivot p that maximizes |d(u, p) - μ_p|, where μ_p is the mean distance from p to the database; the object stores that pivot and d(u, p). The memory is groups (pivot, distance) pairs per object, whatever the number of pivots, so the groups can hold many pivots: their number is tuned during the construction.

A search evaluates every pivot (they are pushed into the result, being objects of the database), then evaluates an object only when none of its groups pivots discards it, |d(q, p) - d(u, p)| > r with r the covering radius of the result. The table is stored in blocks, one per pivot of the first group holding the objects associated with it, each block sorted by the distance to that pivot. The search visits the blocks by increasing distance from the query to their pivots, so the radius shrinks early, and in each block the objects the first group lets through form a contiguous run found by binary search; the other groups are checked only on that run. The paper describes this kind of sublinear scan as possible but implements the flat scan.

index! builds the groups. Each one grows by windows of random pivots while an estimate of the search cost keeps falling: the cost model of the paper (its Algorithm 3), from the variance of the distances the pivots keep and from statistics of the queries, or the measured cost of a sample of queries.

When it pays off

Like every metric index, it prunes when the query radius is small next to the spread of the distances: low intrinsic dimension, or costly distances. In high intrinsic dimension a pivot discards little and the scan approaches an exhaustive search; an approximate index such as SearchGraph is the right tool there.

Arguments

• dist: the distance function, a metric
• db: the database to index

Keyword Arguments

• groups: the number of pivot groups, i.e., of (pivot, distance) pairs stored per object, the memory of the index (the paper's ℓ; it suggests 2 to 4 for cheap distances and more for costly ones)
• checkmetric: whether a non-Dist.Metric distance is rejected (default true)

Examples

using SimilaritySearch

db = MatrixDatabase(rand(Float32, 4, 10_000))
ept = EPTable(Dist.L2(), db; groups=4)
ctx = GenericContext()
index!(ept, ctx)
search(ept, ctx, rand(Float32, 4), knnqueue(KnnSorted, 5))

NEP(dist::Dist.Metric, db::AbstractDatabase; nfar::Integer=1, checkmetric::Bool=true)
NEP(db::AbstractDatabase; dist::Dist.Metric, nfar::Integer=1, checkmetric::Bool=true)

The node-based extreme pivots (NEP), which are to EPTable what NANNI is to ANNI: an exact index for metrics that gives one set of pivots two roles: the nearest pivot of every object defines its node, a cell of a Dirichlet partition as in NANNI, and the pivots that see it farthest above their mean distance act as extreme pivots, as in EPTable, filtering it inside its cell. Every object keeps its distance to its center and, for each of its nfar far pivots, the pivot and the distance to it; these data are stored by cell, aligned with the cell's members, so a cell is read as contiguous memory.

A far pivot is chosen on the far side, by the largest d(u, p) - μ_p, μ_p being the mean distance from p to the database. On the near side the most extreme pivot of an object is usually its own center, which already filters it.

A search evaluates every pivot (they are objects of the database and go into the result), then visits the cells by increasing distance from the query to their centers, with the rules of NANNI: it stops at the first cell beyond the hyperplane rule, skips a cell whose covering ball misses the query ball, and inside a cell considers only the run of members whose distance to the center is within r of the query's. Each member of that run is evaluated only when none of its far pivots discards it, |d(q, p) - d(u, p)| > r. The far filters cost no evaluation: the query's distance to every pivot is already known.

index! adds random pivots in steps and stops when the mean number of distance evaluations of a sample of queries no longer falls. nfar=0 is a NANNI over the same pivots, a reference to measure the far filters by.

Arguments

• dist: the distance function, a metric
• db: the database to index

Keyword Arguments

• nfar: far pivots kept per object (its internal filters)
• checkmetric: whether a non-Dist.Metric distance is rejected (default true)

getcontext(ept::EPTable; kwargs...)

A GenericContext: an EPTable needs no dedicated context type. Not part of the formal AbstractSearchIndex interface, a convenience.

eptpermutation(ept::EPTable) -> Vector{UInt32}

The order that stores ept's database as its table: by block (pivot of the first group) and, within a block, by increasing distance to that pivot. See permuteept.

permuteept(ept::EPTable, π=eptpermutation(ept), π′=invperm(π); permutedb)

A PermutedSearchIndex over a copy of ept whose database is stored in the order π (by default by the first group, see eptpermutation), answering with the original identifiers. The runs of objects a block lets through are then stored next to each other. permutedb(db, π) makes the copy of the database (by default a MatrixDatabase keeps its layout and anything else becomes a VectorDatabase of copies).

neppermutation(nf::NEP) -> Vector{UInt32}

The order that stores nf's database as its search visits it: the pivots first, then the members cell by cell. See permutenep.

permutenep(nf::NEP, π=neppermutation(nf), π′=invperm(π); permutedb=_permutedb)

A PermutedSearchIndex over a copy of nf whose database is stored in the order π, answering with the original identifiers: the pivots and every run of members a cell evaluates then sit in contiguous memory.