Struct goko::CoverTreeReader

pub struct CoverTreeReader<D: PointCloud> { /* fields omitted */ }

Cover Tree Reader Head

You can clone the reader head, though this is a relatively expensive operation and should not be performed lightly.

All queries of the covertree should go through a reader head. This includes queries you are doing to modify the tree. There are no thread locks anywhere in the code below the reader head, so it's fast.

The data structure is just a list of CoverLayerReaders, the parameter's object and the root address. Copies are relatively expensive as each CoverLayerReader contains several Arcs that need to be cloned.

Implementations

impl<D: PointCloud + LabeledCloud> CoverTreeReader<D>

pub fn get_node_label_summary_and<F, S>(
    &self,
    node_address: (i32, PointIndex),
    transform_fn: F
) -> Option<S> where
    F: Fn(&D::LabelSummary) -> S, 

Reads the contents of a plugin, due to the nature of the plugin map we have to access it with a closure.

impl<D: PointCloud> CoverTreeReader<D>

pub fn point_cloud(&self) -> &Arc<D>

A reference to the point cloud the tree was built on.

pub fn layer(&self, scale_index: i32) -> &CoverLayerReader<D>

Returns a borrowed reader for a cover layer.

pub fn scale(&self, scale_index: i32) -> f32

simple helper to get the scale from the scale index and the scale base, this is just b^i

pub fn get_node_and<F, T>(
    &self,
    node_address: (i32, PointIndex),
    f: F
) -> Option<T> where
    F: FnOnce(&CoverNode<D>) -> T, 

Read only access to the internals of a node.

pub fn get_node_children_and<F, T>(
    &self,
    node_address: (i32, PointIndex),
    f: F
) -> Option<T> where
    F: FnOnce(NodeAddress, &[NodeAddress]) -> T, 

Grabs all children indexes and allows you to query against them. Usually used at the tree level so that you can access the child nodes as they are not on this layer.

pub fn root_address(&self) -> NodeAddress

The root of the tree. Pass this to get_node_and to get the root node's content and start a traversal of the tree.

pub fn layers(&self) -> LayerIter<D>

An iterator for accessing the layers starting from the layer who holds the root.

pub fn len(&self) -> usize

Returns the number of layers in the tree. This is not the number of non-zero layers.

pub fn is_empty(&self) -> bool

Returns the number of layers in the tree. This is not the number of non-zero layers.

pub fn parameters(&self) -> &Arc<CoverTreeParameters<D>>

If you want to build a new tree with shared parameters, this is helpful.

pub fn node_count(&self) -> usize

This is the total number of nodes in the tree. This queries each layer, so it's not a simple return int.

pub fn scale_range(&self) -> Range<i32>

Returns the scale index range. It starts at the minimum min_res_index and ends at the top. You can reverse this for the correct order.

pub fn get_plugin_and<T: Send + Sync + 'static, F, S>(
    &self,
    transform_fn: F
) -> Option<S> where
    F: FnOnce(&T) -> S, 

Access the stored tree plugin

pub fn get_node_plugin_and<T: Send + Sync + 'static, F, S>(
    &self,
    node_address: (i32, PointIndex),
    transform_fn: F
) -> Option<S> where
    F: FnOnce(&T) -> S, 

Reads the contents of a plugin, due to the nature of the plugin map we have to access it with a closure.

pub fn knn<'a, T: Into<PointRef<'a>>>(
    &self,
    point: T,
    k: usize
) -> GokoResult<Vec<(f32, PointIndex)>>

The KNN query.

This works by recursively greedily querying the nearest child node with the lowest scale index to the point in question of a node, starting at the root until we hit a leaf. During this process all nodes touched are pushed onto a pair of min-heaps, one to keep track of the nodes' who have been not yet been queried for their children or singletons (called the child_heap, and the other to track the nodes who have not yet been queried for their singletons (called the singleton_heap). Both these heaps are min-heaps, ordering the nodes lexicographically by minimum possible distance to the point, then scale index, and finally the actual distance to the query point.

Once we reach the bottom we pop a node from the singleton_heap and if that node could have a point within range we query that node's singletons. These should be the closest to the query point. We then pop a node from the child_heap and repeat the greedy query starting from the popped node and terminating at a leaf.

The process terminates when there is no node that could cover a point in the tree closer than the furthest point we already have in our KNN.

See query_tools::KnnQueryHeap for the pair of heaps and mechanisms for tracking the minimum distance and the current knn set. See the nodes::CoverNode::singleton_knn and nodes::CoverNode::child_knn for the brute force node based knn.

pub fn routing_knn<'a, T: Into<PointRef<'a>>>(
    &self,
    point: T,
    k: usize
) -> GokoResult<Vec<(f32, PointIndex)>>

Same as knn, but only deals with non-singleton points

pub fn multiscale_knn<'a, T: Into<PointRef<'a>>>(
    &self,
    point: T,
    k: usize
) -> GokoResult<HashMap<i32, Vec<(f32, NodeAddress)>>>

Multiscale KNN

This tries to return the k closest node on each layer to the query point. It terminates when the closest node is a leaf node.

Todo: More Documentation, make this the k closest nodes on each layer.

pub fn path<'a, T: Into<PointRef<'a>>>(
    &self,
    point: T
) -> GokoResult<Vec<(f32, NodeAddress)>>

Dry Insert Query

pub fn known_path(
    &self,
    point_index: PointIndex
) -> GokoResult<Vec<(f32, NodeAddress)>>

pub fn node_fractal_dim(&self, node_address: NodeAddress) -> f32

Computes the fractal dimension of a node

pub fn node_weighted_fractal_dim(&self, node_address: NodeAddress) -> f32

Computes the weighted fractal dimension of a node

pub fn layer_fractal_dim(&self, scale_index: i32) -> f32

Computes the fractal dimension of a layer

pub fn layer_weighted_fractal_dim(&self, scale_index: i32) -> f32

Computes the weighted fractal dimension of a node

Trait Implementations

impl<D: PointCloud> Clone for CoverTreeReader<D>

fn clone(&self) -> CoverTreeReader<D>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.