struct Sat{DT<:SemiMetric,DBT<:AbstractDatabase} <: AbstractSearchIndex
    dist::DT
    db::DBT
    root::UInt32
    # parents::Vector{UInt32}
    children::Vector{Union{Nothing,Vector{UInt32}}}
    cov::Vector{Float32} # leafs: ``- d(parent, leaf)``, internal: ``\max \{d(parent, u) | u \in children(parent)\}``
end

Spatial Access Tree data structure. Please see Sat function for high level constructors

index!(sat::Sat; <kwargs...>)
index!(sat::Sat, ipart::SatInitialPartition; <kwargs...>)
index!(sat::Sat, 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.
• 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 by a thread on multithreading setups.
  • RandomInitialPartition(nparts=Threads.nthreads(), shuffle=false): construction that divides the dataset (randomly if suffle=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 purporses, i.e., each part will be processed by a thread.

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)

PruningSat(sat::Sat; factor=0.9)

Creates an approximate similarity sarch index based on sat and aggressive pruning; adapted from the paper A probabilistic spell for the curse of dimensionality (Chavez and Navarro, 2001). It supports auto-tuning via optimize!.

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

Creates an approximate similarity sarch index based on sat and aggressive pruning; adapted from the paper A probabilistic spell for the curse of dimensionality (Chavez and Navarro, 2001). It supports auto-tuning via optimize!.

BeamSearchMultiSat(sat::Vector{SatType}; bsize=8, Δ=1f0) where {SatType<:Sat}

Applies beam search on a multi SAT array. See optimize! to tune the index for some objective.

allknn_single_search(psat::BeamSearchParSat, i::Integer, res::KnnResult, pools)

Solves a single query, $i$th object, called from allknn function

allknn_single_search(psat::PrunParSat, i::Integer, res::KnnResult, pools)

Solves a single query, $i$th object, called from allknn function

beamsearch(psat::BeamSearchParSat, i::Integer, res::KnnResult, c::BeamSearchParSatConfig)

Solves a single query, $i$th object, specific solution for allknn_single_search, also used for runconfig.

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

Computes the parents of all elements in the sat tree

ith_par(parents, c, ith)

Retrieves the $i$-th parent of $c$

travelsat(psat::PrunParSat, i::Integer, res::KnnResult, c::PrunParSatConfig)

Solves a single query, $i$th object, specific solution for allknn_single_search, also used for runconfig.