Lucene102BinaryQuantizedVectorsFormat
The binary quantization format used here is a per-vector optimized scalar quantization. These ideas are evolutions of LVQ proposed in Similarity search in the blink of an eye with compressed indices by Cecilia Aguerrebere et al., the previous work on globally optimized scalar quantization in Apache Lucene, and Accelerating Large-Scale Inference with Anisotropic Vector Quantization by Ruiqi Guo et. al. Also see [ ]. Some of key features are:
Estimating the distance between two vectors using their centroid centered distance. This requires some additional corrective factors, but allows for centroid centering to occur.
Optimized scalar quantization to single bit level of centroid centered vectors.
Asymmetric quantization of vectors, where query vectors are quantized to half-byte (4 bits) precision (normalized to the centroid) and then compared directly against the single bit quantized vectors in the index.
Transforming the half-byte quantized query vectors in such a way that the comparison with single bit vectors can be done with bit arithmetic.
A previous work related to improvements over regular LVQ is Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search by Jianyang Gao, et. al.
The format is stored within two files:
.veb (vector data) file
Stores the binary quantized vectors in a flat format. Additionally, it stores each vector's corrective factors. At the end of the file, additional information is stored for vector ordinal to centroid ordinal mapping and sparse vector information.
For each vector:
byte the binary quantized values, each byte holds 8 bits.
float the optimized quantiles and an additional similarity dependent corrective factor.
short the sum of the quantized components
After the vectors, sparse vector information keeping track of monotonic blocks.
.vemb (vector metadata) file
Stores the metadata for the vectors. This includes the number of vectors, the number of dimensions, and file offset information.
int the field number
int the vector encoding ordinal
int the vector similarity ordinal
vint the vector dimensions
vlong the offset to the vector data in the .veb file
vlong the length of the vector data in the .veb file
vint the number of vectors
float the centroid
float the centroid square magnitude
The sparse vector information, if required, mapping vector ordinal to doc ID
Functions
Returns a KnnVectorsReader to read the vectors from the index.
Returns a FlatVectorsWriter to write the vectors to the index.
Returns the maximum number of vector dimensions supported by this codec for the given field name