Struct goko::query_tools::KnnQueryHeap

pub struct KnnQueryHeap { /* fields omitted */ }

The heaps for doing a fairly efficient KNN query. There are 3 heaps, the child min-heap, singleton min-heap, and distance max-heap. The distance heap is for the output KNN, each node or point that’s pushed onto the heap is pushed onto this distance heap. If the heap grows past K it’s popped off. This provides an estimate for the distance to the furthest nearest neighbor out of the k.

The child and singleton heaps are for nodes only. The names are a bit of a misnomer, the child heap is for nodes where we haven’t checked their children yet, and the singleton heap is for those nodes where we haven’t checked their singletons. Next to these is a hashmap that records the minimum distance a point could have to a point covered by that node. Togther with the current max distance (from the distance max-heap) K this can help with the KNN query.

To help with double inserts (easy due to a node’s central point’s index being repeated througout the tree), we also have a HashSet of visited points. We reject a node insert if it’s central point index is in this hashset.

Implementations

impl KnnQueryHeap

pub fn new(k: usize, scale_base: f32) -> KnnQueryHeap

Creates a new KNN heap. The K is obvious, but the scale_base is for the minimum distance from our query point to potential covered points of a node.

pub fn closest_unvisited_child_covering_address(
    &mut self
) -> Option<(f32, NodeAddress)>

Finds the closest node who could have a child node at least the current kth furthest distance away from the query point. This pops that node and pushes it onto the singleton heap.

pub fn closest_unvisited_singleton_covering_address(
    &mut self
) -> Option<(f32, NodeAddress)>

Finds the closest node who could have a singleton at least the current kth furthest distance away from the query point. This pops the node and sends it to oblivion.

pub fn len(&self) -> usize

The current number of points on the distance heap

pub fn is_empty(&self) -> bool

The current number of points on the distance heap

pub fn node_len(&self) -> usize

The current number of points still on the

pub fn max_dist(&self) -> f32

The current maximum distance to the query point. If the distance heap isn’t full it returns the maximum float value.

pub fn unpack(self) -> Vec<(f32, usize)>

Unpacks the distance heap. This consumes the query heap.

pub fn increase_estimated_distance(
    &mut self,
    address: NodeAddress,
    new_estimate: f32
)

This allows you to update the minimum distance to the parent of a node, or it’s siblings. If you are well within the radius of coverage of a node, this allows you to remove the parent or sibling from the closest_unvisited_child_covering_address and closest_unvisited_singleton_covering_address queries.

Trait Implementations

impl Debug for KnnQueryHeap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl RoutingQueryHeap for KnnQueryHeap

fn push_nodes(
    &mut self,
    indexes: &[NodeAddress],
    dists: &[f32],
    parent_address: Option<NodeAddress>
)

Shove a bunch of nodes onto the heap. Optionally, if you pass a parent node it updates the distance to that parent node.

impl SingletonQueryHeap for KnnQueryHeap

fn push_outliers(&mut self, indexes: &[usize], dists: &[f32])

Shove a bunch of single points onto the heap