abd-clam 0.17.0

Clustered Learning of Approximate Manifolds
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use distances::Number;

use crate::{cluster::Tree, dataset::Dataset};

#[derive(Clone, Copy, Debug)]
pub enum RnnAlgorithm {
    Linear,
    Clustered,
}

impl Default for RnnAlgorithm {
    fn default() -> Self {
        Self::Clustered
    }
}

impl RnnAlgorithm {
    pub fn search<T, U, D>(&self, query: T, radius: U, tree: &Tree<T, U, D>) -> Vec<(usize, U)>
    where
        T: Send + Sync + Copy,
        U: Number,
        D: Dataset<T, U>,
    {
        match self {
            Self::Linear => Self::linear_search(tree.data(), query, radius, tree.indices()),
            Self::Clustered => Self::clustered_search(tree, query, radius),
        }
    }

    pub(crate) fn linear_search<T, U, D>(data: &D, query: T, radius: U, indices: &[usize]) -> Vec<(usize, U)>
    where
        T: Send + Sync + Copy,
        U: Number,
        D: Dataset<T, U>,
    {
        let distances = data.query_to_many(query, indices);
        indices
            .iter()
            .copied()
            .zip(distances.into_iter())
            .filter(|&(_, d)| d <= radius)
            .collect()
    }

    pub(crate) fn clustered_search<T, U, D>(tree: &Tree<T, U, D>, query: T, radius: U) -> Vec<(usize, U)>
    where
        T: Send + Sync + Copy,
        U: Number,
        D: Dataset<T, U>,
    {
        let data = tree.data();

        // Tree search.
        let [confirmed, straddlers] = {
            let mut confirmed = Vec::new();
            let mut straddlers = Vec::new();
            let mut candidates = vec![tree.root()];

            let (mut terminal, mut non_terminal): (Vec<_>, Vec<_>);
            while !candidates.is_empty() {
                (terminal, non_terminal) = candidates
                    .drain(..)
                    .map(|c| (c, c.distance_to_instance(data, query)))
                    .filter(|&(c, d)| d <= (c.radius + radius))
                    .partition(|&(c, d)| (c.radius + d) <= radius);
                confirmed.append(&mut terminal);

                (terminal, non_terminal) = non_terminal.drain(..).partition(|&(c, _)| c.is_leaf());
                straddlers.append(&mut terminal);

                candidates = non_terminal
                    .drain(..)
                    .flat_map(|(c, d)| {
                        if d < c.radius {
                            c.overlapping_children(data, query, radius)
                        } else {
                            c.children().unwrap().to_vec()
                        }
                    })
                    .collect();
            }

            [confirmed, straddlers]
        };

        // Leaf Search
        let hits = confirmed.into_iter().flat_map(|(c, d)| {
            let distances = if c.is_singleton() {
                vec![d; c.cardinality]
            } else {
                data.query_to_many(query, c.indices(data))
            };
            c.indices(data).iter().copied().zip(distances.into_iter())
        });

        let indices = straddlers
            .into_iter()
            .flat_map(|(c, _)| c.indices(data))
            .copied()
            .collect::<Vec<_>>();

        hits.chain(Self::linear_search(data, query, radius, &indices).into_iter())
            .collect()
    }
}