VP-tree nearest neighbor search
A relatively simple and readable Rust implementation of Vantage Point tree search algorithm.
The VP tree algorithm doesn't need to know coordinates of items, only distances between them. It can efficiently search multi-dimensional spaces and abstract things as long as you can define similarity between them (e.g. points, colors, and even images).
Please see the API reference or examples for details.
This algorithm does not work with squared distances. When implementing Euclidean distance, you MUST use sqrt()
. Vantage Point trees require metric spaces.
/// `MetricSpace` makes items comparable. It's a bit like Rust's `PartialOrd`.
Implementing MetricSpace
for Rust built-in types
This library includes a workaround for orphan rules. You need to add your crate's type when implementing MetricSpace
:
; // it can be any type, as long as it's yours
Memory efficiency tip
Tree
clones all the items and puts them in the tree. If the items are too big to clone and you'd rather keep the items elsewhere, you can!
Instead of storing the items, make the tree store indices into your items storage, and pass actual items as user_data
to your MetricSpace::distance()
function.
let items = /* your actual items are here */;
let indices: = .collect;
let tree = new_with_user_data_ref;
let res = tree.find_nearest;