#space #knn #ann #search

no-std space

A library providing abstractions for spatial datastructures and search

35 releases (17 breaking)

0.18.0 Aug 14, 2021
0.17.0 Jul 18, 2021
0.16.0 Jul 18, 2021
0.10.3 Mar 5, 2020
0.6.0 Nov 20, 2018

#260 in Data structures

Download history 833/week @ 2022-08-10 597/week @ 2022-08-17 734/week @ 2022-08-24 625/week @ 2022-08-31 924/week @ 2022-09-07 406/week @ 2022-09-14 415/week @ 2022-09-21 309/week @ 2022-09-28 992/week @ 2022-10-05 628/week @ 2022-10-12 462/week @ 2022-10-19 657/week @ 2022-10-26 1335/week @ 2022-11-02 1244/week @ 2022-11-09 671/week @ 2022-11-16 458/week @ 2022-11-23

3,896 downloads per month
Used in 11 crates (8 directly)

MIT license

16KB
155 lines

space

Discord Crates.io MIT/Apache docs.rs LoC Tests Lints no_std

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.

Dependencies

~110–320KB