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.