rcf3 0.2.0

A Rust implementation of the Random Cut Forest algorithm for anomaly detection.
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
106
107
108
109
110

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

use crate::bounding_box::BoundingBox;

pub const NULL: usize = usize::MAX;

// ---------------------------------------------------------------------------
// Node representation
// ---------------------------------------------------------------------------

/// A node in the random-cut tree.
///
/// Leaves track the point they contain and the number of duplicate arrivals.
/// Internal nodes track the split criterion and the tight bounding-box of
/// their entire sub-tree (kept up-to-date on every insert / delete).
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum Node {
    Leaf {
        /// Index into the forest-wide [`crate::point_store::PointStore`].
        point_idx: usize,
        /// Number of identical (duplicate) points at this leaf.
        mass: usize,
    },
    Internal {
        left: usize,
        right: usize,
        cut_dim: usize,
        cut_val: f32,
        /// Total number of point-observations in this sub-tree (counting duplicates).
        mass: usize,
        bbox: BoundingBox,
    },
}

impl Node {
    pub fn mass(&self) -> usize {
        match self {
            Node::Leaf { mass, .. } => *mass,
            Node::Internal { mass, .. } => *mass,
        }
    }

    pub fn is_leaf(&self) -> bool {
        matches!(self, Node::Leaf { .. })
    }
}

// ---------------------------------------------------------------------------
// Arena allocator
// ---------------------------------------------------------------------------

/// Arena of [`Node`]s with O(1) alloc / free.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct NodeArena {
    nodes: Vec<Option<Node>>,
    free: Vec<usize>,
}

impl NodeArena {
    pub fn new(initial_capacity: usize) -> Self {
        NodeArena {
            nodes: Vec::with_capacity(initial_capacity),
            free: Vec::new(),
        }
    }

    /// Allocate a new node and return its index.
    pub fn alloc(&mut self, node: Node) -> usize {
        if let Some(id) = self.free.pop() {
            self.nodes[id] = Some(node);
            id
        } else {
            let id = self.nodes.len();
            self.nodes.push(Some(node));
            id
        }
    }

    /// Return the node at `id`.  Panics if `id` is NULL or freed.
    pub fn get(&self, id: usize) -> &Node {
        self.nodes[id]
            .as_ref()
            .expect("accessed freed or uninitialized node")
    }

    /// Mutably return the node at `id`.
    pub fn get_mut(&mut self, id: usize) -> &mut Node {
        self.nodes[id]
            .as_mut()
            .expect("accessed freed or uninitialized node")
    }

    /// Free the node at `id`.
    pub fn free(&mut self, id: usize) {
        debug_assert!(id < self.nodes.len());
        self.nodes[id] = None;
        self.free.push(id);
    }

    /// Number of allocated slots (including freed ones).
    pub fn slot_count(&self) -> usize {
        self.nodes.len()
    }
}