Documentation
¶
Overview ¶
Package ivfq is inverted-file clustering plus quantization: the two halves of an IVF index in the FAISS sense ("IVF + quantizer").
The clustering half partitions vectors into hoods: k-means (plain, spherical, and sample-trained), the centroid Tree and its Nearest lookup, splits and merges, and the rebalancing Policy. The quantization half gives every hood a candidate column and an exact rerank: Vector[T], Rows, Sparse, Rotation, Quantizer, the 1-bit RaBitQ Code and its Scorer, and the SIMD kernels under them (Dot, L2Sq, CosineSim, Dots, the bit products). LateInteractionScore scores multi-vector documents token by token; package rank selects and fuses the results. No I/O.
Index ¶
- Constants
- func AppendF16(dst []byte, v []float32) []byte
- func AppendI8(dst []byte, v []float32) []byte
- func CosineSim(a, b []float32) float32
- func DecodeF16(b []byte) []float32
- func DecodeF16Into(dst []float32, b []byte)
- func DecodeI8(b []byte) []float32
- func DecodeI8Into(dst []float32, b []byte)
- func DefaultNprobe(k int) int
- func Dot(a, b []float32) float32
- func Dots(q, block, out []float32)
- func EncodeF16(v []float32) []byte
- func EncodeI8(v []float32) []byte
- func HoodK(total int) int
- func HoodSize(total int) int
- func L2Sq(a, b []float32) float32
- func LateInteractionScore(metric string, query, document [][]float32) float32
- func MaxTrainN() int
- func MergeBelow(total int) int
- func Nearest(centroids [][]float32, v []float32) int
- func Normalize(v []float32)
- func ResetMaxTrainN()
- func RoundF16(v []float32) []float32
- func RoundI8(v []float32) []float32
- func RoundSqrt(total int) int
- func RunSampled(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)
- func RunSampledBudget(ctx context.Context, vecs [][]float32, k, iters int, seed int64, bytes int) ([][]float32, []int, error)
- func RunSampledSpherical(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)
- func RunSampledSphericalBudget(ctx context.Context, vecs [][]float32, k, iters int, seed int64, bytes int) ([][]float32, []int, error)
- func SampleSize(k int) int
- func SampleSizeForBudget(k, dims, bytes int) int
- func Score(metric string, q, v []float32) float32
- func Seed(parts ...string) uint64
- func Split(ctx context.Context, vecs [][]float32, seed int64) ([][]float32, []int, error)
- func SplitAbove(total int) int
- func SplitSpherical(ctx context.Context, vecs [][]float32, seed int64) ([][]float32, []int, error)
- func TotalCount(stats []ClusterStat) int
- func ValidateLateInteraction(tokens [][]float32, dims int) error
- type ClusterStat
- type Code
- type Codes
- type DefaultPolicy
- type Metric
- type Number
- type Options
- type Policy
- type Quantizer
- func AppendRows(c Quantizer, vectors [][]float32) (Quantizer, error)
- func Empty(centroid []float32, opts Options) (Quantizer, error)
- func Quantize(vectors [][]float32, opts Options) (Quantizer, error)
- func UnmarshalBinary(data []byte) (Quantizer, error)
- func UnmarshalBinaryBorrowed(data []byte) (Quantizer, error)
- func (c Quantizer) MarshalBinary() ([]byte, error)
- func (c Quantizer) Retained() int
- func (c Quantizer) Rows() int
- func (c *Quantizer) SameFrame(o *Quantizer) bool
- func (c Quantizer) Score(q Query, row int) float32
- func (c Quantizer) ScoreAndBound(q Query, row int) (score, bound float32)
- func (c *Quantizer) Scorer(q Query) Scorer
- func (c Quantizer) Select(rows []int) (Quantizer, error)
- func (c Quantizer) UpperBound(q Query, row int) float32
- type Query
- type Rotation
- type Rows
- type Scorer
- type Sparse
- type Tree
- func (t Tree) Assigner(beam int) func([]float32) int
- func (t Tree) Clone() Tree
- func (t Tree) Dims() int
- func (t Tree) Evaluations(q []float32, probe int) ([]int, int)
- func (t Tree) Height() int
- func (t Tree) Leaf(id int) []float32
- func (t Tree) Leaves() int
- func (t Tree) MarshalBinary() ([]byte, error)
- func (t Tree) Nearest(q []float32, probe int) []int
- func (t Tree) Ranker(probe int) func(q []float32, visit func(id int))
- func (t Tree) TwoStageAssigner(top int) func([]float32) int
- func (t Tree) TwoStageNearest(q []float32, top int) ([]int, int)
- func (t *Tree) Upsert(id int, v []float32) error
- type Vector
Constants ¶
const ( MergeMax = 3 // HoodTarget is the vectors-per-neighborhood the sizing rule aims at. // It is the ONE constant that makes a query's cost 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 (512 KiB at 128 dims, one S3 GET's worth and the // unit the byte cache evicts), and the centroid set both the query and // the build must scan is N/HoodTarget. // // 1024 was CHOSEN, not swept: it makes the 1M index 977 hoods against the // 1,000 the old rule gave, so the 1M measurements are a controlled A/B on // one corpus rather than a comparison of two different indexes. A sweep // over {512, 2048, 4096} at 1M is the obvious follow-up and has not been // run. The reasoning: fixed-size neighborhoods. HoodTarget = 1024 // 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 ¶
This section is empty.
Functions ¶
func DecodeF16Into ¶
DecodeF16Into decodes len(dst) values of b into dst.
func DecodeI8Into ¶
DecodeI8Into decodes len(dst) values of b into dst.
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 namespace. It is also where the controller starts and what its ceiling is a multiple of (engine/recall_tune.go), 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 made the default an EXACT scan just below its own size: a 100,000-vector index has 98 hoods and the budget asks for 98, so the default read every one — 4.42 ms measured, for recall the index did not need. The quarter it now reads there is 24 hoods: recall@10 1.000 at 1.12 ms, 24,641 candidates against 100,000. Above ~400,000 vectors the ceiling is never the binding bound and 1M and 10M are untouched. Below 64 hoods it floors at 16, which is at or above k for every namespace the bootstrap threshold allows, so a small namespace 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 — the same kernel sequence go-simd runs per row — in one call: a centroid tree ranks a node's hundred children at a time, and at 16 dimensions the call per child cost more than the arithmetic.
func EncodeF16 ¶
EncodeF16 stores v as little-endian IEEE binary16, round-to-nearest-even; out-of-range values become ±Inf (callers validate with float16.Fromfloat32(x).IsInf(0) before storing).
func EncodeI8 ¶
EncodeI8 rounds to the nearest integer, ties away from zero, and saturates to [-128,127]. This is an implementation choice because the public docs do not prescribe conversion of floating-point inputs to i8 storage.
func HoodK ¶
HoodK is the sizing rule: k = ceil(total / HoodTarget), so hood size is constant in N and hood COUNT carries the growth. It replaces round(sqrt(total)), under which both count and size grew as sqrt(N) and candidates per query therefore grew linearly in N. Identical to the old rule for total <= 256; larger for everything above, by design.
func HoodSize ¶
HoodSize is the per-hood target HoodK implies at this total: HoodTarget once the namespace 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-namespace floor does not make every hood look tiny and merge the index into one pack.
func L2Sq ¶
L2Sq returns squared euclidean distance. Squared preserves ranking and skips the sqrt. (floats has no squared form, so the sqrt is paid and undone — still 2.4x the scalar loop it replaced.)
func LateInteractionScore ¶ added in v0.3.0
LateInteractionScore sums each query token's best document-token score. Inputs must be validated nonempty matrices of the same width. In particular, a negative best match contributes its negative score, not zero.
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 the pre-existing "singleton hoods merge" behavior survives at any size.
func Normalize ¶
func Normalize(v []float32)
Normalize scales v to unit length in place. A zero-norm v (degenerate antipodal cluster mean) is left unnormalized.
func ResetMaxTrainN ¶
func ResetMaxTrainN()
func RoundF16 ¶
RoundF16 is DecodeF16(EncodeF16(v)), except that it returns v itself, allocating nothing, when every value already is an f16 value.
func RoundI8 ¶
RoundI8 is DecodeI8(EncodeI8(v)), except that it returns v itself, allocating nothing, when every value already is an i8 value — as every row read back from an i8 column is. -0 is not: it decodes as +0.
func RunSampled ¶
func RunSampled(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)
RunSampled fits k centroids on a deterministic random sample of at most SampleSize(k) vectors, then assigns EVERY vector in one parallel pass (assignAll). This is the only k-means the build runs at scale: with fixed-size hoods k = N/HoodTarget, so global Lloyd's would be O(N^2/S) per iteration — eleven passes of it at 10M is hours. Sampling collapses the iterated term to the sample and leaves exactly one O(N x k) pass.
Identical to Run when the sample covers the corpus, so small namespaces (and every existing test) get the full fit unchanged.
func RunSampledBudget ¶
func RunSampledSpherical ¶
func RunSampledSpherical(ctx context.Context, vecs [][]float32, k, iters int, seed int64) ([][]float32, []int, error)
RunSampledSpherical is RunSampled for cosine namespaces.
func SampleSize ¶
SampleSize is the training-set bound: NOTHING in a build may call Lloyd's with more vectors than this. It is the property that makes the build linear-ish in N — training is O(SampleSize(k) x k x dims) whatever N is, and the only pass that touches all N vectors is one assignment.
func SampleSizeForBudget ¶
SampleSizeForBudget additionally caps the training vectors by their raw float32 footprint. It never returns zero for a non-empty build.
func Seed ¶
Seed is the rotation seed a namespace's field uses: FNV-1a over the namespace and field names. Deriving it rather than drawing it keeps every hood of a field in ONE frame, so a query rotates once per hood and the cache above holds one entry — while two different fields, and two different namespaces, still get independent rotations. The value is written into every codes part anyway, so a reader never re-derives it and changing this function cannot strand existing packs.
func Split ¶
Split is 2-means: the cluster-split primitive. A cancelled ctx returns its error and no result, as Run.
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 hood no longer has to wait for a verb to learn it: a rewrite that leaves a hood above this splits 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. 1,432 at a million vectors.
func SplitSpherical ¶
SplitSpherical is Split's spherical counterpart.
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.
func ValidateLateInteraction ¶ added in v0.3.0
ValidateLateInteraction checks a nonempty matrix of finite, fixed-width tokens.
Types ¶
type ClusterStat ¶
ClusterStat is one hood as the manifest records it. Count is the number of vectors the hood's PACK holds and Radius the mean distance from those members to its centroid, both written by whichever verb last rewrote the hood — so both are exact, delete-aware by construction (a deleted id is removed from its pack in the cycle that deletes it), 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 Code ¶
type Code struct {
// Words is rows x ceil(dims/64) little-endian bit rows: bit j of row i
// is word[i*w + j/64] >> (j%64).
Words []uint64
// Centroid is the hood's own mean, in the ORIGINAL frame, subtracted
// before rotation. It is the codec's, not the manifest's: a patched
// hood's members drift from the centroid set they were filed under, and
// the estimator's accuracy is a function of how short the residuals
// are, so the codec carries the centroid it actually encoded against.
Centroid []float32
// Norms is ||o - c|| per row, and Aligns is <x_b, x> per row: the two
// scalars the estimator needs. Aligns is zeroRowAlign for a row whose
// vector has no direction at all (a zero vector in a cosine namespace),
// which scores 0 the way CosineSim scores it.
Norms []float32
Aligns []float32
// Seed is the rotation the bits live in (rotate.go). Stored rather than
// derived so a reader never has to agree with the writer about how a
// seed is computed.
Seed uint64
// Unit says the rows are unit vectors: cosine namespaces quantize the
// residual of the NORMALIZED vector, so the estimator's squared
// distance maps to cosine as 1 - d^2/2.
Unit bool
// contains filtered or unexported fields
}
Code is the 1-bit payload of a Codes. Rows are indexed the same way the int8 payload's are: by the hood's row order, which is the ids column's order, which is what the candidate pass labels a score with.
type DefaultPolicy ¶
type DefaultPolicy struct{}
DefaultPolicy is the one production policy. The Policy interface exists so tests can substitute a stub that names a verb unconditionally; there is no second shipped policy. SplitTarget is answered by a verb bounded by a single hood:
- SplitTarget: size, then radius, for the hood one verb from the band.
func (DefaultPolicy) SplitTarget ¶
func (DefaultPolicy) SplitTarget(clusters []ClusterStat) (int, bool)
type Options ¶
Options is what Encode needs beyond the vectors: the field's declared width (an empty hood still publishes a shaped column), the metric (cosine hoods encode unit vectors), and the rotation seed.
type Policy ¶
type Policy interface {
// Bootstrap: no index exists; total = live vector count from the winner
// scan. ok=false leaves the namespace unindexed this cycle. This 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: a ClusterStat slice is read straight out of the manifest, so consulting the policy costs O(k) arithmetic and no pass over the vectors. There is deliberately NO whole-index trigger any more — the drift-gated full recluster this interface used to carry (ReclusterK, with its IndexStats of additive and live counts) was the last thing in the engine that could decide, on its own, to touch all N vectors. It is gone, and so is the regional re-fit that briefly replaced it; split, merge and reclaim are the whole vocabulary, and an explicit recluster is the only verb that still rebuilds a whole index when a human asks for it.
type Quantizer ¶
type Quantizer struct {
Dims int
// Code is the payload. Non-nil for anything UnmarshalBinary returned.
Code *Code
}
Codes is one hood's candidate column: the bytes the probe wave moves and the kernel scores. There is ONE codec — RaBitQ 1-bit residuals (rabitq.go), dims BITS plus 8 bytes per row, with a bound that holds at boundConfidence — and this type is the seam the engine sees.
Until 2026-09-15 there were two, selected by Config.CandidateCodes, and a hood's payload said which one it held so mixed generations read. The per-vector symmetric int8 codec (DQC2) is gone: it cost dims BYTES plus 16 a row against 1-bit's dims bits plus 8, which on SIFT1M was 105.3 stored bytes a row against 27.8, and the one thing it bought — a bound that cannot be exceeded — is bought back where it is actually wanted by Query.Exact.
func AppendRows ¶
AppendRows returns a copy of the column with one freshly encoded row per vector, appended in order, encoded against the column's OWN centroid, seed and metric frame. The zero-vector rule carries over: a zero vector appended to a cosine column becomes a zeroRowAlign row.
It is the other half of copying codes between packs: the few rows that move INTO a split's new hood from a neighbouring one are re-encoded against the copied column's centroid, so the whole column stays one frame without re-quantizing the rows that were copied verbatim.
func Empty ¶
Empty returns a column with no rows around centroid, in opts' frame: what AppendRows grows one block at a time, so every block of a cluster is encoded against the cluster's own centroid rather than the mean of whichever rows happened to start the block.
func Quantize ¶
Quantize is the ONE door a hood's codes are written through. vectors are the hood's rows in id order, already at the precision the exact rerank will read them at.
func UnmarshalBinary ¶
UnmarshalBinary decodes MarshalBinary output. Everything a row's score and bound rest on is checked there (rabitq.go, unmarshalBits), because the candidate pass prunes the exact rerank with these values before any full vector is read.
func UnmarshalBinaryBorrowed ¶
UnmarshalBinaryBorrowed validates codes like UnmarshalBinary, but keeps scalar and bit rows in data. The caller must keep data immutable and alive.
func (Quantizer) MarshalBinary ¶
func (Quantizer) Retained ¶
Retained is what a decoded column holds in memory, for the byte cache's accounting.
func (Quantizer) Rows ¶
Count is how many code rows this column holds — one per vector the manifest counted, which is what CheckParts holds it to.
func (Quantizer) Score ¶
Score is the one-off form of Scorer.Score: it binds the query for a single row. Tests and oracles use it; the candidate pass does not, because the binding is O(dims).
func (Quantizer) ScoreAndBound ¶
ScoreAndBound is the one-off form of Scorer.ScoreAndBound.
func (Quantizer) Select ¶
Select returns a column holding only the rows at the given indexes, in that order, sharing the source column's centroid, seed and metric frame. Every per-row scalar and bit is copied verbatim, so a copied row decodes, scores and bounds exactly as it did in the source column.
This is the read-and-reassemble half of copying codes between packs: a split writes each half's rows out of the source hood's column instead of quantizing them again. A column is self-consistent around the ONE centroid its rows are residuals to, so rows may only be combined with rows of a column carrying that same centroid — that is what AppendRows is for.
type Query ¶
type Query struct {
Vector []float32
Metric string
// Exact drops the bound: every row's bound is +Inf, so the bound-pruned
// pass reads every row and the answer is exactly the top k over the
// probed hoods. It is how a caller buys back the certainty the 1-bit
// codec's probabilistic bound trades away.
Exact bool
// Sigmas overrides boundSigmas for the 1-bit codec (0 = the default).
// Tests measure coverage against it; the query path sets it from
// search.Config.BoundSigmas, which the bound-width sweep varies.
Sigmas float64
// contains filtered or unexported fields
}
Query is a vector prepared for scoring many rows: the cosine query norm is computed once here rather than per candidate.
type Rotation ¶
type Rotation struct {
// contains filtered or unexported fields
}
The rotation RaBitQ's error bound assumes: a uniformly random orthogonal transform, applied to every residual before it is sign-quantized. It is what makes the quantization error independent of the data's own axes — without it, a corpus whose energy sits in a few dimensions quantizes to a handful of distinct codes and the estimator's variance is whatever the corpus says it is, not O(1/sqrt(D)).
A materialized D x D matrix is out of the question at the dimensions this engine serves: building one is O(D^3) (3.6 GFLOP at 1536 dims), storing it is 9 MB, and applying it to every row of every hood at build time is D^2 per vector. So the rotation is a BUTTERFLY of Givens rotations: a few rounds, each one a random pairing of all D coordinates and a random angle per pair. Every factor is exactly orthogonal, so the product is exactly orthogonal at any D (no power-of-two padding, no code bits spent on a pad), it costs O(D log D) to apply, and it is reproducible from a seed — the pack stores the seed, not the matrix.
rounds is 3 + ceil(log2(D)): each round mixes disjoint pairs, so after log2(D) rounds of random pairings every coordinate has had a path to every other, and the three extra rounds are the mixing margin. The coverage test (TestBitBoundCoversAtItsConfidence, including its axis-aligned corpus) is what actually holds this number honest. Rotation is the butterfly of Givens rotations RaBitQ applies.
type Scorer ¶
type Scorer struct {
// contains filtered or unexported fields
}
Scorer binds one column to one query: the per-hood work the paper's estimator needs — the query's residual to THIS hood's centroid, rotated and quantized to four bit planes — which is O(dims) once per probed hood rather than once per row. The candidate pass builds one per hood and scores its rows through it.
A Scorer belongs to the goroutine that made it.
func (Scorer) Rebind ¶
Rebind is Scorer for a column in the same frame as the one s was built on (same centroid, rotation and metric): the query-side work is reused and only the rows change. A cluster of the LSM tier is many 64-row blocks encoded against one centroid, so a probe binds the query once per cluster rather than once per block. A column in another frame is bound afresh.
func (Scorer) ScoreAndBound ¶
ScoreAndBound is the candidate kernel: a higher-is-better estimate of the exact score, and a conservative upper bound on it. A row may be skipped by an exact top-k cutoff only when its bound is below the cutoff.
The bound is boundSigmas standard deviations of the RaBitQ estimator's error and holds at boundConfidence, so "exact within the probed hoods" is a recall guarantee rather than a certainty — unless Query.Exact is set, which is how a caller buys the certainty back.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a deterministic hierarchy over a set of leaf centroids.
func Build ¶
Build constructs a fanout-ary hierarchy. Its fixed seeds make identical inputs deterministic; fanout values below two are promoted to two. A cancelled ctx returns its error and no tree.
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 (Tree) Assigner ¶
Assigner ranks one leaf with the same beam traversal as Nearest. Each concurrent caller borrows its own reusable scratch; no per-row tree-sized allocations or unused top-k leaf sort are needed by bulk assignment.
func (Tree) Clone ¶
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 (Tree) Evaluations ¶
Evaluations is Nearest with the number of centroid distance evaluations.
func (Tree) MarshalBinary ¶
MarshalBinary encodes the hierarchy and leaf vectors in a versioned format.
func (Tree) Ranker ¶
Ranker is Nearest for bulk callers: each call visits the same leaves in the same order as Nearest(q, probe), on scratch borrowed from a pool the concurrent callers share. Nearest allocates its candidate buffer per call; a fold re-routing every member of its moved hoods through it allocated about 45 KB per row, 200 GB for one 4,096-hood fold (measured on a 4,096-cluster re-route).
func (Tree) TwoStageAssigner ¶
TwoStageAssigner ranks one leaf in two exact stages: a distance for every child of the root, then a distance for every leaf under the best top of them. The beam search prunes at every level, so on a tree deeper than the fan — k-means grouping is never balanced enough to keep one level under the fanout — a miss at any level loses the true centroid for good, and recall only comes back with the beam wide enough to be most of a brute scan. The two-stage search spends its whole budget on the one decision that can miss, which subtree, and is exact everywhere else: 3.2x fewer centroid evaluations than beam 16 at k = 9,766.
Measured, it is a wash for bulk routing: on real BIGANN rows the stage-two subtree scans gather their holders cold and give back the evaluation savings (97.0% exact agreement at top 8 against the beam's 96.8% at the same nanoseconds per row — BenchmarkAssignerBeam in tree_bench_test.go), so the maintainer's router keeps the beam. Small trees are where this wins: at k = 977 a top-4 two-stage reached 99.1% agreement at 2.5x less wall per row than beam 16, because the stage-one fan there is 10 wide and four subtrees cover nearly the whole set. Choose by the benchmark, not by the evaluation count.
func (Tree) TwoStageNearest ¶
TwoStageNearest is TwoStageAssigner's search with the picked leaf ids, nearest first, and the number of centroid distance evaluations returned — the pairing Nearest and Evaluations give the beam search.
func (*Tree) Upsert ¶
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. The height never changes and the result round-trips through MarshalBinary and UnmarshalTree.
A replace writes v into the slot the leaf's reference already aliases — index() made t.leaves[id] a sub-slice of the owning holder's block, so one copy serves both views — and refreshes that holder's norm. Internal centroids are deliberately not recomputed: a re-centred hood moves by a fraction of its radius, 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.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package rank orders scored hits: score descending, ties by id ascending.
|
Package rank orders scored hits: score descending, ties by id ascending. |
|
Package recall tunes an IVF index's two query knobs, the probe count and the rerank depth, from a sample of live queries.
|
Package recall tunes an IVF index's two query knobs, the probe count and the rerank depth, from a sample of live queries. |