### 2 releases

✓ Uses Rust 2018 edition

0.1.1 | Jun 30, 2020 |
---|---|

0.1.0 | Jun 24, 2020 |

#**268** in Algorithms

**MIT**license

96KB

2.5K SLoC

`acap`

`acap`

As Close As Possible — nearest neighbor search in Rust.

## Example

`use` `acap``::``euclid``::`Euclidean`;`
`use` `acap``::``vp``::`VpTree`;`
`use` `acap``::`NearestNeighbors`;`
`let` tree `=` `VpTree``::`balanced`(``vec!``[`
Euclidean`(``[``3``,` `4``]``)``,`
Euclidean`(``[``5``,` `12``]``)``,`
Euclidean`(``[``8``,` `15``]``)``,`
Euclidean`(``[``7``,` `24``]``)``,`
`]``)``;`
`let` nearest `=` tree`.``nearest``(``&``[``7``,` `7``]``)``.``unwrap``(``)``;`
`assert_eq!``(`nearest`.`item`,` `&`Euclidean`(``[``3``,` `4``]``)``)``;`
`assert_eq!``(`nearest`.`distance`,` `5``)``;`

### `lib.rs`

:

As Close As Possible — nearest neighbor search in Rust.

# Overview

The notion of distances between points is captured by the [

] trait. Its `Proximity`

method returns a [`distance``(``)`

], from which the actual numerical distance may be retrieved with `Distance`

. These layers of abstraction allow `value``(``)`

to work with generically with different distance functions over different types.`acap`

There are no restrictions on the distances computed by a [

]. For example, they don't have to be symmetric, subadditive, or even positive. Implementations that do have these desirable properties will additionally implement the [`Proximity`

] marker trait. This distinction allows `Metric`

to support a wide variety of useful metric and non-metric distances.`acap`

As a concrete example, consider

. The [`Euclidean <[i32; 2]>`

`Euclidean`

] wrapper equips any type that has coordinates with the Euclidean distance function as its [`Proximity`

] implementation:` ``use` `acap``::``distance``::`Proximity`;`
`use` `acap``::``euclid``::`Euclidean`;`
`let` a `=` Euclidean`(``[``3``,` `4``]``)``;`
`let` b `=` Euclidean`(``[``7``,` `7``]``)``;`
`assert_eq!``(`a`.``distance``(``&`b`)``,` `5``)``;`

In this case,

doesn't return a number directly; as an optimization, it returns a [`distance``(``)`

] wrapper. This wrapper stores the squared value of the distance, to avoid computing square roots until absolutely necessary. Still, it transparently supports comparisons with numerical values:`EuclideanDistance`

` ``#` `use` `acap``::``distance``::`Proximity`;`
`#` `use` `acap``::``euclid``::`Euclidean`;`
`#` `let` a `=` Euclidean`(``[``3``,` `4``]``)``;`
`#` `let` b `=` Euclidean`(``[``7``,` `7``]``)``;`
`use` `acap``::``distance``::`Distance`;`
`let` d `=` a`.``distance``(``&`b`)``;`
`assert!``(`d `>` `4` `&&` d `<` `6``)``;`
`assert_eq!``(`d`,` `5``)``;`
`assert_eq!``(`d`.``value``(``)``,` `5.``0``f32``)``;`

For finding the nearest neighbors to a point from a set of other points, the [

] trait provides a uniform interface to many different similarity search data structures. One such structure is the vantage-point tree, available in `NearestNeighbors`

as `acap`

:`VpTree`

` ``#` `use` `acap``::``euclid``::`Euclidean`;`
`use` `acap``::``vp``::`VpTree`;`
`use` `acap``::`NearestNeighbors`;`
`let` tree `=` `VpTree``::`balanced`(``vec!``[`
Euclidean`(``[``3``,` `4``]``)``,`
Euclidean`(``[``5``,` `12``]``)``,`
Euclidean`(``[``8``,` `15``]``)``,`
Euclidean`(``[``7``,` `24``]``)``,`
`]``)``;`

implements [`VpTree`

], which has a `NearestNeighbors`

method that returns an optional [`nearest``(``)`

]. The [`Neighbor`

] struct holds the actual neighbor it found, and the distance it was from the target:`Neighbor`

` ``#` `use` `acap``::``euclid``::`Euclidean`;`
`#` `use` `acap``::``vp``::`VpTree`;`
`#` `use` `acap``::`NearestNeighbors`;`
`#` `let` tree `=` `VpTree``::`balanced`(`
`#` `vec!``[`Euclidean`(``[``3``,` `4``]``)``,` Euclidean`(``[``5``,` `12``]``)``,` Euclidean`(``[``8``,` `15``]``)``,` Euclidean`(``[``7``,` `24``]``)``]`
`#` `)``;`
`let` nearest `=` tree`.``nearest``(``&``[``7``,` `7``]``)``.``unwrap``(``)``;`
`assert_eq!``(`nearest`.`item`,` `&`Euclidean`(``[``3``,` `4``]``)``)``;`
`assert_eq!``(`nearest`.`distance`,` `5``)``;`

[

] also provides the `NearestNeighbors`

, `nearest_within``(``)`

, and `k_nearest``(``)`

methods which find up to `k_nearest_within``(``)`

neighbors within a possible threshold.`k`

It can be expensive to compute nearest neighbors exactly, especially in high dimensions. For performance reasons, [

] implementations are allowed to return approximate results. Many implementations have a speed/accuracy tradeoff which can be tuned. Those implementations which always return exact results will also implement the [`NearestNeighbors`

] marker trait. For example, a `ExactNeighbors`

will be exact when the [`VpTree`

] function is a [`Proximity`

].`Metric`

#### Dependencies

~140KB