As Close As Possible — nearest neighbor search in Rust.
The notion of distances between points is captured by the
Proximity trait. Its
distance() method returns a
Distance, from which the actual numerical distance may be
value(). These layers of abstraction allow
acap to work with generically
with different distance functions over different types.
There are no restrictions on the distances computed by a
Proximity. For example, they don't
have to be symmetric, subadditive, or even positive. Implementations that do have these
desirable properties will additionally implement the
Metric marker trait. This distinction
acap to support a wide variety of useful metric and non-metric distances.
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,
distance() doesn't return a number directly; as an optimization, it returns a
EuclideanDistance 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:
use acap::distance::Distance; let d = a.distance(&b); assert!(d > 4 && d < 6); assert_eq!(d, 5); assert_eq!(d.value(), 5.0f32);
For finding the nearest neighbors to a point from a set of other points, the
NearestNeighbors trait provides a uniform interface to many different similarity search
data structures. One such structure is the vantage-point tree, available in
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);
It can be expensive to compute nearest neighbors exactly, especially in high dimensions.
For performance reasons,
NearestNeighbors 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
marker trait. For example, a
VpTree will be exact when the
Proximity function is a
Abstract notions of distance.
Exhaustive nearest neighbor search.
A nearest neighbor.
Marker trait for NearestNeighbors implementations that always return exact results.
A nearest neighbor search index.
Accumulates nearest neighbor search results.