goko 0.5.5

A lock-free, eventually consistent, concurrent covertree.
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

//! # Diagonal Gaussian
//!
//! This computes a coordinate bound multivariate Gaussian. This can be thought of as a rough
//! simulation of the data underling a node. However we can chose the scale from which we
//! simulate the data, down to the individual point, so this can be arbitrarily accurate.

use super::*;
use crate::covertree::node::CoverNode;
use crate::covertree::CoverTreeReader;
use crate::plugins::utils::*;

use ndarray::prelude::*;
use ndarray_linalg::svd::*;

/// Node component, coded in such a way that it can be efficiently, recursively computed.
#[derive(Debug, Clone, Default)]
pub struct SvdGaussian {
    /// Mean of this gaussian
    pub mean: Array1<f32>,
    /// Second Moment
    pub vt: Array2<f32>,
    /// The singular values
    pub singular_vals: Array1<f32>,
}
/*
impl ContinousDistribution for SvdGaussian {
    fn ln_pdf(&self, _point: &PointRef) -> Option<f64> {
        unimplemented!()
    }

    fn sample<R: Rng>(&self, _rng: &mut R) -> Vec<f32> {
        unimplemented!()
    }

    fn kl_divergence(&self, _other: &SvdGaussian) -> Option<f64> {
        unimplemented!()
    }
}
*/
impl SvdGaussian {
    /// Mean: `moment1/count`
    pub fn mean(&self) -> Array1<f32> {
        self.mean.clone()
    }
}

impl<D: PointCloud> NodePlugin<D> for SvdGaussian {}

/// Zero sized type that can be passed around. Equivilant to `()`
#[derive(Debug, Clone)]
pub struct GokoSvdGaussian {
    max_points: usize,
    min_points: usize,
    tau: f32,
}

impl GokoSvdGaussian {
    /// Specify the max number of points, and the min that you want to compute the SVD over, and the tau used for dimension calulations
    pub fn new(min_points: usize, max_points: usize, tau: f32) -> GokoSvdGaussian {
        GokoSvdGaussian {
            max_points,
            min_points,
            tau,
        }
    }
}

impl<D: PointCloud> GokoPlugin<D> for GokoSvdGaussian {
    type NodeComponent = SvdGaussian;
    fn prepare_tree(parameters: &Self, my_tree: &mut CoverTreeWriter<D>) {
        my_tree.add_plugin::<GokoCoverageIndexes>(GokoCoverageIndexes::restricted(
            parameters.max_points,
        ));
        my_tree.add_plugin::<GokoDiagGaussian>(GokoDiagGaussian::recursive());
    }
    fn node_component(
        parameters: &Self,
        my_node: &CoverNode<D>,
        my_tree: &CoverTreeReader<D>,
    ) -> Option<Self::NodeComponent> {
        if my_node.coverage_count() > parameters.min_points {
            let points = my_node.get_plugin_and::<CoverageIndexes, _, _>(|p| {
                my_tree
                    .parameters()
                    .point_cloud
                    .points_dense_matrix(p.point_indexes())
                    .unwrap()
            });
            if let Some(mut points) = points {
                let mean = my_node
                    .get_plugin_and::<DiagGaussian, _, _>(|p| {
                        Array1::from_shape_vec((p.dim(),), p.mean()).unwrap()
                    })
                    .unwrap();
                for mut p in points.axis_iter_mut(Axis(0)) {
                    p -= &mean;
                }

                let (_u, singular_vals, vt) = points.svd(false, true).unwrap();
                let vt = vt.unwrap();
                Some(SvdGaussian {
                    singular_vals,
                    vt,
                    mean,
                })
            } else {
                None
            }
        } else {
            None
        }
    }
}
/*
#[cfg(test)]
pub(crate) mod tests {
    use super::*;
    use crate::covertree::tests::build_basic_tree;
}
*/