Indices

The uncompressed CPU estimators. Every one takes its parameters in the constructor, its data in fit, and hands results back from kneighbors.

Parameters described as search-time can be overridden per call, so index.kneighbors(X, ef_search=200) leaves the fitted index alone. Everything else is fixed at build time and changing it means refitting.

indices

The estimators.

Each class stores its constructor arguments verbatim, names the compiled handle it drives, and says which of its parameters are search-time knobs. Everything else comes from BaseAnnIndex.

Build defaults are lifted from the crate's own gridsearch examples and parameter defaults rather than invented; see examples/gridsearch_*.rs and docs/benchmarks_standard.md in the repository.

ExhaustiveIndex

ExhaustiveIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    verbose: bool = False,
)

Bases: BaseAnnIndex

Brute-force exact search.

Every query is scored against every point, so recall is 1 by construction. The usual reason to reach for it is ground truth, but it is not a naive scan: the core dispatches on batch size between a fused per-query SIMD scan and a blocked GEMM path that reuses each database tile across a tile of queries. On a large batch, and the self-kNN graph is the largest batch there is, that puts it further up the field than brute force has any right to be. Measure before assuming an approximate index is worth its build.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

KmknnIndex

KmknnIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    nlist: int | None = None,
    kmeans_iters: int | None = None,
    kmeans_balanced: bool = False,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

k-means-based k-nearest-neighbours.

Partitions the data with k-means and prunes clusters by the triangle inequality. Exact, and usually well ahead of brute force once the data clusters at all. Manhattan is not supported.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
nlist	int | None	Number of k-means clusters to partition into. None defaults to sqrt(n). More clusters prune harder but cost more to scan the centroids.	None
kmeans_iters	int | None	Lloyd iterations when training the partition. None defaults to 30.	None
kmeans_balanced	bool	Reseed starved centroids each iteration. Off by default because it changes the partition, and therefore the index built on it.	False
seed	int	Fixes k-means initialisation.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

AnnoyIndex

AnnoyIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    n_trees: int = 25,
    search_budget: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Random projection forest, as in Spotify's Annoy.

More trees means better recall and a larger index. Manhattan is not supported.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
n_trees	int	Trees in the forest. The size and build-cost knob; recall climbs with it and so does memory.	25
search_budget	int | None	Candidates to inspect per query, the recall knob. None defaults to k * n_trees * 20. Search-time: override it per call as index.kneighbors(search_budget=5000).	None
seed	int	Fixes the random hyperplanes.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

HnswIndex

HnswIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    m: int = 16,
    ef_construction: int = 200,
    ef_search: int = 50,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Hierarchical navigable small world graph.

The usual first choice: high recall at low query latency, for a graph roughly m edges per node wide. Raise ef_search for recall, ef_construction for a better graph. The second one is what the build cost is actually sensitive to.

Cheapest of the graph indices here to build at its cheapest setting. That ordering does not survive matching on recall, where VamanaIndex can come out ahead.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
m	int	Edges per node on the upper layers, 2 * m on layer 0. The memory knob. 16 suits most data; 32 to 48 helps in high dimensions.	16
ef_construction	int	Candidate list width during the build. Higher means a better graph and a slower build, and it does not cost anything at query time.	200
ef_search	int	Beam width at query time, the recall knob. Raised to k if you ask for less, since a beam narrower than the answer cannot fill it. Search-time: override it per call as index.kneighbors(ef_search=200).	50
seed	int	Fixes the layer assignment.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

IvfIndex

IvfIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    nlist: int | None = None,
    nprobe: int | None = None,
    kmeans_iters: int | None = None,
    kmeans_balanced: bool = False,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Inverted file index over k-means Voronoi cells.

