Crate kiddo

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:

• Its standard floating-point k-d tree, exposed as kiddo::KdTree
• integer / fixed point support via the Fixed library;
• f16 support via the half library;
• instant zero-copy deserialization and serialization via Rkyv (Serde still available).
• An ImmutableKdTree with space and performance advantages over the standard k-d tree, for situations where the tree does not need to be modified after creation

Kiddo is ideal for super-fast 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”

Installation

Add kiddo to Cargo.toml

[dependencies]
kiddo = "4.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.

• serialize - serialization / deserialization via Serde
• serialize_rkyv - zero-copy serialization / deserialization via Rkyv
• global_allocate (NIGHTLY) - When enabled Kiddo will use the unstable allocator_api feature within ImmutableKdTree to get a slight performance improvement when allocating space for leaves.
• simd (NIGHTLY) - enables some hand written SIMD and pre-fetch intrinsics code within ImmutableKdTree that may improve performance (currently only on nearest_one with f64)
• f16 - enables usage of f16 from the half crate for float trees.

Re-exports

• pub use best_neighbour::BestNeighbour;
• pub use float::distance::Manhattan;
• pub use float::distance::SquaredEuclidean;
• pub use nearest_neighbour::NearestNeighbour;

Modules

• best_neighbour
  A result item returned by a query
• distance_metric
  The trait that needs to be implemented by any distance metrics
• 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 if the f16 feature is enabled
• immutable
  Immutable k-d trees (faster and smaller, but slower to build).
• nearest_neighbour
  A result item returned by a query
• types
  Definitions for some types that are common between the fixed and float modules
• within_unsorted_iter
  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.