### 4 releases (2 breaking)

0.3.0 | Oct 24, 2021 |
---|---|

0.2.0 | Aug 24, 2020 |

0.1.1 | Jun 30, 2020 |

0.1.0 | Jun 24, 2020 |

#**757** in Algorithms

**275** downloads per month

**MIT**license

105KB

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 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`;`
`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``::``knn``::`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`

# Examples

## Searching without owning

Since

has a blanket implementation for references, you can store references in a
nearest neighbor index instead of having it hold the data itself:`Proximity`

` ``use` `acap``::``euclid``::`Euclidean`;`
`use` `acap``::``knn``::`NearestNeighbors`;`
`use` `acap``::``vp``::`VpTree`;`
`let` points `=` `vec!``[`
Euclidean`(``[``3``,` `4``]``)``,`
Euclidean`(``[``5``,` `12``]``)``,`
Euclidean`(``[``8``,` `15``]``)``,`
Euclidean`(``[``7``,` `24``]``)``,`
`]``;`
`let` tree `=` `VpTree``::`balanced`(`points`.``iter``(``)``)``;`
`let` nearest `=` tree`.``nearest``(``&&``[``7``,` `7``]``)``.``unwrap``(``)``;`
`assert!``(``std``::``ptr``::`eq`(``*`nearest`.`item`,` `&`points`[``0``]``)``)``;`

## Custom distance functions

See the

documentation.`Proximity`

#### Dependencies

~155KB