vicinity/
lib.rs

1// Crate-level lint configuration
2#![warn(missing_docs)]
3
4//! vicinity: Approximate Nearest Neighbor Search primitives.
5//!
6//! Provides implementations of ANN algorithms:
7//!
8//! - **Graph-based**: [`hnsw`], `nsw`, `sng`, `vamana`
9//! - **Partition-based**: `ivf_pq`, `scann`
10//! - **Quantization**: `quantization` (RaBitQ, SAQ), `ivf_pq` (Product Quantization)
11//!
12//! # Which Index Should I Use?
13//!
14//! | Situation | Recommendation | Feature |
15//! |-----------|----------------|---------|
16//! | **General Purpose** (Best Recall/Speed) | [`hnsw::HNSWIndex`] | `hnsw` (default) |
17//! | **Billion-Scale** (Memory Constrained) | `ivf_pq::IVFPQIndex` | `ivf_pq` |
18//! | **Flat Graph** (Simpler graph, often worth trying for modern embeddings) | `nsw::NSWIndex` | `nsw` |
19//! | **Attribute Filtering** | [`hnsw::filtered`] | `hnsw` |
20//! | **Out-of-Core** (SSD-based) | `diskann` | `diskann` (experimental) |
21//!
22//! **Default features**: `hnsw`, `innr` (SIMD).
23//!
24//! ## Recommendation Logic
25//!
26//! 1. **Start with HNSW**. It's the industry standard for a reason. It offers the best
27//!    trade-off between search speed and recall for datasets that fit in RAM.
28//!
29//! 2. **Use IVF-PQ** if your dataset is too large for RAM (e.g., > 10M vectors on a laptop).
30//!    It compresses vectors (32x-64x) but has lower recall than HNSW.
31//!
32//! 3. **Try NSW (Flat)** if you want a simpler graph, or you are benchmarking on
33//!    modern embeddings (hundreds/thousands of dimensions). Recent empirical work suggests the
34//!    hierarchy may provide less incremental value in that regime (see arXiv:2412.01940).
35//!    *Note: HNSW is the more common default in production systems, so it’s still a safe first choice.*
36//!
37//! 4. **Use DiskANN** (experimental) if you have an NVMe SSD and 1B+ vectors.
38//!
39//! ```toml
40//! # Minimal (HNSW + SIMD)
41//! vicinity = "0.3"
42//!
43//! # With quantization support
44//! vicinity = { version = "0.3", features = ["ivf_pq"] }
45//! ```
46//!
47//! # Notes (evidence-backed)
48//!
49//! - **Flat vs hierarchical graphs**: Munyampirwa et al. (2024) empirically argue that, on
50//!   high-dimensional datasets, a flat small-world graph can match HNSW’s recall/latency
51//!   benefits because “hub” nodes provide routing power without explicit hierarchy
52//!   (arXiv:2412.01940). This doesn’t make HNSW “wrong” — it just means NSW is often a
53//!   worthwhile baseline to benchmark.
54//!
55//! - **Memory**: for modern embeddings, the raw vector store (n × d × 4 bytes) can dominate.
56//!   The extra hierarchy layers and graph edges still matter, but you should measure on your
57//!   actual (n, d, M, ef) and memory layout.
58//!
59//! - **Quantization**: IVF-PQ and related techniques trade recall for memory. `vicinity` exposes
60//!   IVF-PQ under the `ivf_pq` feature, but you should treat parameter selection as workload-
61//!   dependent (benchmark recall@k vs latency vs memory).
62//!
63//! ## Background (kept short; pointers to sources)
64//!
65//! - **Distance concentration**: in high dimensions, nearest-neighbor distances can become
66//!   less discriminative; see Beyer et al. (1999), “When Is Nearest Neighbor Meaningful?”
67//!   (DOI: 10.1007/s007780050006).
68//!
69//! - **Hubness**: some points appear as nearest neighbors for many queries (“hubs”); see
70//!   Radovanović et al. (2010), “Hubs in Space”.
71//!
72//! - **Benchmarking**: for real comparisons, report recall@k vs latency/QPS curves and include
73//!   memory and build time. When in doubt, use the `ann-benchmarks` datasets and methodology:
74//!   `http://ann-benchmarks.com/`.
75//!
76//! For a curated bibliography covering HNSW/NSW/NSG/DiskANN/PQ/OPQ/ScaNN and related phenomena,
77//! see `doc/references.md` in the repo.
78
79pub mod ann;
80pub mod classic;
81
82#[cfg(feature = "diskann")]
83pub mod diskann;
84
85// Shared helpers for clump-backed modules (evoc, kmeans partitioning).
86#[cfg(any(feature = "evoc", feature = "scann", feature = "ivf_pq"))]
87pub(crate) mod clump_compat;
88
89#[cfg(feature = "evoc")]
90pub mod evoc;
91
92#[cfg(feature = "hnsw")]
93pub mod hnsw;
94
95#[cfg(feature = "ivf_pq")]
96pub mod ivf_pq;
97
98#[cfg(feature = "nsw")]
99pub mod nsw;
100
101#[cfg(feature = "quantization")]
102pub mod quantization;
103
104#[cfg(feature = "scann")]
105pub mod scann;
106
107#[cfg(feature = "sng")]
108pub mod sng;
109
110#[cfg(feature = "vamana")]
111pub mod vamana;
112
113pub(crate) mod adaptive;
114#[cfg(feature = "experimental")]
115pub(crate) mod matryoshka;
116pub mod partitioning;
117pub(crate) mod pq_simd;
118
119pub mod distance;
120pub mod filtering;
121pub mod lid;
122pub mod simd;
123
124// Spectral sanity helpers (feature-gated).
125#[cfg(feature = "rmt-spectral")]
126pub mod spectral;
127
128// Re-exports
129pub use distance::DistanceMetric;
130pub use error::{Result, RetrieveError};
131
132#[cfg(feature = "benchmark")]
133pub mod benchmark;
134pub mod compression;
135pub mod error;
136pub mod persistence;
137pub mod streaming;
vicinity/lib.rs

vicinity/
lib.rs
