Struct space::LinearKnn

pub struct LinearKnn<M, I> {
    pub metric: M,
    pub points: I,
}

Performs a linear knn search by iterating over everything in the space and performing a binary search on running set of neighbors.

Example

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

#[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, 2),
    &[
        (Neighbor { index: 2, distance: 2 }, &data[2].0, &data[2].1),
        (Neighbor { index: 3, distance: 2 }, &data[3].0, &data[3].1),
    ]
);

Fields

metric: M

points: I

Trait Implementations

impl<'a, M: Metric<P>, I, P: 'a, V: 'a> Knn<'a> for LinearKnn<M, I> where
    I: Iterator<Item = &'a (P, V)> + Clone, 

type Ix = usize

type Metric = M

type Point = P

type Value = V

type KnnIter = Vec<(Neighbor<M::Unit>, &'a P, &'a V)>

fn point(&self, index: Self::Ix) -> &'a Self::Point

Get a point using a neighbor index returned by Knn::knn or Knn::nn.

fn value(&self, index: Self::Ix) -> &'a Self::Value

Get a value using a neighbor index returned by Knn::knn or Knn::nn.

fn knn(&'a self, query: &Self::Point, num: usize) -> Self::KnnIter

Get num nearest neighbor keys and values of target.

fn nn(
    &self,
    query: &Self::Point
) -> Option<(Neighbor<<Self::Metric as Metric<Self::Point>>::Unit, Self::Ix>, &'a Self::Point, &'a Self::Value)>

Get the nearest neighbor key and values of target.

impl<'a, M, I> KnnFromMetricAndBatch<M, I> for LinearKnn<M, I> where
    M: Default, 

fn from_metric_and_batch(metric: M, points: I) -> Self