velesdb_core/quantization/
binary.rs

1//! Binary quantization (1-bit per dimension) for extreme memory reduction.
2//!
3//! Each f32 value is converted to 1 bit: >= 0.0 becomes 1, < 0.0 becomes 0.
4//! This provides **32x memory reduction** compared to f32 storage.
5
6use std::io;
7
8use super::codec_helpers::{serialize_with_header, validate_and_split_header};
9use super::QuantizationCodec;
10
11/// A binary quantized vector using 1-bit per dimension.
12///
13/// Each f32 value is converted to 1 bit: >= 0.0 becomes 1, < 0.0 becomes 0.
14/// This provides **32x memory reduction** compared to f32 storage.
15///
16/// # Memory Usage
17///
18/// | Dimension | f32 | Binary |
19/// |-----------|-----|--------|
20/// | 768 | 3072 bytes | 96 bytes |
21/// | 1536 | 6144 bytes | 192 bytes |
22///
23/// # Use with Rescoring
24///
25/// For best accuracy, use binary search for candidate selection,
26/// then rescore top candidates with full-precision vectors.
27#[derive(Debug, Clone)]
28pub struct BinaryQuantizedVector {
29    /// Binary data (1 bit per dimension, packed into bytes).
30    pub data: Vec<u8>,
31    /// Original dimension of the vector.
32    dimension: usize,
33}
34
35impl BinaryQuantizedVector {
36    /// Creates a new binary quantized vector from f32 data.
37    ///
38    /// Values >= 0.0 become 1, values < 0.0 become 0.
39    ///
40    /// # Arguments
41    ///
42    /// * `vector` - The original f32 vector to quantize
43    #[must_use]
44    pub fn from_f32(vector: &[f32]) -> Self {
45        // Caller guarantees non-empty (dimension validated at collection level).
46        debug_assert!(!vector.is_empty(), "Cannot quantize empty vector");
47
48        let dimension = vector.len();
49        // Calculate number of bytes needed: ceil(dimension / 8)
50        let num_bytes = dimension.div_ceil(8);
51        let mut data = vec![0u8; num_bytes];
52
53        for (i, &value) in vector.iter().enumerate() {
54            if value >= 0.0 {
55                // Set bit i in the packed byte array
56                let byte_idx = i / 8;
57                let bit_idx = i % 8;
58                data[byte_idx] |= 1 << bit_idx;
59            }
60        }
61
62        Self { data, dimension }
63    }
64
65    /// Returns the dimension of the original vector.
66    #[must_use]
67    pub fn dimension(&self) -> usize {
68        self.dimension
69    }
70
71    /// Returns the memory size in bytes.
72    #[must_use]
73    pub fn memory_size(&self) -> usize {
74        self.data.len()
75    }
76
77    /// Returns the individual bits as a boolean vector.
78    ///
79    /// Useful for debugging and testing.
80    #[must_use]
81    pub fn get_bits(&self) -> Vec<bool> {
82        (0..self.dimension)
83            .map(|i| {
84                let byte_idx = i / 8;
85                let bit_idx = i % 8;
86                (self.data[byte_idx] >> bit_idx) & 1 == 1
87            })
88            .collect()
89    }
90
91    /// Computes the Hamming distance to another binary vector.
92    ///
93    /// Hamming distance counts the number of bits that differ.
94    /// Uses POPCNT for fast bit counting.
95    ///
96    /// # Panics
97    ///
98    /// Panics if the vectors have different dimensions.
99    #[must_use]
100    pub fn hamming_distance(&self, other: &Self) -> u32 {
101        debug_assert_eq!(
102            self.dimension, other.dimension,
103            "Dimension mismatch in hamming_distance"
104        );
105
106        // XOR bytes and count differing bits using POPCNT
107        self.data
108            .iter()
109            .zip(other.data.iter())
110            .map(|(&a, &b)| (a ^ b).count_ones())
111            .sum()
112    }
113
114    /// Computes normalized Hamming similarity (0.0 to 1.0).
115    ///
116    /// Returns 1.0 for identical vectors, 0.0 for completely different.
117    #[must_use]
118    #[allow(clippy::cast_precision_loss)]
119    pub fn hamming_similarity(&self, other: &Self) -> f32 {
120        let distance = self.hamming_distance(other);
121        1.0 - (distance as f32 / self.dimension as f32)
122    }
123}
124
125/// Binary header: `[dimension: u32 LE]` = 4 bytes.
126const BINARY_HEADER_SIZE: usize = 4;
127
128impl QuantizationCodec for BinaryQuantizedVector {
129    fn to_bytes(&self) -> Vec<u8> {
130        // Dimension is set from vector.len() which fits in usize (always < u32::MAX
131        // on supported platforms where vectors cannot exceed 4B dimensions).
132        debug_assert!(
133            u32::try_from(self.dimension).is_ok(),
134            "BinaryQuantizedVector dimension {} exceeds u32::MAX for serialization",
135            self.dimension
136        );
137
138        // Reason: dimension validated above to fit in u32
139        #[allow(clippy::cast_possible_truncation)]
140        let header = (self.dimension as u32).to_le_bytes();
141        serialize_with_header(&header, &self.data)
142    }
143
144    fn from_bytes(bytes: &[u8]) -> io::Result<Self> {
145        let (header, payload) =
146            validate_and_split_header(bytes, BINARY_HEADER_SIZE, "BinaryQuantizedVector")?;
147
148        #[allow(clippy::cast_possible_truncation)]
149        // Reason: u32 always fits in usize on 32-bit and 64-bit platforms
150        let dimension = u32::from_le_bytes([header[0], header[1], header[2], header[3]]) as usize;
151        let expected_data_len = dimension.div_ceil(8);
152
153        if payload.len() < expected_data_len {
154            return Err(io::Error::new(
155                io::ErrorKind::InvalidData,
156                format!(
157                    "Not enough bytes for BinaryQuantizedVector data: expected {}, got {}",
158                    BINARY_HEADER_SIZE + expected_data_len,
159                    bytes.len()
160                ),
161            ));
162        }
163
164        let data = payload[..expected_data_len].to_vec();
165
166        Ok(Self { data, dimension })
167    }
168}
velesdb_core/quantization/binary.rs

velesdb_core/quantization/
binary.rs
