A high-performance, flexible, ergonomic k-d tree library. Possibly the fastest k-d tree library in the world? See for yourself.

• Crate
• Documentation
• Usage
• Examples
• Benchmarks
• Change Log
• License

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".

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

Add kiddo to Cargo.toml

[dependencies]
kiddo = "4.2.0"

Add points to kdtree and query nearest n points with distance function

use kiddo::{KdTree, SquaredEuclidean};

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 tree: KdTree<_, 2> = (&entries).into();

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

// find the nearest item to [0f64, 0f64].
// returns an instance of kiddo::NearestNeighbour
let nearest = tree.nearest_one::<SquaredEuclidean>(&[0f64, 0f64]);
assert_eq!(nearest.distance, 0f64);
assert_eq!(nearest.item, 0);


// find the nearest 3 items to [0f64, 0f64]
// // returns an Vec of kiddo::NearestNeighbour
let nearest_n: Vec<_> = tree.nearest_n::<SquaredEuclidean>(&[0f64, 0f64], 3);
assert_eq!(
    nearest_n.iter().map(|x|(x.distance, x.item)).collect::<Vec<_>>(),
    vec![(0f64, 0), (2f64, 1), (8f64, 2)]
);

See the examples documentation for some more detailed examples.

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 intrinsic code within ImmutableKdTree that may improve performance (currently only on the nearest_one method when using f64)
• f16 - enables usage of f16 from the half crate for float trees.

Version 3.x changed the distance metrics syntax, switching from function pointers to a trait-based approach that permitted some ergonomics and performance improvements. This is a breaking change though: whereas prior to v3, you may have had queries that look like this:

use kiddo::distance::squared_euclidean;
let result = kdtree.nearest_one(&[0f64, 0f64], &squared_euclidean);

Now for v3 onwards, you'll need to switch to this syntax:

use kiddo::SquaredEuclidean;
let result = kdtree.nearest_one::<SquaredEuclidean>(&[0f64, 0f64]);

V3 also introduces the ImmutableKdTree variant. Designed for use cases where all the points that you need to add to the tree are known up-front, and no modifications need to be made after the tree is initially populated. ImmutableKdTree balances and optimises the tree at construction time, ensuring much more efficient memory usage (and a correspondingly smaller size on-disk for serialized trees). Since the interior nodes of the ImmutableKdTree also take up less space in memory, more of them can fit in the CPU cache, potentially improving performance in some cases.

Version 2.x was a complete rewrite, providing:

• a new internal architecture for much-improved performance;
• Added integer / fixed point support via the Fixed library;
• instant zero-copy deserialization and serialization via Rkyv (Serde still available).
• See the changelog for a detailed run-down on all the changes made in v2.

The results of all the below benchmarks are viewable in an interactive webapp over at https://sdd.github.io/kd-tree-comparison-webapp/.