## 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.