space

A library providing abstractions for spatial datastructures and search

If you use a kNN datastructure library and would like to have the Knn trait implemented on its types natively, please raise an issue on that library. Similarly, crates which define datapoints with specific distance metrics, and not general linear algebra crates, can implement the MetricPoint trait.

See the bitarray crate for an implementation of MetricPoint using hamming distance (with optional, though unstable, 512-bit SIMD support, and always-on 64-bit popcnt instruction support).

Usage

use space::Metric;

struct Hamming;

impl Metric<u8> for Hamming {
    type Unit = u8;

    fn distance(&self, &a: &u8, &b: &u8) -> Self::Unit {
        (a ^ b).count_ones() as u8
    }
}

use space::{Knn, KnnFromBatch, LinearKnn, Metric, Neighbor};

#[derive(Default)]
struct Hamming;

impl Metric<u8> for Hamming {
    type Unit = u8;

    fn distance(&self, &a: &u8, &b: &u8) -> Self::Unit {
        (a ^ b).count_ones() as u8
    }
}

let data = vec![
    (0b1010_1010, 12),
    (0b1111_1111, 13),
    (0b0000_0000, 14),
    (0b1111_0000, 16),
    (0b0000_1111, 10),
];

let search: LinearKnn<Hamming, _> = KnnFromBatch::from_batch(data.iter());

assert_eq!(
    &search.knn(&0b0101_0000, 3),
    &[
        (
            Neighbor {
                index: 2,
                distance: 2
            },
            &data[2].0,
            &data[2].1
        ),
        (
            Neighbor {
                index: 3,
                distance: 2
            },
            &data[3].0,
            &data[3].1
        ),
        (
            Neighbor {
                index: 0,
                distance: 6
            },
            &data[0].0,
            &data[0].1
        )
    ]
);

Benchmarks

To run the benchmarks, use the following command:

cargo bench --all-features

If you do not pass --all-features, the benchmark wont run. Due to this issue, the SIMD feature must be enabled. Cargo offers no way to automatically bring the SIMD feature in for the benchmark, and thus it must be passed at the command line.