[−][src]Struct goko::query_tools::KnnQueryHeap
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
[src]
pub fn new(k: usize, scale_base: f32) -> KnnQueryHeap
[src]
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)>
[src]
&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)>
[src]
&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
[src]
The current number of points on the distance heap
pub fn is_empty(&self) -> bool
[src]
The current number of points on the distance heap
pub fn node_len(&self) -> usize
[src]
The current number of points still on the
pub fn max_dist(&self) -> f32
[src]
The current maximum distance to the query point. If the distance heap isn't full it returns the maximum float value.
pub fn unpack(mut self: Self) -> Vec<(f32, usize)>
[src]
Unpacks the distance heap. This consumes the query heap.
pub fn increase_estimated_distance(
&mut self,
address: NodeAddress,
new_estimate: f32
)
[src]
&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
[src]
impl RoutingQueryHeap for KnnQueryHeap
[src]
fn push_nodes(
&mut self,
indexes: &[NodeAddress],
dists: &[f32],
parent_address: Option<NodeAddress>
)
[src]
&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
[src]
Auto Trait Implementations
impl RefUnwindSafe for KnnQueryHeap
[src]
impl Send for KnnQueryHeap
[src]
impl Sync for KnnQueryHeap
[src]
impl Unpin for KnnQueryHeap
[src]
impl UnwindSafe for KnnQueryHeap
[src]
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> Cast<U> for T where
U: FromCast<T>,
U: FromCast<T>,
pub fn cast(self) -> U
impl<T> From<T> for T
[src]
impl<T> FromCast<T> for T
pub fn from_cast(t: T) -> T
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Pointable for T
pub const ALIGN: usize
type Init = T
The type for initializers.
pub unsafe fn init(init: <T as Pointable>::Init) -> usize
pub unsafe fn deref<'a>(ptr: usize) -> &'a T
pub unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T
pub unsafe fn drop(ptr: usize)
impl<T> Same<T> for T
type Output = T
Should always be Self
impl<SS, SP> SupersetOf<SS> for SP where
SS: SubsetOf<SP>,
SS: SubsetOf<SP>,
pub fn to_subset(&self) -> Option<SS>
pub fn is_in_subset(&self) -> bool
pub unsafe fn to_subset_unchecked(&self) -> SS
pub fn from_subset(element: &SS) -> SP
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,