transposeHalfByte

Transpose the query vector into a byte array allowing for efficient bitwise operations with the index bit vectors. The idea here is to organize the query vector bits such that the first bit of every dimension is in the first set dimensions bits, or (dimensions/8) bytes. The second, third, and fourth bits are in the second, third, and fourth set of dimensions bits, respectively. This allows for direct bitwise comparisons with the stored index vectors through summing the bitwise results with the relative required bit shifts.

This bit decomposition for fast bitwise SIMD operations was first proposed in:

Gao, Jianyang, and Cheng Long. "RaBitQ: Quantizing High-
Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search."
Proceedings of the ACM on Management of Data 2, no. 3 (2024): 1-27.

Parameters