SIMD support for Scalar Quantisation

[abdelr]

Describe your feature request

When we use Scalar Quantisation, there are two settings where we need to calculate distances. During indexing, required by the pruning heuristic, we need to calculate distances between compressed vectors. During querying, we need to calculate the distance from the uncompressed query vector to the compressed indexed vectors.
A compressed vector is represented by a sequence of bytes. Each byte been the code that approximates the original float32 in the corresponding dimension. The code is generated as:

byte(math.Floor(float64((x - b) * codes / a)))

Where a and b are the global range and min of the variables you are encoding and codes stands for the amount of codes you want to generate (default to 256, meaning we use a full byte). Similarly, the original value could be approximated from de code as:

x*a/codes+b

Based on the code before, we can infer the distance calculations for dot and l2squared directly in the compressed space as follows:

dot

compressed to compressed

$$\sum_{i=1}^n \left( x_i*a/codes+b \right)* \left( y_i*a/codes+b \right)$$ $$a^2/codes^2\sum_{i=1}^n \left( x_i*y_i \right)+a*b/codes+\sum_{i=1}^n\left(x_i\right)+\sum_{i=1}^n\left(y_i\right)+ib^2$$

Most parts we can pre-calculate except

$$\sum_{i=1}^n \left( x_i*y_i \right)$$

which we could implement very efficiently using SIMD.

uncompressed to compressed

Similarly in the case we calculate distance from compressed to uncompressed vectors we would have:

$$\sum_{i=1}^n x_i* \left( y_i*a/codes+b \right)$$

where x is a float32 array (uncompressed). We could derive the expression:

$$a/codes\sum_{i=1}^n \left( x_i*y_i \right)+b\sum_{i=1}x_i$$

In this case we could calculate the

$$\sum_{i=1}x_i$$

once per vector when creating the distance but still need the SIMD version of

$$\sum_{i=1}^n \left( x_i*y_i \right)$$

l2squared

compressed to compressed

$$\sum_{i=1}^n \left(\left( x_i*a/codes+b \right)- \left( y_i*a/codes+b \right) \right)^2$$ $$a^2/codes^2*\sum_{i=1}^n \left( x_i- y_i \right)^2$$

so we need the SIMD implementation of:

$$\sum_{i=1}^n \left( x_i- y_i \right)^2$$

uncompressed to compressed

$$\sum_{i=1}^n \left(x_i- \left( y_i*a/codes+b \right) \right)^2$$

to_be_completed_soon

Code of Conduct

• I have read and agree to the Weaviate's Contributor Guide and Code of Conduct