vicinity 0.8.1

Approximate nearest-neighbor search
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

//! Compression for vector IDs in ANN indexes.
//!
//! This module provides compression algorithms that exploit ordering invariance
//! in vector ID collections (IVF clusters, HNSW neighbor lists) to achieve
//! compression ratios of 2-4x for large sets.
//!
//! # Implementation
//!
//! When the `id-compression` feature is enabled, compression primitives are
//! provided by the `cnk` crate, which implements:
//! - **Delta+varint**: Compress sorted ID sets with gap coding
//!
//! # Usage
//!
//! ```rust,ignore
//! use vicinity::compression::{DeltaVarintCompressor, IdSetCompressor};
//!
//! let compressor = DeltaVarintCompressor::new();
//! let ids: Vec<u32> = vec![1, 5, 10, 20, 50];
//! let universe_size = 1000;
//!
//! // Compress
//! let compressed = compressor.compress_set(&ids, universe_size)?;
//!
//! // Decompress
//! let decompressed = compressor.decompress_set(&compressed, universe_size)?;
//! ```

// When id-compression feature is enabled, re-export everything from cnk
#[cfg(feature = "id-compression")]
pub use cnk::{
    choose_method, compress_set_auto, compress_set_enveloped, decompress_set_auto,
    decompress_set_enveloped, ChooseConfig, CodecChoice, CompressionError, DeltaVarintCompressor,
    IdCompressionMethod, IdListStats, IdSetCompressor,
};

// Fallback types when id-compression is not enabled
#[cfg(not(feature = "id-compression"))]
mod error;
#[cfg(not(feature = "id-compression"))]
mod traits;

#[cfg(not(feature = "id-compression"))]
pub use error::CompressionError;
#[cfg(not(feature = "id-compression"))]
pub use traits::IdSetCompressor;

/// Compression method selection.
#[cfg(not(feature = "id-compression"))]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub enum IdCompressionMethod {
    /// Delta+varint encoding.
    #[default]
    DeltaVarint,
}

#[cfg(all(test, feature = "id-compression"))]
mod tests {
    use super::*;

    #[test]
    fn test_cnk_integration() {
        let compressor = DeltaVarintCompressor::new();
        let ids: Vec<u32> = vec![1, 5, 10, 20, 50, 100];
        let universe_size = 1000;

        let compressed = compressor.compress_set(&ids, universe_size).unwrap();
        let decompressed = compressor
            .decompress_set(&compressed, universe_size)
            .unwrap();

        assert_eq!(ids, decompressed);
    }

    #[test]
    fn test_compression_ratio() {
        let compressor = DeltaVarintCompressor::new();
        let ids: Vec<u32> = (0..1000).collect();
        let universe_size = 100_000;

        let compressed = compressor.compress_set(&ids, universe_size).unwrap();
        let ratio = (ids.len() * 4) as f64 / compressed.len() as f64;

        // Should achieve compression
        assert!(
            ratio > 1.5,
            "Expected compression ratio > 1.5, got {}",
            ratio
        );
    }
}