Crate linfa_nn

linfa-nn provides Rust implementations of common spatial indexing algorithms, as well as a trait-based interface for performing nearest-neighbour and range queries using these algorithms.

The big picture

linfa-nn is a crate in the linfa ecosystem, a wider effort to bootstrap a toolkit for classical Machine Learning implemented in pure Rust, kin in spirit to Python’s scikit-learn.

You can find a roadmap (and a selection of good first issues) here - contributors are more than welcome!

Current state

Right now linfa-nn provides the following algorithms:

• Linear Scan
• KD Tree
• Ball Tree

The CommonNearestNeighbour enum should be used to dispatch between all of the above algorithms flexibly.

Modules

distance

Structs

BallTree

Implementation of ball tree, a space partitioning data structure that partitions its points into nested hyperspheres called “balls”. It performs spatial queries in O(k * logN) time, where k is the number of points returned by the query. Calling from_batch returns a BallTreeIndex.

BallTreeIndex

Spatial indexing structure created by BallTree

KdTree

Implementation of K-D tree, a fast space-partitioning data structure. For each parent node, the indexed points are split with a hyperplane into two child nodes. Due to its tree-like structure, the K-D tree performs spatial queries in O(k * logN) time, where k is the number of points returned by the query. Calling from_batch returns a KdTree.

KdTreeIndex

Spatial indexing structure created by KdTree

LinearSearch

Implementation of linear search, which is the simplest nearest neighbour algorithm. All queries are implemented by scanning through every point, so all of them are O(N). Calling from_batch returns a LinearSearchIndex.

LinearSearchIndex

Spatial indexing structure created by LinearSearch

Enums

BuildError

Error returned when building nearest neighbour indices

CommonNearestNeighbour

Enum that dispatches to one of the crate’s NearestNeighbour implementations based on value. This enum should be used instead of using types like LinearSearch and KdTree directly.

NnError

Error returned when performing spatial queries on nearest neighbour indices

Traits

NearestNeighbour

Nearest neighbour algorithm builds a spatial index structure out of a batch of points. The distance between points is calculated using a provided distance function. The index implements the NearestNeighbourIndex trait and allows for efficient computing of nearest neighbour and range queries.

NearestNeighbourIndex

A spatial index structure over a set of points, created by NearestNeighbour. Allows efficient computation of nearest neighbour and range queries over the set of points. Individual points are represented as one-dimensional array views.