flow-knn 0.1.1

Algorithm-agnostic k-NN graphs for flow cytometry — exact, usearch HNSW, optional ann-search-rs
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//! Configuration for k-NN search.

/// Approximate / exact nearest-neighbour method.
#[derive(Debug, Clone)]
pub enum KnnMethod {
    /// HNSW via usearch (C++ FFI, hardware SIMD) — default when the `hnsw` feature is on.
    #[cfg(feature = "hnsw")]
    Hnsw(HnswParams),

    /// Exact brute-force O(n · k · d) with a bounded heap per query.
    Exact,

    /// k-d tree via `kiddo` (currently falls back to exact).
    #[cfg(feature = "kdtree")]
    KdTree,

    /// HNSW via `ann-search-rs` (optional feature `ann-search`).
    #[cfg(feature = "ann-search")]
    AnnSearchHnsw(HnswParams),

    /// Exact exhaustive kNN on GPU (ann-search-rs + cubeCL / wgpu). Feature `gpu`.
    #[cfg(feature = "gpu")]
    GpuExact,

    /// IVF approximate kNN on GPU. Feature `gpu`.
    #[cfg(feature = "gpu")]
    GpuIvf(IvfGpuParams),

    /// NN-Descent / CAGRA-style approximate kNN on GPU. Feature `gpu`.
    #[cfg(feature = "gpu")]
    GpuNnDescent(NnDescentGpuParams),

    /// Reserved placeholder.
    Annoy,
}

/// IVF-GPU list / probe parameters (`None` → ann-search-rs defaults √n / √nlist).
#[derive(Debug, Clone, Default)]
#[cfg(feature = "gpu")]
pub struct IvfGpuParams {
    pub n_list: Option<usize>,
    pub n_probes: Option<usize>,
}

/// NN-Descent GPU graph parameters (`None` → library defaults).
#[derive(Debug, Clone)]
#[cfg(feature = "gpu")]
pub struct NnDescentGpuParams {
    /// Final graph degree after pruning (default: max(k, 30) at call site).
    pub k: Option<usize>,
    pub k_build: Option<usize>,
    pub n_trees: Option<usize>,
    pub delta: f32,
    pub rho: Option<f32>,
}

#[cfg(feature = "gpu")]
impl Default for NnDescentGpuParams {
    fn default() -> Self {
        Self {
            k: None,
            k_build: None,
            n_trees: None,
            delta: 0.001,
            rho: None,
        }
    }
}

impl Default for KnnMethod {
    fn default() -> Self {
        // Prefer ann-search-rs when that feature is enabled (matches manifolds-rs HNSW).
        #[cfg(feature = "ann-search")]
        return Self::AnnSearchHnsw(HnswParams::default());
        #[cfg(all(not(feature = "ann-search"), feature = "hnsw"))]
        return Self::Hnsw(HnswParams::default());
        #[cfg(all(not(feature = "ann-search"), not(feature = "hnsw")))]
        return Self::Exact;
    }
}

/// Quality / memory trade-off for HNSW indices (usearch or ann-search-rs).
#[derive(Debug, Clone)]
pub struct HnswParams {
    /// Graph connectivity (M). Default 16.
    pub m: usize,
    /// Build-time candidate set size. Default 200.
    pub ef_construction: usize,
    /// Query-time candidate set size. Default 50.
    pub ef_search: usize,
    /// Storage quantization (usearch only; ignored by ann-search-rs).
    pub quantization: Quantization,
}

impl Default for HnswParams {
    fn default() -> Self {
        Self {
            m: 16,
            ef_construction: 200,
            ef_search: 50,
            quantization: Quantization::F32,
        }
    }
}

/// Vector quantization for usearch HNSW storage.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Quantization {
    #[default]
    F32,
    F16,
    I8,
}

/// Distance metric for the KNN graph.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum DistanceMetric {
    #[default]
    Euclidean,
    EuclideanSq,
    Cosine,
    Manhattan,
}