Inverted files and sparse data

abstract type AbstractInvertedFile <: AbstractSearchIndex end

Abstract inverted file; the concrete data structure is InvertedFile.

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

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

Fields

• dist: distance function used at search time (e.g. Dist.Sets.Jaccard(), Dist.NormCosine()).
• adj: posting lists (non-zero id-elements, in rows).
• sizes: number of non-zero values in each element (non-zero values in columns); resized/populated only up to len[].
• db: the original indexed objects, one per identifier; always populated by push_item!/append_items!, but may hold more objects than have actually been indexed – see len.
• len: number of objects already indexed (postings built); may be less than length(database(idx)) if db was grown directly without a following index! call to catch up.

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

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

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

Constructors

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

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

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

Arguments

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

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

Fetches and prepares the involved posting lists to solve q

has_exact_fastpath(dist::PreMetric)::Bool

Whether the score computed while merging posting lists (via set_distance_evaluate) is already the exact dist value. When false, search_invfile instead evaluates dist directly against the objects stored in the index's db for every merge candidate — see FallbackInvFileOutput in invfilesearch.jl; raise t above the default 1 to bound how many such evaluations happen per query.

identiterator(obj)

Iterator over the plain ids/keys in obj, for callers that only need to know which ids/keys are present (e.g. InvertedFile building/re-sorting/searching its posting lists, which never need a weight: the handful of distances with an exact fast path score from intersection size and set sizes alone, and any other distance is evaluated directly against the full objects kept in db – see InvertedFile). Dense Vectors are not accepted directly – convert to a SparseVector first (e.g. via SparseArrays.sparse) so the reduction to non-zero components is explicit in the caller's code.

identiterator(dist::PreMetric, obj)

Distance-aware id-only iterator for obj. Defaults to the distance-agnostic identiterator(obj) dispatch tree above; overload this for a specific (DistType, ObjType) pair when the same native object type must generate different candidate ids depending on which distance the enclosing index is built for (e.g. a shingle-based candidate encoding for a sequence distance).

sort_postinglist!(adj::AbstractAdjList, N)

Sorts a single posting list N (as returned by neighbors(adj, tokenID)) back into the order the merge/search algorithms rely on: ascending by id, for plain token adjacency (UInt32). Override for a different concrete adjacency element type (e.g. a compressed encoding).

InvertedFileContext(; verbose, reporters, observers, maxbatches, parallel_block, scheduler, ...)

The context an inverted file is searched and built with. It holds what a query needs besides the index itself: the logging channels, the batching parameters, the per-batch cost counters, and the scratch buffers that a posting-list merge reuses instead of allocating.

It plays the same role for an inverted file that SearchGraphContext plays for a graph. Use getcontext to obtain one that matches a given index, since the buffers depend on the key type the index uses.

getcontext(invfile::AbstractInvertedFile; kwargs...) -> InvertedFileContext

A context whose buffers match invfile. The scratch buffers a merge reuses are typed by the index's key type, so building the context from the index is safer than building it by hand. The keyword arguments are those of InvertedFileContext.

set_distance_evaluate(dist::PreMetric, intersection::Integer, size1::Integer, size2::Integer)

Computes a score for a candidate found while merging posting lists, given the intersection size of the matching posting lists and the total number of non-zero entries of each of the two compared elements (size1, size2). Only defined for the handful of distances with an exact closed form (see has_exact_fastpath) — the resulting value is exact, computed purely from these three integers, with no need to touch the original objects. For any other dist, search_invfile does not call this function at all — it evaluates dist directly against the stored objects for every merge candidate instead (see FallbackInvFileOutput in invfilesearch.jl); use t > 1 to bound how many such evaluations happen per query.

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

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

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

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

Barybay & Kenyon t-thresholds

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

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

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

Arguments:

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

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

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

About the callback function

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

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

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

Arguments:

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

Simple wrapper around other specific operations depending on t value

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

svs(postinglists, intersect2=baezayates!) -> output

Computes the intersection of the ordered lists in postinglists using a small vs small strategy. Accepts an intersection algorithm of two sets.

This method does not give explicit support for onmatch2!

binarysearch(A, x, sp=1, ep=length(A))

Finds the insertion position of x in A in the range sp:ep

doublingsearch(A, x, sp=1, ep=length(A))

Finds the insertion position of x in A, starting at sp

doublingsearchrev(A, x, sp=1, ep=length(A))

Finds the insertion position of x in A, starting at the end

seqsearch(A, x, sp=1, ep=length(A))

Sequential search, i.e., it starts from sp to ep

seqsearchrev(A, x, sp=1, ep=length(A))

Reverse sequential search, i.e., it starts from ep to sp

imerge2!(output, A, B) -> num. matches

Computes the intersection of A and B (sorted arrays), using a merge-like algorithm, and stores it in output or calls onmatch(A, i, B, j) on every match. See bk! for how change the behaviour of matches.

Spherical

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

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

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

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

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

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

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

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

Arguments

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

Keyword Arguments

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

Examples

julia> using SimilaritySearch, SimilaritySearch.Special.Spherical

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

julia> se = SphericalEmbedding(X);

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

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

julia> q = rand(Float32, 8);

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

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

outdim(se::SphericalEmbedding) -> Int

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

indim(se::SphericalEmbedding) -> Int

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Out-of-place version of transform_query!.

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

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

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

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

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

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

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

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

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

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

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

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

Adaptive dot product between two SparseVectors or SparseVecViews:

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

centroid(cluster::AbstractVector{<:SparseVectorLike})

Centroid (normalized sum) of a cluster of SparseVectors. See sum(::AbstractVector{<:SparseVectorLike}) for the algorithm.