Crate kiddo

Crate kiddo 

Source
Expand description

§Kiddo

A high-performance, flexible, ergonomic k-d tree library.

Possibly the fastest k-d tree library in the world? See for yourself.

Kiddo provides:

  • A standard floating-point k-d tree, exposed as kiddo::KdTree, for when you may need to add or remove points to the tree after the initial construction / deserialization
  • An ImmutableKdTree with performance and space advantages over the standard k-d tree, for situations where the tree does not need to be modified after creation
  • integer / fixed point support via the fixed crate;
  • f16 support via the half crate;
  • instant zero-copy deserialization and serialisation via Rkyv (Serde still available).

Kiddo is ideal for superfast spatial / geospatial lookups and nearest-neighbour / KNN queries for low-ish numbers of dimensions, where you want to ask questions such as:

  • Find the nearest_n item(s) to a query point, ordered by distance;
  • Find all items within a specified radius of a query point;
  • Find the “best” n item(s) within a specified distance of a query point, for some definition of “best”, For example, “give me the 5 largest settlements within 50km of a given point, ordered by descending population”, or “the 5 brightest stars within a degree of a point on the sky, ordered by brightest first”.

§Installation

Add kiddo to Cargo.toml

[dependencies]
kiddo = "5.2.0"

§Usage

use kiddo::KdTree;
use kiddo::SquaredEuclidean;
use kiddo::NearestNeighbour;

let entries = vec![
    [0f64, 0f64],
    [1f64, 1f64],
    [2f64, 2f64],
    [3f64, 3f64]
];

// use the kiddo::KdTree type to get up and running quickly with default settings
let mut kdtree: KdTree<_, 2> = (&entries).into();

// How many items are in tree?
assert_eq!(kdtree.size(), 4);

// find the nearest item to [0f64, 0f64].
// returns a tuple of (dist, index)
assert_eq!(
    kdtree.nearest_one::<SquaredEuclidean>(&[0f64, 0f64]),
    NearestNeighbour { distance: 0f64, item: 0 }
);

// find the nearest 3 items to [0f64, 0f64], and collect into a `Vec`
assert_eq!(
    kdtree.nearest_n::<SquaredEuclidean>(&[0f64, 0f64], 3),
    vec![NearestNeighbour { distance: 0f64, item: 0 }, NearestNeighbour { distance: 2f64, item: 1 }, NearestNeighbour { distance: 8f64, item: 2 }]
);

See the examples documentation for some more in-depth examples.

§Optional Features

The Kiddo crate exposes the following features. Any labelled as (NIGHTLY) are not available on stable Rust as they require some unstable features. You’ll need to build with nightly in order to user them.

  • serde - serialization / deserialization via Serde
  • rkyv - zero-copy serialization / deserialization via Rkyv version 0.7.x
  • rkyv_08 - zero-copy serialization / deserialization via Rkyv version 0.8.x
  • simd (NIGHTLY) - enables some handwritten SIMD and pre-fetch intrinsics code within ImmutableKdTree that may improve performance (currently only on nearest_one with f64)
  • fixed - enables usage of kiddo::fixed::KdTree for use with the fixed library’s fixed-point number types

NOTE: Support for rkyv 0.7 is now deprecated and will be removed in Kiddo v6.

Re-exports§

pub use float::distance::Manhattan;
pub use float::distance::SquaredEuclidean;

Modules§

fixed
Fixed point k-d tree, for use when the co-ordinates of the points being stored in the tree are fixed point or integers. u8, u16, u32, and u64 based fixed-point / integers are supported via the Fixed crate, eg FixedU16<U14> for a 16-bit fixed point number with 14 bits after the decimal point.
float
Floating point k-d tree, for use when the co-ordinates of the points being stored in the tree are floats. f64 or f32 are the types that are supported for use as co-ordinates, or f16 when used with the half crate
immutable
Immutable k-d trees (faster and smaller, but cannot be modified after construction).
traits
Definitions and implementations for some traits that are common between the float, immutable and fixed modules

Structs§

BestNeighbour
Represents an entry in the results of a “best” query, with distance being the distance of this particular item from the query point, and item being the stored item index that was found as part of the query.
NearestNeighbour
Represents an entry in the results of a nearest neighbour query, with distance being the distance of this particular item from the query point, and item being the stored item index that was found as part of the query.
WithinUnsortedIter
Iterator object returned by within_unsorted_iter

Type Aliases§

ImmutableKdTree
An immutable floating-point k-d tree with default parameters.
KdTree
A floating-point k-d tree with default parameters.