Method search_layer_0

nodedb-vector/src/codec_index/search.rs:137–186

Beam search at layer 0 using `fast_symmetric_distance`. Returns candidates sorted ascending by symmetric distance (used only for routing; final ranking is done by `exact_asymmetric_distance` in the caller).

(&self, q_enc: &C::Quantized, ep_idx: u32, ef: usize)

    /// for routing; final ranking is done by `exact_asymmetric_distance` in
    /// the caller).
    fn search_layer_0(&self, q_enc: &C::Quantized, ep_idx: u32, ef: usize) -> Vec<Cand> {
        let mut visited: HashSet<u32> = HashSet::new();
        visited.insert(ep_idx);

        let ep_dist = self
            .codec
            .fast_symmetric_distance(q_enc, &self.nodes[ep_idx as usize].quantized);
        let ep_cand = Cand {
            dist: ep_dist,
            idx: ep_idx,
        };

        let mut candidates: BinaryHeap<Reverse<Cand>> = BinaryHeap::new();
        candidates.push(Reverse(ep_cand));

        let mut results: BinaryHeap<Cand> = BinaryHeap::new();
        if !self.nodes[ep_idx as usize].deleted {
            results.push(ep_cand);
        }

        while let Some(Reverse(cur)) = candidates.pop() {
            let worst = results.peek().map_or(f32::INFINITY, |w| w.dist);
            if cur.dist > worst && results.len() >= ef {
                break;
            }

            for &nb in self.neighbors_at(cur.idx, 0) {
                if !visited.insert(nb) {
                    continue;
                }
                let d = self
                    .codec
                    .fast_symmetric_distance(q_enc, &self.nodes[nb as usize].quantized);
                let worst_now = results.peek().map_or(f32::INFINITY, |w| w.dist);
                if d < worst_now || results.len() < ef {
                    candidates.push(Reverse(Cand { dist: d, idx: nb }));
                }
                if !self.nodes[nb as usize].deleted {
                    results.push(Cand { dist: d, idx: nb });
                    if results.len() > ef {
                        results.pop();
                    }
                }
            }
        }

        let mut out: Vec<Cand> = results.into_vec();
        out.sort_unstable_by(|a, b| a.dist.total_cmp(&b.dist));
        out
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────