## srtree

Rust implementation of SR-Tree: a high-dimensional nearest neighbor search index

### 3 unstable releases

 0.2.1 Jun 21, 2023 May 31, 2023 May 16, 2023

#1321 in Algorithms

Apache-2.0

43KB
1K SLoC

# srtree

Rust implementation of SR-Tree: nearest neighbor search index for high-dimensional clustered datasets, modified to support variance-based bulk-loading. This crate applies fundamental concepts presented in the paper, and the original C++ version can be found here.

## Examples

This example shows how to query nearest neighbors on Euclidean SRTree:

``````use srtree::SRTree;

fn main() {
let points = vec![
vec![0., 0.],
vec![1., 1.],
vec![2., 2.],
vec![3., 3.],
vec![4., 4.],
];
let tree = SRTree::euclidean(&points).expect("Failed to build SRTree");

let (indices, distances) = tree.query(&[8., 8.], 3);
println!("{indices:?}"); // [4, 3, 2] (sorted by distance)
println!("{distances:?}");
}
``````

Other distance metrics can be defined using `Metric` trait:

``````use srtree::{SRTree, Metric};

struct Manhattan;
impl Metric<f64> for Manhattan {
fn distance(&self, point1: &[f64], point2: &[f64]) -> f64 {
point1.iter().zip(point2).map(|(a, b)| (a - b).abs()).sum()
}

fn distance_squared(&self, _: &[f64], _: &[f64]) -> f64 {
0.
}
}

fn main() {
let points = vec![
vec![0., 0.],
vec![1., 1.],
vec![2., 2.],
vec![3., 3.],
vec![4., 4.],
];
let tree = SRTree::default(&points, Manhattan).expect("Failed to build SRTree");
let (indices, distances) = tree.query(&[8., 8.], 3);
println!("{indices:?}"); // [4, 3, 2] (sorted by distance)
println!("{distances:?}"); // [8., 10., 12.]
}
``````