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
//! Vamana approximate nearest neighbor search.
//!
//! # Feature Flag
//!
//! Requires the `vamana` feature:
//! ```toml
//! jin = { version = "0.1", features = ["vamana"] }
//! ```
//!
//! Vamana is a graph-based ANN algorithm that uses two-pass construction with
//! RRND (Relaxed Relative Neighborhood Diversification) and RND strategies.
//!
//! Based on 2025-2026 research: Vamana is competitive with HNSW on large datasets
//! and better for SSD-based serving (5-10× more points/node).
//!
//! # Algorithm
//!
//! Vamana constructs a proximity graph using:
//! 1. Random graph initialization with node degree ≥ log(n)
//! 2. First pass: Refine using RRND (Relaxed RND) with α ≥ 1.5
//! 3. Second pass: Further refine using RND
//! 4. Two-pass construction ensures better graph quality
//!
//! # Performance
//!
//! - Competitive with HNSW on large datasets (100GB-1B vectors)
//! - Better for SSD-based serving (higher points/node ratio)
//! - Two-pass construction: Higher indexing time but better graph quality
//!
//! # Usage
//!
//! Requires `features = ["vamana"]`:
//!
//! ```ignore
//! use jin::vamana::{VamanaIndex, VamanaParams};
//!
//! let params = VamanaParams {
//! max_degree: 64,
//! alpha: 1.3,
//! ..Default::default()
//! };
//! let mut index = VamanaIndex::new(128, params)?;
//!
//! index.add(0, vec![0.1; 128])?;
//! index.build()?;
//!
//! let results = index.search(&vec![0.15; 128], 10, 50)?;
//! ```
//!
//! # References
//!
//! - Subramanya et al. (2019): "DiskANN: Fast accurate billion-point nearest neighbor search"
//! - Azizi et al. (2025): "Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art"
pub use ;