Expand description

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:

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

Modules

Structs

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.

Spatial indexing structure created by BallTree

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.

Spatial indexing structure created by KdTree

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.

Spatial indexing structure created by LinearSearch

Enums

Error returned when building nearest neighbour indices

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.

Error returned when performing spatial queries on nearest neighbour indices

Traits

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.

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.