Cheap to build and easy to tune: nlist sets how finely the space is cut, nprobe how many cells a query visits. Both default to the crate's own heuristics when left as None. The smallest of the approximate unquantised indices: it holds the vectors and a permutation, and little else. Manhattan is not supported.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
nlist	int | None	Number of Voronoi cells to cut the space into. None defaults to sqrt(n). More cells means less work per probe and a longer build.	None
nprobe	int | None	Cells visited per query, the recall knob. None defaults to sqrt(nlist), and anything above nlist is capped there. Search-time: override it per call as index.kneighbors(nprobe=32).	None
kmeans_iters	int | None	Lloyd iterations when training the cells. None defaults to 30.	None
kmeans_balanced	bool	Reseed starved centroids each iteration. Evens out the posting lists, at the cost of a partition that no longer matches an unbalanced run.	False
seed	int	Fixes k-means initialisation.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

NNDescentIndex

NNDescentIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    delta: float = 0.001,
    diversify_prob: float = 1.0,
    max_iter: int | None = None,
    max_candidates: int | None = None,
    n_trees: int | None = None,
    ef_search: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: ExtractKnnMixin, BaseAnnIndex

NN-Descent kNN graph.

Builds the neighbour graph directly by iterative local join. n_neighbors is used at build time as well as at query time, so changing it means rebuilding.

Whether it is the quickest route to a self-kNN graph depends on the shape. On the benchmark runs it wins at 128 dimensions, where extract_knn reaches recall 1.0 in roughly half the time KmknnIndex needs. At 32 dimensions KmknnIndex and IvfIndex get there first, exactly. Measure both on your data.

diversify_prob prunes redundant edges from the graph queries walk: 0.0 disables it, 1.0 prunes whenever the rule fires. On the ann-benchmarks runs 1.0 gives 2.7x the queries per second at equal recall on SIFT and GloVe; on easy low-dimensional data it buys nothing and costs ~15% more build time.

extract_knn hands back the converged graph instead of searching for it again, which is far cheaper than kneighbors(None). It reads the full kNN graph whatever diversify_prob is.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per node in the graph being built, and the default k for kneighbors. A build parameter here, unlike every other index: changing it means rebuilding.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
delta	float	Convergence threshold. Descent stops once the fraction of updated edges falls below it.	0.001
diversify_prob	float	Probability of pruning an edge the occlusion rule fires on, in the query graph only. 0.0 disables pruning, 1.0 prunes every time.	1.0
max_iter	int | None	Descent iteration cap. None defaults to max(round(log2(n)), 5).	None
max_candidates	int | None	Neighbours sampled per node per local join. None defaults to min(n_neighbors, 60). The main quality-versus-time knob on the build; 30 to 60 is the useful range.	None
n_trees	int | None	Random projection trees used to seed the initial graph. None defaults to min(5 + round(sqrt(n) / 20), 64), scanpy's setting.	None
ef_search	int | None	Beam width at query time. None defaults to clamp(2 * k, 50, 200), and any value is raised to k. Search-time: override it per call as index.kneighbors(ef_search=200). Irrelevant to extract_knn, which does not search.	None
seed	int	Fixes the seed graph and the sampling.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

VamanaIndex

VamanaIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    r: int = 48,
    l_build: int = 100,
    alpha_pass1: float = 1.0,
    alpha_pass2: float = 1.2,
    ef_search: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Vamana graph, as in DiskANN.

A single flat graph of out-degree r, pruned in two passes with the relaxed-neighbour rule. Builds slower than HNSW at its cheapest setting, though the gap closes once you match on recall. The index runs a few per cent smaller than HNSW's, and NsgIndex is smaller than both.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
r	int	Maximum out-degree. The memory knob, and the ceiling on how much the beam can expand per hop.	48
l_build	int	Candidate list width during the build, the analogue of HNSW's ef_construction.	100
alpha_pass1	float	Relaxed-neighbour factor on the first pruning pass. 1.0 is the plain rule.	1.0
alpha_pass2	float	Same on the second pass. Above 1 keeps longer edges, which is what makes the graph navigable from far away.	1.2
ef_search	int | None	Beam width at query time, the recall knob. None defaults to 75, and any value is raised to k. Search-time: override it per call as index.kneighbors(ef_search=200).	None
seed	int	Fixes the entry point and the pruning order.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

