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.