nodedb_vector/navix/
selectivity.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Local selectivity estimation for NaviX adaptive-local filtered traversal.
4//!
5//! At each hop during HNSW traversal, NaviX computes the fraction of 1-hop
6//! neighbors that pass the filter (local selectivity) and picks an expansion
7//! heuristic accordingly.  This is the key difference from static ACORN-1,
8//! which always expands to 2-hop regardless of local density.
9
10use roaring::RoaringBitmap;
11
12/// Compute the local selectivity at a graph node.
13///
14/// Returns the fraction of 1-hop neighbors that are present in `allowed`.
15/// Range: `[0.0, 1.0]`.  An empty neighborhood returns `0.0`.
16pub fn local_selectivity_at(node_neighbors: &[u32], allowed: &RoaringBitmap) -> f32 {
17    if node_neighbors.is_empty() {
18        return 0.0;
19    }
20    let matched = node_neighbors
21        .iter()
22        .filter(|&&n| allowed.contains(n))
23        .count();
24    matched as f32 / node_neighbors.len() as f32
25}
26
27/// Heuristic chosen for expanding a given hop based on local selectivity.
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29#[non_exhaustive]
30pub enum NavixHeuristic {
31    /// High selectivity (> 50%) — normal HNSW expansion; score every neighbor
32    /// in `allowed` and add to the candidate heap.
33    Standard,
34    /// Medium-low selectivity (1% ≤ sel ≤ 50%) — score 1-hop neighbors, pick
35    /// the single best (lowest distance), then expand that neighbor's 2-hop
36    /// neighbors into the candidate heap.
37    Directed,
38    /// Very low selectivity (< 1%) — skip 1-hop scoring entirely; sample all
39    /// 2-hop neighbors of every 1-hop neighbor and add those that are in
40    /// `allowed` to the candidate heap directly.
41    Blind,
42}
43
44/// Pick the expansion heuristic for a node given its local selectivity.
45pub fn pick_heuristic(local_selectivity: f32) -> NavixHeuristic {
46    if local_selectivity > 0.50 {
47        NavixHeuristic::Standard
48    } else if local_selectivity >= 0.01 {
49        NavixHeuristic::Directed
50    } else {
51        NavixHeuristic::Blind
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    // ── pick_heuristic boundary tests ──────────────────────────────────────
60
61    #[test]
62    fn heuristic_zero() {
63        assert_eq!(pick_heuristic(0.0), NavixHeuristic::Blind);
64    }
65
66    #[test]
67    fn heuristic_below_directed_threshold() {
68        assert_eq!(pick_heuristic(0.005), NavixHeuristic::Blind);
69    }
70
71    #[test]
72    fn heuristic_at_directed_lower_boundary() {
73        // 0.01 is inclusive in Directed range
74        assert_eq!(pick_heuristic(0.01), NavixHeuristic::Directed);
75    }
76
77    #[test]
78    fn heuristic_mid_directed() {
79        assert_eq!(pick_heuristic(0.30), NavixHeuristic::Directed);
80    }
81
82    #[test]
83    fn heuristic_at_standard_lower_boundary() {
84        // 0.50 is still Directed (not strictly greater than 0.50)
85        assert_eq!(pick_heuristic(0.50), NavixHeuristic::Directed);
86    }
87
88    #[test]
89    fn heuristic_just_above_standard_boundary() {
90        assert_eq!(pick_heuristic(0.51), NavixHeuristic::Standard);
91    }
92
93    #[test]
94    fn heuristic_full_selectivity() {
95        assert_eq!(pick_heuristic(1.0), NavixHeuristic::Standard);
96    }
97
98    // ── local_selectivity_at tests ─────────────────────────────────────────
99
100    #[test]
101    fn empty_neighbors_returns_zero() {
102        let allowed = RoaringBitmap::new();
103        assert_eq!(local_selectivity_at(&[], &allowed), 0.0);
104    }
105
106    #[test]
107    fn all_matching_returns_one() {
108        let mut allowed = RoaringBitmap::new();
109        allowed.insert(0);
110        allowed.insert(1);
111        allowed.insert(2);
112        let neighbors = [0u32, 1, 2];
113        assert!((local_selectivity_at(&neighbors, &allowed) - 1.0).abs() < 1e-6);
114    }
115
116    #[test]
117    fn half_matching_returns_half() {
118        let mut allowed = RoaringBitmap::new();
119        allowed.insert(0);
120        allowed.insert(2);
121        let neighbors = [0u32, 1, 2, 3];
122        assert!((local_selectivity_at(&neighbors, &allowed) - 0.5).abs() < 1e-6);
123    }
124
125    #[test]
126    fn none_matching_returns_zero() {
127        let allowed = RoaringBitmap::new();
128        let neighbors = [0u32, 1, 2, 3];
129        assert_eq!(local_selectivity_at(&neighbors, &allowed), 0.0);
130    }
131}
nodedb_vector/navix/selectivity.rs

nodedb_vector/navix/
selectivity.rs