NsgIndex

NsgIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    r: int = 32,
    l_build: int = 100,
    c: int = 500,
    knn_k: int = 64,
    ef_search: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Navigating spreading-out graph.

Refines a kNN graph into a sparse monotonic one. knn_k sizes the NN-Descent graph it builds internally first, so it is a build cost rather than a query knob.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
r	int	Maximum out-degree of the refined graph. The memory knob.	32
l_build	int	Candidate list width while refining.	100
c	int	Candidate pool size per node before pruning. Larger means a better choice of edges and a slower build.	500
knn_k	int	Degree of the NN-Descent graph built first, which NSG then prunes. Wants to be comfortably above r.	64
ef_search	int | None	Beam width at query time, the recall knob. None defaults to 100, and any value is raised to k. Search-time: override it per call as index.kneighbors(ef_search=200).	None
seed	int	Fixes the initial graph and the navigating node.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

BallTreeIndex

BallTreeIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    search_budget: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Metric tree of nested hyperspheres.

Prunes by the triangle inequality, which pays off when the data has genuine cluster structure and the dimensionality is moderate. search_budget defaults to 5% of the indexed points, so the defaults are approximate; raise it for recall. Manhattan is not supported.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
search_budget	int | None	Points to inspect per query, the recall knob. None defaults to 5% of the indexed points. That holds up at 32 dimensions and goes thin higher up, where it drops to about 0.91 recall and 10% is the better starting point. Past 10% recall plateaus and query time does not fall. Search-time: override it per call as index.kneighbors(search_budget=5000).	None
seed	int	Fixes the pivot choice at each split.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

KdTreeIndex

KdTreeIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    n_trees: int = 25,
    search_budget: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Forest of randomised kd spill-trees.

Same trade as Annoy, with axis-aligned splits instead of random hyperplanes: more trees means better recall and a larger index. The one tree index here that supports Manhattan.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
n_trees	int	Trees in the forest. The size and build-cost knob; recall climbs with it and so does memory.	25
search_budget	int | None	Candidates to inspect per query, the recall knob. None defaults to k * n_trees * 20. Search-time: override it per call as index.kneighbors(search_budget=5000).	None
seed	int	Fixes the split dimensions and the spill overlap.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

Note

The trees are spill-trees: points near a split land in both children, at the crate's fixed 5% overlap. That is what lets a single descent recover neighbours a hard split would have separated. The overlap is not exposed here.

LshIndex

LshIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    num_tables: int = 8,
    bits_per_hash: int = 12,
    slot_bits: int | None = None,
    n_probe: int | None = None,
    max_candidates: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Multi-probe locality-sensitive hashing over random projections.

The cheapest index to build here by a wide margin, and the weakest on recall for the query time it costs. Lower bits_per_hash widens the buckets, trading query time for recall; num_tables trades index size for recall. n_probe defaults to one probe per projection. Manhattan is not supported.

It is also the one index here whose query can come out slower than brute force, so time it rather than assuming.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
num_tables	int	Independent hash tables. Trades index size for recall.	8
bits_per_hash	int	Total bits in a bucket code. Fewer bits means wider buckets, so more candidates and better recall per probe.	12
slot_bits	int | None	Bits each quantised projection contributes, so the table holds bits_per_hash // slot_bits projections. None defaults to 1 for cosine and 2 otherwise, clamped into 1..=bits_per_hash.	None
n_probe	int | None	Buckets probed per table, the recall knob. None defaults to one probe per projection, i.e. bits_per_hash // slot_bits. Search-time: override it per call as index.kneighbors(n_probe=32).	None
max_candidates	int | None	Cap on candidates scored per query. None means no cap, so every point the probes turned up gets scored. Search-time.	None
seed	int	Fixes the random projections.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

