Module list_bounds 

Cosine/Dot (MIPS) List Bounds (Task 3)

Provides computable upper bounds for cosine/dot similarity over IVF lists, enabling best-first probing and bound-based termination for non-L2 metrics.

Architecture

For cosine/dot similarity, we store spherical cap metadata per list:

• Centroid direction c (unit vector)
• Max angular deviation θ_max (or min dot to centroid)

Math/Algorithm

For normalized queries q, the upper bound on achievable similarity in list L is:

max_{v∈L} q·v ≤ cos(max(0, angle(q,c) - θ_max))

where:

• angle(q,c) = arccos(q·c)
• θ_max = max_{v∈L} arccos(v·c)

Bound evaluation is O(1) per list after precomputing q·c.

Usage

use sochdb_vector::list_bounds::{SphericalCapMetadata, ListBoundComputer};

// Build metadata during indexing
let metadata = SphericalCapMetadata::from_vectors(&vectors, centroid);

// At query time, compute bounds
let computer = ListBoundComputer::new(&query);
let bound = computer.upper_bound(&metadata);

Structs

L2ListMetadata

Metadata for L2 distance bounds (centroid + radius)

ListBound

Precomputed bounds for best-first list ordering

ListBoundComputer

Computes bounds for a query across multiple lists

SphericalCapMetadata

Spherical cap metadata for a list/partition

UnifiedListMetadata

Combined metadata supporting all metrics

Enums

DistanceMetric

Supported distance metrics with bound computation methods

Functions

normalize

Normalize a vector, returning new vector

normalize_inplace

Normalize a vector in-place