Documentation
¶
Overview ¶
Package ivfq is the clustering half of an IVF index in the FAISS sense ("IVF + quantizer"): the sizing rule that keeps clusters at about HoodTarget vectors, the centroid trees a query probes, the split and merge rules that hold cluster sizes between rebuilds, the Policy that names the next cluster to split, and a binary codec for centroid sets and their deltas. It also holds the distance vocabulary every subpackage shares: Metric, Score, Dot, L2Sq and CosineSim.
The sizing rule is the package's central claim: k = HoodK(N) = ceil(N/HoodTarget), so clusters hold about HoodTarget vectors whatever N is and cluster COUNT carries the growth. A default query probes DefaultNprobe(k) clusters, which is not constant in N and cannot be: flat IVF recall tracks the fraction of the corpus scanned, and no sizing changes that. What fixed-size clusters buy is a better index at whatever budget is chosen, and a far cheaper build, because kmeans fits them on a sample. After the build nothing here asks for a pass over N: Policy and MergeTargets read only per-cluster counts, radii and centroids, which an index already holds, and rebuilding an index is a caller's explicit decision.
The other halves are subpackages: kmeans fits the centroids, rabitq gives every cluster a 1-bit candidate column with a scorer and an error bound, rank selects hits by int id, codec stores rows at f16 and int8, vector reads flat float32, f16, int8 or uint8 input as float32 rows, and bench reads the standard ANN corpora. No I/O anywhere but bench.
Index ¶
- Constants
- Variables
- func ApplyCentroidDeltas(base [][]float32, deltas ...[]CentroidUpsert) ([][]float32, error)
- func Centroid(vecs [][]float32, dims int, spherical bool) ([]float32, float64)
- func CosineSim(a, b []float32) float32
- func DecodeCentroids(data []byte, dims int) ([][]float32, error)
- func DefaultNprobe(k int) int
- func Dot(a, b []float32) float32
- func Dots(q, block, out []float32)
- func EncodeCentroidDelta(entries []CentroidUpsert) []byte
- func EncodeCentroids(cs [][]float32) []byte
- func HoodK(total int) int
- func HoodSize(total int) int
- func L2Sq(a, b []float32) float32
- func MeanDistance(vecs [][]float32, c []float32) float64
- func MergeBelow(total int) int
- func MergeOwed(stats []ClusterStat) bool
- func MergeTargets(stats []ClusterStat, centroids [][]float32, busy func(i int) bool, n int) [][2]int
- func Normalize(v []float32)
- func RoundSqrt(total int) int
- func Score(metric Metric, q, v []float32) float32
- func SplitAbove(total int) int
- func TotalCount(stats []ClusterStat) int
- type CentroidUpsert
- type ClusterStat
- type DefaultPolicy
- type Dense
- type DenseEmbedding
- type DenseEncoder
- type Embedding
- type EmbeddingBatch
- type Encoder
- type FloatTree
- func (t *FloatTree) ApplyCentroidDeltas(deltas [][]CentroidUpsert) error
- func (t FloatTree) Clone() FloatTree
- func (t FloatTree) Dims() int
- func (t FloatTree) EvaluationsBeam(q []float32, beam, probe int) ([]int, int)
- func (t FloatTree) EvaluationsBeamI8Work(q []float32, beam, probe int) ([]int, TreeWork)
- func (t FloatTree) Height() int
- func (t FloatTree) Leaf(id int) []float32
- func (t FloatTree) Leaves() int
- func (t FloatTree) MarshalBinary() ([]byte, error)
- func (t FloatTree) Nearest(q []float32, probe int) []int
- func (t *FloatTree) NewSearcher() *Searcher
- func (t *FloatTree) QuantizeI8()
- func (t *FloatTree) Truncate(n int) error
- func (t *FloatTree) Upsert(id int, v []float32) error
- type Metric
- type Policy
- type Searcher
- type Tree
- type TreeWork
Examples ¶
Constants ¶
const ( MergeMax = 3 // HoodTarget is the vectors-per-neighborhood the sizing rule aims at, // the one constant that keeps hood size constant in N. Three things are // proportional to it and they pull opposite ways: candidates scored per // query is nprobe x HoodTarget, pack bytes per hood is HoodTarget x dims // x 4 (98 KiB at 128 dims: one object read and the unit a cache // evicts), and the centroid set both the query and the build must scan // is N/HoodTarget. // // The sizing rule aims at 196 rows, a soft target with headroom under // MaxHoodRows: a hood born at the hard cap splits again at its first // growth, and that churn was half the rows a backlog ingested. HoodTarget = 196 // MaxHoodRows is the hard ceiling on live rows in a published dense // hood (DefaultPolicy.MaxHoodRows); the caller's capacity pass enforces it // beyond the geometric splits. MaxHoodRows = 256 // CandidateBudget is how many candidates a default query is allowed to // score. 100,000 is what the sqrt-sized index spent at 1M for recall // 0.968, so the default is the old default, made constant in N. CandidateBudget = 100_000 )
Variables ¶
var ErrCorrupt = errors.New("ivfq: corrupt")
ErrCorrupt wraps every decode failure of a centroid set or delta.
Functions ¶
func ApplyCentroidDeltas ¶ added in v0.4.0
func ApplyCentroidDeltas(base [][]float32, deltas ...[]CentroidUpsert) ([][]float32, error)
ApplyCentroidDeltas folds deltas, oldest first, over a base set. The base slice is not mutated; its vectors are shared. A slot past the end of the set (a gap) is corruption: appends are contiguous by construction.
func Centroid ¶ added in v0.4.0
Centroid is the mean of the dims-wide vectors (spherical: normalized) and their mean distance to it; nil for none. Vectors of another width are skipped.
func CosineSim ¶
CosineSim returns cosine similarity (higher = more similar). Zero vectors score 0, and so do vectors so small that their float32 squared norms underflow (coordinates about 1e-23 or below), with growing error on the way there; Dense's cosine sums such vectors in float64 instead.
func DecodeCentroids ¶ added in v0.4.0
DecodeCentroids reads what EncodeCentroids wrote, every centroid dims wide.
func DefaultNprobe ¶
DefaultNprobe is how many hoods a query probes when the caller does not name a number and no recall controller has tuned the index. It is also where a recall controller starts and what its ceiling is a multiple of, so it is a starting point rather than the last word. Two bounds, and the smaller wins:
max(budgetNprobe, k/32) the FLOOR: a constant candidate budget, raised
to a fixed fraction of the index once that is
bigger, because a constant budget does not hold
recall (see recallProbeDiv).
max(16, k/4) the CEILING: never read more than a quarter of
the hoods by default once there are enough of
them to matter.
The ceiling exists because the budget alone makes the default an EXACT scan just below its own size: a 100,000-vector index has 511 hoods and the budget asks for 511, so the default would read every one, for recall the index does not need. The ceiling reads 127 there. Above ~400,000 vectors the ceiling is never the binding bound. Below 64 hoods it floors at 16, so an index of up to 16 hoods (3,136 vectors) still probes everything and answers exactly.
func Dot ¶
Dot returns the inner product. With precomputed squared norms it gives a squared distance without the sqrt L2Sq pays: |a-b|^2 = |a|^2 + |b|^2 - 2 a.b. The subtraction loses a few low bits when a and b are much longer than their difference, so callers rank with it; they do not report it.
func Dots ¶
func Dots(q, block, out []float32)
Dots sets out[r] to Dot(q, block[r*len(q):(r+1)*len(q)]) for every row of block, bit for bit, in one call.
func EncodeCentroidDelta ¶ added in v0.4.0
func EncodeCentroidDelta(entries []CentroidUpsert) []byte
EncodeCentroidDelta writes upserts as: magic, dims, count, then per entry the slot and the vector. The dims are carried so a delta applied to the wrong field fails on its header, not on a misaligned float.
func EncodeCentroids ¶ added in v0.4.0
EncodeCentroids writes a little-endian uint32 count, then each centroid's float32 values.
func HoodK ¶
HoodK is the sizing rule: k = ceil(total / HoodTarget), so hood size is constant in N and hood COUNT carries the growth. Under round(sqrt(total)) both count and size grow as sqrt(N), and candidates per query therefore grow linearly in N. The two rules agree up to 272 vectors; HoodK is no larger up to HoodTarget² (38,416) and larger above it, by design.
func HoodSize ¶
HoodSize is the per-hood target HoodK implies at this total: HoodTarget once the index is big enough to want more than hoodFloor hoods, and total/k below that. Split and merge are stated against THIS, not against HoodTarget directly, so the small-index floor does not make every hood look tiny and merge the index into one pack.
func MeanDistance ¶ added in v0.4.0
MeanDistance is the mean Euclidean distance from c to the vectors as wide as c; 0 for none.
func MergeBelow ¶
MergeBelow is the hood size under which a hood is a wasted probe slot and should be absorbed by its nearest neighbor. Never below MergeMax, so singleton hoods merge at any size.
func MergeOwed ¶ added in v0.4.0
func MergeOwed(stats []ClusterStat) bool
MergeOwed reports an empty cluster (reclaim) or a tiny one with room somewhere to merge into. MergeTargets refuses a merge past the split trigger, so a tiny no cluster has room for owes nothing: counting it would buy a rebalancing cycle that declines every time.
func MergeTargets ¶ added in v0.9.0
func MergeTargets(stats []ClusterStat, centroids [][]float32, busy func(i int) bool, n int) [][2]int
MergeTargets plans up to n merges at once: pairs of a tiny cluster and the nearest cluster to absorb it, the smallest tinies first, each tiny merging into its nearest neighbour when that neighbour stays at or under the split trigger with its rows. A merge past the trigger undoes the split that made the tiny, and the next cycle splits the host again: a lopsided 2-means split leaves a child under MergeBelow, the child's nearest cluster is its sibling, and the layout alternates split and merge on every cycle, forever. A tiny with no such neighbour stays until it grows. The size trigger is the one mirrored: a merge can still widen a host past the radius trigger.
No cluster is in two pairs, and none busy reports (nil: none) is in any: a tiny whose nearest neighbour is busy or already paired waits for a later call rather than taking its second nearest. centroids[i] is stats[i]'s centroid; pairs index stats as {tiny, host}. At most mergeTries distance scans (k × dims each) per pair wanted; they run on GOMAXPROCS goroutines, a batch of tinies per pass over the centroids.
func Normalize ¶
func Normalize(v []float32)
Normalize scales v to unit length in place. A zero-norm v is left as is.
func RoundSqrt ¶
RoundSqrt is round(√total), the k rule HoodK replaced: about √N neighborhoods of about √N vectors. HoodK keeps it as its small-index floor.
func Score ¶
Score is q against v under metric as a "higher is better" score: the negated squared distance for L2, the similarity for Cosine, the inner product for InnerProduct. An unknown Metric is a programming error and panics.
func SplitAbove ¶
SplitAbove is the band's MAXIMUM: the hood size past which the policy owes a split (SplitTarget's size trigger, 1.4x the target). It is stated here rather than inlined at the trigger because a rewrite that leaves a hood above this may split it inside the rewrite, the way SPFresh's LIRE splits a posting inside the insert that overflowed it, and both readers of the rule have to agree on the same number. 273 at a million vectors.
func TotalCount ¶
func TotalCount(stats []ClusterStat) int
TotalCount sums a stats slice — the live vector count the split and merge thresholds are stated against. Both triggers are relative to the size the sizing rule wants at THIS total, so neither needs the policy to be told N.
Types ¶
type CentroidUpsert ¶ added in v0.4.0
CentroidUpsert is one entry of a centroid delta: the vector now at slot ID, which is either an existing slot (a recentred cluster) or one past the last (a cluster a split added), or, with a nil Vec, the set cut to its first ID slots (the last entry of a delta, after its upserts). A caller that drops a cluster moves the last one into its slot and cuts the end, so a merge is two entries and not a full set.
func CentroidDelta ¶ added in v0.4.0
func CentroidDelta(prev, next [][]float32, limit int) ([]CentroidUpsert, bool)
CentroidDelta reports the upserts that turn prev into next when next keeps every slot of prev in place and only replaces or appends at most limit slots. Callers pass max(2, len(prev)/16): small enough that a delta stays cheap to apply on every load, and at least two so a split always qualifies. ok=false means write a full set: slots moved or vanished, or more than limit changed.
func DecodeCentroidDelta ¶ added in v0.4.0
func DecodeCentroidDelta(data []byte, dims int) ([]CentroidUpsert, error)
DecodeCentroidDelta reads what EncodeCentroidDelta wrote. Like DecodeCentroids it grows with bytes actually read, so a lying count dies on its first truncated entry instead of sizing an allocation.
type ClusterStat ¶
ClusterStat is one hood as its index records it. Count is the number of vectors the hood holds and Radius the mean distance from those members to its centroid, both measured by whatever last rewrote the hood, so both are exact and free to read. Radius == 0 means either "every member is the same point" or "emptied, awaiting reclaim"; either way it is not splittable evidence. Hits is query heat since the last cycle, and is 0 on a detached cycle.
type DefaultPolicy ¶
type DefaultPolicy struct{}
DefaultPolicy is the one shipped Policy. SplitTarget answers with one hood, chosen by size and then by radius.
func (DefaultPolicy) MaxHoodRows ¶ added in v0.16.0
func (DefaultPolicy) MaxHoodRows() int
MaxHoodRows opts this policy into a hard publication cap (MaxHoodRows). Engines without capacity enforcement may still temporarily exceed it.
func (DefaultPolicy) SplitTarget ¶
func (DefaultPolicy) SplitTarget(clusters []ClusterStat) (int, bool)
type Dense ¶ added in v0.17.0
Dense is an EmbeddingBatch of rows stored as T and decoded to float32 to score. NewDense[T] is its encoder for BuildTree.
float32 rows are kept exactly. float16 rows are rounded to the nearest IEEE binary16 value; a coordinate that rounds past ±65504 (|x| ≥ 65520) is an error, not an infinity. int8 and uint8 rows are codes on one affine scale per block, because tree means are fractional: the block's [min, max] coordinate range maps onto all 256 codes, scale = (max-min)/255 and offset = min - scale*(T's minimum), a coordinate x is stored as round((x-offset)/scale), halves away from zero, clamped to T's range, and decodes to offset + scale*code, within scale/2 of x up to float32 rounding. A block whose coordinates are all equal decodes them exactly.
Scores are of the decoded rows, not the coordinates before encoding, exactly as a Dense[float32] of the decoded rows would score them: -(‖q‖² + ‖row‖² - 2·q·row) for L2, from float32 q·row and squared norms combined in float64 (FloatTree's ranking distance negated); q·row for InnerProduct; and q·row/(‖q‖‖row‖) from the same terms for Cosine, except that a row or query whose squared norm is under 2⁻⁶⁰ is summed wholly in float64, so a tiny nonzero vector is not mistaken for zero. Cosine is 0 when either vector is exactly zero.
func NewDense ¶ added in v0.17.0
NewDense encodes rows, which must be nonempty, equally wide, at least one-dimensional and finite, and each row as encoded must have a finite float32 squared norm (FloatTree's rule: no coordinate past about 1.8e19). It copies them and keeps no float32 copy unless T is float32.
func (Dense[T]) ScoreAll ¶ added in v0.17.0
ScoreAll implements EmbeddingBatch for a dense query, a DenseEmbedding of any scalar, under L2, Cosine or InnerProduct. It reads a float32 query in place and decodes any other, and a non-float32 block a row at a time, into scratch of its own. A finite query far from a row can overflow to an infinite score, which is an error.
type DenseEmbedding ¶ added in v0.17.0
DenseEmbedding is row i of a Dense[T], from Dense.At: a read-only view that keeps the block, with its scale and offset, alive. It is also the dense query every Score and ScoreAll in this module takes; to score a []float32 q, use NewDense[float32]([][]float32{q}) and At(0), once per query: At allocates its interface value on every call.
func (DenseEmbedding[T]) Decode ¶ added in v0.17.0
func (e DenseEmbedding[T]) Decode(dst []float32) error
Decode copies the row's Dims decoded coordinates into dst, which must be at least that long, and leaves dst[Dims:] as it was. The values are what the block scores: float16 decoded as IEEE binary16, int8 and uint8 as offset + scale*code. Decode keeps nothing of dst, and dst never aliases the block.
func (DenseEmbedding[T]) Dims ¶ added in v0.17.0
func (e DenseEmbedding[T]) Dims() int
Dims is the row's width.
type DenseEncoder ¶ added in v0.17.0
DenseEncoder is the Encoder from rows of S to Dense[T] blocks. Encode reads S's values as float32 (float16 decoded as IEEE binary16), then encodes them as NewDense[T] does, a row at a time: it borrows rows only for the call, keeps nothing of them, and never builds a float32 copy of the whole input.
type Embedding ¶ added in v0.17.0
Embedding is one vector in some representation: a row of a Dense block (DenseEmbedding), of a rabitq.Block, or of any other EmbeddingBatch.
Score is query scored against the receiver, the stored target, under metric, higher is better: the negated squared distance for L2 (up to rounding, so a row equal to the query may score just above 0), the similarity for Cosine (0 when either vector is zero), the inner product for InnerProduct. A representation may score an estimate (RaBitQ does). It returns an error for a query of another width, a query representation or metric the receiver does not score, or a non-finite result. Every receiver in this module takes a dense query (DenseEmbedding of any scalar, the value At returns, not a pointer to it) and no other; none asks the query to score itself instead. Score neither changes nor retains query.
type EmbeddingBatch ¶ added in v0.17.0
type EmbeddingBatch interface {
Len() int
Dims() int
At(i int) Embedding
ScoreAll(query Embedding, metric Metric, dst []float32) error
}
EmbeddingBatch is Len embeddings of one width held together, scored together.
At returns row i as an Embedding: a read-only view that keeps the batch (and how to read it) alive, never shared scratch. It panics, as slice indexing does, when i is not a row.
ScoreAll sets dst[i], for every i < Len(), in row order, to what At(i).Score(query, metric) returns, up to float rounding, and never writes dst[Len():]. It fails as Score does, and when dst is shorter than Len(); after an error dst[:Len()] may be partly written and means nothing. It does not change query, retains neither query nor dst, and dst must not overlap query's or the batch's storage. A batch does not change once built: concurrent ScoreAll calls are safe, each with its own dst.
type Encoder ¶ added in v0.17.0
type Encoder[S vector.Scalar, B EmbeddingBatch] interface { Encode(rows vector.Slice[S]) (B, error) }
Encoder encodes rows of S into a block B: DenseEncoder[S, T] makes Dense[T] blocks, rabitq.BlockEncoder[S] rabitq.Blocks, from any source scalar S. Encode borrows rows read-only for the call and returns a block that owns its data, rows in input order; rows must not change during the call.
BuildTree does not take an Encoder: a tree's internal rows are fractional means held as [][]float32, so its encoder is NewDense[T] or a closure over rabitq.NewBlock.
type FloatTree ¶ added in v0.17.0
type FloatTree struct {
// contains filtered or unexported fields
}
FloatTree is a deterministic hierarchy over a set of float32 leaf centroids, kept exactly: it is the tree with Leaf, Upsert, Truncate, Clone and a wire format (MarshalBinary, UnmarshalTree). Tree is the immutable one whose nodes hold caller-encoded centroid blocks.
func Build ¶
Build constructs a fanout-ary hierarchy. Its fixed seeds make identical inputs deterministic; fanout values below two are promoted to two. Every centroid must have the first one's length and a finite squared norm, as Upsert requires, or Build returns an error. A cancelled ctx returns its error and no tree.
Example ¶
Route a query to its nearest cluster centroids.
package main
import (
"context"
"fmt"
"github.com/axiomhq/ivfq"
)
func main() {
centroids := [][]float32{{0, 0}, {10, 0}, {0, 10}, {10, 10}}
tree, err := ivfq.Build(context.Background(), centroids, 2)
if err != nil {
panic(err)
}
fmt.Println(tree.Nearest([]float32{9, 1}, 1))
}
Output: [1]
func UnmarshalTree ¶
UnmarshalTree decodes MarshalBinary output. Counts are checked against the bytes remaining before they size an allocation, and indices against the encoder's invariants: in range, the root is node zero, every child numbered after its parent (Build appends a node before recursing into its children, which is what makes traversal finite), every other node referenced by exactly one parent, every leaf owned by one node, and no node both branches and holds leaves.
func (*FloatTree) ApplyCentroidDeltas ¶ added in v0.17.0
func (t *FloatTree) ApplyCentroidDeltas(deltas [][]CentroidUpsert) error
ApplyCentroidDeltas upserts deltas, oldest first, into t in place. An error leaves t with the entries before it applied, so apply to a Clone when t must survive a bad delta.
func (FloatTree) Clone ¶ added in v0.17.0
Clone returns a deep copy of the tree: every centroid, child and leaf list, scan block, and norm slice is duplicated, and the clone's leaves address the clone's blocks. Neither tree can observe the other's Upsert: a decoded tree sits in a shared cache behind concurrent searches, so a caller that means to mutate clones first and swaps the result in.
func (FloatTree) EvaluationsBeam ¶ added in v0.17.0
EvaluationsBeam is Nearest with the number of centroid distance evaluations and the beam set apart from probe (Nearest's beam is probe): the search keeps beam nodes per level and ranks every leaf under them, so it scans every leaf only once beam covers every level's width. Leaves are ranked exactly; a narrower beam can only miss a leaf under a node it dropped. beam may be smaller than probe, and the result is still the probe nearest leaves the beam reached.
func (FloatTree) EvaluationsBeamI8Work ¶ added in v0.17.0
EvaluationsBeamI8Work is EvaluationsBeam, the same leaves in the same order, with the leaf scan read through the holders' int8 copies (QuantizeI8). The beam over internal nodes is EvaluationsBeam's own, in float32, so it visits the same holders. Each scanned leaf gets an int8 distance and an exact bound on its error,
|<q,c> - <q~,c~>| <= ||q|| ||c - c~|| + ||q - q~|| ||c~||
and its float32 distance is computed, as EvaluationsBeam computes it, only for the probe nearest by int8 and for any other leaf whose lower bound is within the probe-th float32 distance so far. TreeWork counts both kinds of distance. A tree without its int8 copies (not quantized, or changed since) is searched by EvaluationsBeam.
func (FloatTree) Height ¶ added in v0.17.0
Height returns the number of node levels, including the root and leaves.
func (FloatTree) Leaf ¶ added in v0.17.0
Leaf returns leaf id's centroid, aliasing the tree's own storage: read only.
func (FloatTree) Leaves ¶ added in v0.17.0
Leaves is the number of leaf centroids the tree ranks over.
func (FloatTree) MarshalBinary ¶ added in v0.17.0
MarshalBinary encodes the hierarchy and leaf vectors in a versioned format.
func (FloatTree) Nearest ¶ added in v0.17.0
Nearest returns up to probe leaf centroid indices, nearest first.
func (*FloatTree) NewSearcher ¶ added in v0.17.0
NewSearcher returns a Searcher over t. t must not change while the Searcher is in use.
func (*FloatTree) QuantizeI8 ¶ added in v0.17.0
func (t *FloatTree) QuantizeI8()
QuantizeI8 gives every leaf holder an int8 copy of its leaves for EvaluationsBeamI8Work: a quarter of the bytes the leaf scan reads, which at 768 dimensions was 12.7 MB a query. It is derived, never serialized, and dropped by Clone and by any change to the tree (Upsert, Truncate), after which EvaluationsBeamI8Work reads the float32 leaves until QuantizeI8 runs again. It writes t, so call it before t is shared.
func (*FloatTree) Truncate ¶ added in v0.17.0
Truncate cuts the tree to its first n leaves, each later leaf detached from its holder. Internal centroids stay, as they do under Upsert, and a holder may be left empty; the next Build rebalances.
func (*FloatTree) Upsert ¶ added in v0.17.0
Upsert replaces leaf id's centroid with v, or appends v as a new leaf when id equals the number of leaves; any other id is an error, since appends must stay contiguous, and so is a vector whose squared norm is not a finite float32 (a NaN or infinite coordinate, or a huge one). The height never changes and the result round-trips through MarshalBinary and UnmarshalTree.
A replace moves the leaf to the holder nearest to v (replace), so a slot refilled with a far centroid stays reachable. Internal centroids are deliberately not recomputed: the beam walks a handful of candidates per level, and holders are ranked by their means, which drift negligibly over a run of upserts. Recentring is what the next full Build is for.
An append descends the hierarchy the way Nearest does (beam = fanout) to find the holder whose centroid is nearest to v, appends the leaf there, and gives that holder a fresh block — holder blocks are sub-slices of the one leaf arena, so growing in place would trample a neighbouring hood — while re-pointing the holder's leaves at the new block. A holder is allowed to grow past the fanout: search scans every leaf of a visited holder, so correctness holds and quality degrades slowly; rebuild once enough upserts have accumulated.
type Metric ¶
type Metric int
Metric is the distance a field is scored with. The zero value is L2.
func ParseMetric ¶ added in v0.5.0
ParseMetric is the inverse of Metric.String: "l2", "cosine" or "ip".
func (Metric) MarshalText ¶ added in v0.5.0
MarshalText implements encoding.TextMarshaler, so a Metric reads and writes as its name in JSON and other text configs.
func (*Metric) UnmarshalText ¶ added in v0.5.0
UnmarshalText implements encoding.TextUnmarshaler.
type Policy ¶
type Policy interface {
// Bootstrap: no index exists and total is the live vector count.
// ok=false leaves the index unbuilt this cycle. The build that follows
// is the ONE pass over all N vectors the design allows.
Bootstrap(total int) (k int, ok bool)
// SplitTarget: consulted AFTER the append pass with post-append counts.
SplitTarget(clusters []ClusterStat) (id int, ok bool)
}
Policy implementations must be safe for concurrent use; the shipped policies are stateless.
Every trigger past Bootstrap is stated on []ClusterStat and nothing else, and that is the point: per-cluster counts and radii are what an index already holds, so consulting the policy costs O(k) arithmetic and no pass over the vectors. There is deliberately NO whole-index trigger: nothing a Policy answers can ask for a pass over every vector. Split, merge and reclaim are the whole vocabulary, and rebuilding an index is a caller's explicit decision.
type Searcher ¶ added in v0.5.0
type Searcher struct {
// contains filtered or unexported fields
}
Searcher is Nearest, Assign and TwoStageAssign with scratch that survives between calls: a warm Searcher allocates nothing per query, where FloatTree.Nearest allocates its result. It belongs to one goroutine; a bulk caller makes one per worker.
func (*Searcher) Assign ¶ added in v0.5.0
Assign is the leaf a beam-wide search ranks first, or -1 when the tree is empty or q is the wrong width: the same leaf Nearest(q, beam)[0] names.
func (*Searcher) Nearest ¶ added in v0.5.0
Nearest is FloatTree.Nearest: up to probe leaf ids, nearest first, in the same order. The slice is the Searcher's own and the next call overwrites it.
func (*Searcher) TwoStageAssign ¶ added in v0.5.0
TwoStageAssign ranks one leaf in two exact stages: a distance for every child of the root, then a distance for every leaf under the top subtrees, then returns the nearest such leaf, or -1.
On large trees the stage-two scan is the whole cost and Assign's beam pruning wins. Small trees are where this wins: with a narrow root fan a few subtrees cover nearly the whole set (at k = 977, a top-4 two-stage reached 99.1% agreement at 2.5x less wall per row on BIGANN). Choose by measured wall time, not by the evaluation count.
type Tree ¶
type Tree[B EmbeddingBatch] struct { // contains filtered or unexported fields }
Tree is FloatTree's hierarchy with every node's rows (child means for an internal node, leaf centroids for a leaf holder) held as one encoded block B: Tree[Dense[float32]], Tree[Dense[float16.Float16]], Tree[Dense[int8]], Tree[Dense[uint8]] or Tree[rabitq.Block]. A search scores each node's rows with B.ScoreAll under L2, whatever metric the field uses, and compares scores across blocks, so every block of one tree must score L2 on one scale. The tree keeps the topology and, per row, the child node or original leaf id; the blocks keep everything else. There is no float32 copy beside the blocks, so a lossy B cannot return a leaf's original centroid; a caller that needs them keeps its own.
A Tree is immutable and safe for concurrent searches.
func BuildTree ¶ added in v0.17.0
func BuildTree[B EmbeddingBatch](ctx context.Context, centroids [][]float32, fanout int, encode func(rows [][]float32) (B, error)) (Tree[B], error)
BuildTree builds the hierarchy Build builds over centroids, from the same float32 working coordinates (each internal row is the mean of the leaves beneath it), then calls encode once per node with that node's rows and keeps only the blocks it returns. The rows are read-only and valid only during the call: a block copies what it keeps. Centroids follow Build's rules and must be at least one-dimensional. An encoder error, or a block whose Len or Dims disagrees with its rows, fails the build; so does a ctx cancelled at any point before BuildTree returns, even over no centroids.
func (Tree[B]) Nearest ¶
Nearest returns up to probe leaf ids, nearest first, ties by lower id. It keeps the beam best nodes per level by their blocks' L2 scores and ranks every leaf of the holders it reaches, as FloatTree.EvaluationsBeam does; with B = Dense[float32] and no score overflowing, the result is EvaluationsBeam's. An empty tree, or a beam or probe below one, returns nil, nil without looking at q. Otherwise the first error a block's ScoreAll returns (a q of the wrong width or representation, an infinite score) is Nearest's, with no ids.
type TreeWork ¶ added in v0.16.0
type TreeWork struct {
Float32, Quantized int
}
TreeWork is a tree search's centroid work: Float32 is the float32 distances it computed, internal nodes included, and Quantized the int8 leaf distances it computed beside them. Every centroid a search scores is in one of the two.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package bench reads Big ANN benchmark corpora and ground truth (.u8bin/.i8bin/.fbin/.ibin), scores recall@k, and reads process CPU time.
|
Package bench reads Big ANN benchmark corpora and ground truth (.u8bin/.i8bin/.fbin/.ibin), scores recall@k, and reads process CPU time. |
|
Package codec stores float32 rows at reduced precision: IEEE binary16 (round to nearest even) and int8 (round half away from zero, saturating).
|
Package codec stores float32 rows at reduced precision: IEEE binary16 (round to nearest even) and int8 (round half away from zero, saturating). |
|
internal
|
|
|
simd
Package simd holds the numeric kernels every ivfq package scores with: the float32 distances, the block dot product the centroid tree ranks with, the 1-bit popcount products, the Walsh-Hadamard rotation and the quantizers behind rabitq, and the int8 codec.
|
Package simd holds the numeric kernels every ivfq package scores with: the float32 distances, the block dot product the centroid tree ranks with, the 1-bit popcount products, the Walsh-Hadamard rotation and the quantizers behind rabitq, and the int8 codec. |
|
Package kmeans fits centroids for an IVF index: sampled greedy k-means++ with one parallel assignment pass, two-level above TwoLevelK, and the size-floored 2-means a cluster split uses.
|
Package kmeans fits centroids for an IVF index: sampled greedy k-means++ with one parallel assignment pass, two-level above TwoLevelK, and the size-floored 2-means a cluster split uses. |
|
Package rabitq is the 1-bit candidate codec of an IVF index: RaBitQ (Gao & Long, SIGMOD 2024, arXiv:2405.12497).
|
Package rabitq is the 1-bit candidate codec of an IVF index: RaBitQ (Gao & Long, SIGMOD 2024, arXiv:2405.12497). |
|
Package rank orders scored hits: score descending, NaN last, ties by id ascending.
|
Package rank orders scored hits: score descending, NaN last, ties by id ascending. |
|
Package vector is the typed input shape for dense rows: one flat, row-major buffer of a supported scalar type and its width.
|
Package vector is the typed input shape for dense rows: one flat, row-major buffer of a supported scalar type and its width. |