Crate vpsearch

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

Project page.

This algorithm does not work with squared distances. When implementing Euclidean distance, you MUST use sqrt(). You really really can't use that optimization. There's no way around it. Vantage Point trees require metric spaces.

#[derive(Copy, Clone)]
struct Point {
    x: f32, y: f32,
}

impl vpsearch::MetricSpace for Point {
    type UserData = ();
    type Distance = f32;

    fn distance(&self, other: &Self, _: &Self::UserData) -> Self::Distance {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx*dx + dy*dy).sqrt() // sqrt is required
    }
}

fn main() {
    let points = vec![Point{x:2.0,y:3.0}, Point{x:0.0,y:1.0}, Point{x:4.0,y:5.0}];
    let vp = vpsearch::Tree::new(&points);
    let (index, _) = vp.find_nearest(&Point{x:1.0,y:2.0});
    println!("The nearest point is at ({}, {})", points[index].x, points[index].y);
}

#[derive(Clone)]
struct LotsaDimensions<'a>(&'a [u8; 64]);

impl<'a> vpsearch::MetricSpace for LotsaDimensions<'a> {
    type UserData = ();
    type Distance = f64;

    fn distance(&self, other: &Self, _: &Self::UserData) -> Self::Distance {
        let dist_squared = self.0.iter().copied().zip(other.0.iter().copied())
            .map(|(a, b)| {
                (a as i32 - b as i32).pow(2) as u32
            }).sum::<u32>();

        (dist_squared as f64).sqrt() // sqrt is required
    }
}

fn main() {
    let points = vec![LotsaDimensions(&[0; 64]), LotsaDimensions(&[5; 64]), LotsaDimensions(&[10; 64])];
    let vp = vpsearch::Tree::new(&points);
    let (index, _) = vp.find_nearest(&LotsaDimensions(&[6; 64]));
    println!("The {}th element is the nearest", index);
}

Structs

Tree	The VP-Tree.

Traits

BestCandidate	You can implement this if you want to peek at all visited elements
MetricSpace	Elements you're searching for must be comparable using this trait.