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
//! vicinity = { version = "0.3", features = ["vamana"] }
//! ```
//!
//! Vamana is a graph-based ANN algorithm that uses two-pass construction with
//! RRND (Relaxed Relative Neighborhood Diversification) and RND strategies.
//!
//! Vamana-style flat graphs are commonly used as the basis for SSD-oriented ANN systems
//! (e.g. DiskANN), where a single-layer graph is friendlier to disk access patterns than a
//! multi-layer hierarchy.
//!
//! # Algorithm
//!
//! Vamana constructs a proximity graph using:
//! 1. Random graph initialization with node degree >= log(n)
//! 2. First pass: Refine using RND (alpha=1.0, strict diversity)
//! 3. Second pass: Further refine using RRND (alpha>1.0, relaxed)
//! 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 vicinity::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"
pub use ;