Struct Compensation 

#[repr(transparent)]
pub struct Compensation(pub f32);

A per-vector precomputed coefficient to help compute inner products.

To understand the use of the compensation coefficient, assume that we wish to compute the inner product between two scalar compressed vectors where the quantization has scale parameter a and centroid B (note: capital letters represent vectors, lower case letters represent scalars).

The inner product between a X = a * (X' + B) and Y = a * (Y' + B) where X' and Y' are the scalar encodings for X and Y respectively is:

P = <a * X' + B, a * Y' + B>
  = a^2 * <X', Y'> + a * <X', B> + a * <Y', B> + <B, B>
           ------    -----------   -----------   ------
              |           |             |           |
         Integer Dot      |        Compensation     |
           Product        |           for Y         |
                          |                    Constant for
                     Compensation               all vectors
                        for X

In other words, the inner product can be decomposed into an integer dot-product plus a bunch of other terms that compensate for the compression.

These compensation terms can be computed as the vectors are compressed. At run time, we can the return vectors consisting of the quantized encodings (e.g. X') and the compensation <X', B>.

Computation of squared Euclidean distance is more straight forward:

P = sum( ((a * X' + B) - (a * Y' + B))^2 )
  = sum( a^2 * (X' - Y')^2 )
  = a^2 * sum( (X' - Y')^2 )

This means the squared Euclidean distance is computed by scaling the squared Euclidean distance computed directly on the integer codes.

Distance Implementations

The following distance function types are implemented:

• CompensatedSquaredL2: For computing squared euclidean distances.
• CompensatedIP: For computing inner products.

Examples

The CompensatedVector has several named variants that are commonly used:

• CompensatedVector: An owning, indepndently allocated CompensatedVector.
• MutCompensatedVectorRef: A mutable, reference-like type to a CompensatedVector.
• CompensatedVectorRef: A const, reference-like type to a CompensatedVector.

use diskann_quantization::{
    scalar::{
        self,
        CompensatedVector,
        MutCompensatedVectorRef,
        CompensatedVectorRef
    },
};

use diskann_utils::{Reborrow, ReborrowMut};

// Create a new heap-allocated CompensatedVector for 4-bit compressions capable of
// holding 3 elements.
let mut v = CompensatedVector::<4>::new_boxed(3);

// We can inspect the underlying bitslice.
let bitslice = v.vector();
assert_eq!(bitslice.get(0).unwrap(), 0);
assert_eq!(bitslice.get(1).unwrap(), 0);
assert_eq!(v.meta().0, 0.0, "expected default compensation value");

// If we want, we can mutably borrow the bitslice and mutate its components.
let mut bitslice = v.vector_mut();
bitslice.set(0, 1).unwrap();
bitslice.set(1, 2).unwrap();
bitslice.set(2, 3).unwrap();

assert!(bitslice.set(3, 4).is_err(), "out-of-bounds access");

// Get the underlying pointer for comparision.
let ptr = bitslice.as_ptr();

// Vectors can be converted to a generalized reference.
let mut v_ref = v.reborrow_mut();

// The generalized reference preserves the underlying pointer.
assert_eq!(v_ref.vector().as_ptr(), ptr);
let mut bitslice = v_ref.vector_mut();
bitslice.set(0, 10).unwrap();

// Setting the underlying compensation will be visible in the original allocation.
v_ref.set_meta(scalar::Compensation(1.0));

// Check that the changes are visible.
assert_eq!(v.meta().0, 1.0);
assert_eq!(v.vector().get(0).unwrap(), 10);

// Finally, the immutable ref also maintains pointer compatibility.
let v_ref = v.reborrow();
assert_eq!(v_ref.vector().as_ptr(), ptr);

Constructing a MutCompensatedVectorRef From Components

The following example shows how to assemble a MutCompensatedVectorRef from raw memory.

use diskann_quantization::{
    bits::{Unsigned, MutBitSlice},
    scalar::{self, MutCompensatedVectorRef}
};

// Start with 2 bytes of memory. We will impose a 4-bit scalar quantization on top of
// these 4 bytes.
let mut data = vec![0u8; 2];
let mut compensation = scalar::Compensation(0.0);
{
    // First, we need to construct a bit-slice over the data.
    // This will check that it is sized properly for 4, 4-bit values.
    let mut slice = MutBitSlice::<4, Unsigned>::new(data.as_mut_slice(), 4).unwrap();

    // Next, we construct the `MutCompensatedVectorRef`.
    let mut v = MutCompensatedVectorRef::new(slice, &mut compensation);

    // Through `v`, we can set all the components in `slice` and the compensation.
    v.set_meta(scalar::Compensation(1.0));
    let mut from_v = v.vector_mut();
    from_v.set(0, 1).unwrap();
    from_v.set(1, 2).unwrap();
    from_v.set(2, 3).unwrap();
    from_v.set(3, 4).unwrap();
}

// Now we can check that the changes made internally are visible.
assert_eq!(&data, &[0x21, 0x43]);
assert_eq!(compensation.0, 1.0);

Tuple Fields

0: f32

Trait Implementations

impl Clone for Compensation

fn clone(&self) -> Compensation

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Compensation

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Compensation

fn default() -> Compensation

Returns the “default value” for a type.

impl Zeroable for Compensation

fn zeroed() -> Self

Calls zeroed.

impl Copy for Compensation

impl Pod for Compensation