SoarIndex

SoarIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    nlist: int | None = None,
    nprobe: int | None = None,
    rule: str | None = None,
    rule_param: float | None = None,
    kmeans_iters: int | None = None,
    kmeans_balanced: bool = False,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

IVF with spilling, as in Google's SOAR.

Every point also lands in a second cell, picked by a rule that accounts for the residual it already carries in its primary cell. That buys recall at a given nprobe over plain IVF, for twice the posting-list entries.

Read that trade against query time, not against nprobe. At a fixed nprobe a spilled index scans about twice the candidates, so comparing at equal nprobe flatters it and answers nothing.

rule is one of "nearest", "shifted" or "orthogonal", and None lets the core choose per metric: orthogonal for cosine, shifted otherwise. rule_param is mu for shifted and lambda for orthogonal, and None takes the core's own value. Manhattan is not supported.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean" or "cosine".	'euclidean'
nlist	int | None	Number of Voronoi cells to cut the space into. None defaults to sqrt(n). Spilling doubles the posting-list entries on top of this, which is a few per cent of index size rather than double: the vectors are stored once either way.	None
nprobe	int | None	Cells visited per query, the recall knob. None defaults to sqrt(nlist). Search-time: override it per call as index.kneighbors(nprobe=32).	None
rule	str | None	Secondary-assignment rule, one of "nearest", "shifted" or "orthogonal". None picks orthogonal for cosine and shifted otherwise.	None
rule_param	float | None	mu for the shifted rule, lambda for the orthogonal one, ignored by "nearest". None takes the crate's values: mu = 0.5, lambda = 1.0.	None
kmeans_iters	int | None	Lloyd iterations when training the cells. None defaults to 30.	None
kmeans_balanced	bool	Reseed starved centroids each iteration.	False
seed	int	Fixes k-means initialisation.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False

Raises:

Type	Description
ValueError	On fit, if rule is not one of the three names.

RnnDescentIndex

RnnDescentIndex(
    n_neighbors: int = 15,
    metric: str = "euclidean",
    s: int = 20,
    r: int = 96,
    t1: int = 4,
    t2: int = 15,
    n_trees: int | None = None,
    ef_search: int | None = None,
    k_search: int | None = None,
    seed: int = 42,
    verbose: bool = False,
)

Bases: BaseAnnIndex

Relative NN-Descent graph.

Builds and prunes in one pass, reaching a sparse navigable graph without the separate NSG-style refinement step. That saves it the double build NsgIndex pays, though HnswIndex still builds faster. r caps the out-degree and is the main size knob; ef_search is the main recall knob.

On the benchmark gaussian runs it tops out around 0.97 recall, so check it reaches what you need before committing to it.

Parameters:

Name	Type	Description	Default
n_neighbors	int	Neighbours per query, and the default k for kneighbors.	15
metric	str	"euclidean"/"l2", "sqeuclidean", "cosine" or "manhattan"/"l1".	'euclidean'
s	int	Neighbours sampled per node per local join during descent.	20
r	int	Maximum out-degree after pruning. The memory knob.	96
t1	int	Outer iterations, each of which rebuilds the candidate graph.	4
t2	int	Inner descent iterations per outer one.	15
n_trees	int | None	Random projection trees used to seed the initial graph. None defaults to min(5 + n ** 0.25 / 2, 16).	None
ef_search	int | None	Beam width at query time, the recall knob. None defaults to 100, and any value is raised to k. Search-time: override it per call as index.kneighbors(ef_search=200).	None
k_search	int | None	Neighbours expanded per hop during the search. None defaults to 32, capped at r. Search-time.	None
seed	int	Fixes the seed graph and the sampling.	42
verbose	bool	Progress to the process stdout, not sys.stdout. In Jupyter that lands in the terminal running the kernel.	False