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:

• 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 space and 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 serialization via Rkyv (Serde still available).

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 = "5.0.3"

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
• 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 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 if the f16 feature is enabled.

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.