Module prt 

Probabilistic Routing Test (PRT) for graph-based ANN search.

Estimates angular distance between vectors using random subspace projections in o(d) time, avoiding unnecessary full distance computations during graph traversal. Inspired by the Projection-Augmented Graph (PAG) approach (Lu et al., 2026, arXiv:2603.06660).

How it works

1. Pre-compute k random projection vectors (k << d).
2. Project all database vectors into the k-dimensional subspace.
3. During search, project the query once, then compare projected distances against a threshold to decide whether to compute the full distance.
4. A Test Feedback Buffer (TFB) tightens the threshold across search rounds by tracking the ratio of false positives, recycling wasted computation.

Usage

use vicinity::prt::ProbabilisticRoutingTest;

let prt = ProbabilisticRoutingTest::new(dimension, 32, Some(42));
prt.project_database(&vectors);

// During search, for each candidate:
let projected_dist = prt.projected_distance(&query_proj, candidate_id);
if projected_dist < threshold {
    // Worth computing full distance.
    let full_dist = l2_distance(query, candidate_vector);
}

Structs

ProbabilisticRoutingTest

Probabilistic Routing Test state.

TestFeedbackBuffer

Test Feedback Buffer for adaptive threshold tightening.