Crate kiddo 

Kiddo

A high-performance k-d tree library for exact and approximate nearest-neighbour queries in low-dimensional spaces.

Built with an aggressive focus on query performance, including cache-aware layouts and optional SIMD-accelerated code paths. See the companion benchmarking site to compare Kiddo against other k-d tree implementations across a range of workloads.

Kiddo v6 provides a single generic KdTree that supports floating-point (f64, f32, f16), selected fixed-point (via the fixed crate), and unsigned-integer (u8, u16, u32) types as coordinates, along with both mutable and immutable usage patterns.

Kiddo is designed for low-dimensional (< ~10D) search problems, especially 2D, 3D, and 4D workloads. Typical use cases include point-cloud analysis, astronomical catalogue crossmatching, colour quantization and palette lookup, local neighbourhood queries in simulations, and other nearest-neighbour and radius-search tasks. Kiddo has been used for diverse geographical and scientific workloads including geocoding, astronomy, cosmology, computer-aided drug discovery, crystallography, and computational neuroscience.

Kiddo supports the following query types:

• Exact Nearest Neighbour: Useful for tasks like finding the nearest airport to a given location, or finding the nearest catalogued star to a sky position. tree.query(&point).nearest_one().execute()
• k-nearest-neighbour (k-NN) search, finding the k nearest items to a query point:
  • ordered by distance: tree.query(&point).nearest_n(5).execute(). Useful for finding the nearest weather stations or sensors to a location, or generating candidate correspondences for point-cloud registration.
  • k items within a max radius: tree.query(&point).nearest_n(5).within(max_dist).execute(). Useful when you want the closest local neighbours inside a meaningful cutoff, such as the nearest shops within 5 miles, or nearby atoms within an interaction radius.
  • All items within a radius: tree.query(&point).within(max_dist).execute(). Finds all items within a specified radius of a query point, ordered by distance. Useful for radial catalogue searches in astronomy, or collision and proximity queries where the full neighbourhood is needed in sorted order.
  • Unsorted, e.g. tree.query(&point).nearest_n(5).within(max_dist).unsorted().execute(): This is often faster than the sorted radius-query form when result order does not matter, such as finding all customers within 5 miles of a store, or collecting point-cloud neighbourhoods for clustering or normal estimation.
• Approximate nearest-neighbour (ANN) search: tree.query(&point).nearest_one().approx().execute() Returns a good approximate nearest item. Generally much faster than exact nearest-neighbour search. Useful for latency-sensitive workloads like interactive point-cloud picking, or mapping image pixels to a palette colour during colour quantization.
• “best” n items: tree.query(&point).best_n(5, max_dist).execute(). Finds the “best” n items 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 brightest first”. This only makes semantic sense when your item type has meaningful ordering; for points-only trees with T = (), the query is allowed but not useful.
• Periodic Boundary Conditions (PBC), whereby the points in the tree are considered to represent a single subunit that repeats across space. Useful primarily for simulations, such as within cosmology or molecular dynamics simulations: tree.query(&point).periodic_boundary_condition(box_size).within(max_dist).execute()
• Exclusive Boundary Queries, where the query radius filter is an exclusive boundary (< max_dist), rather than the default inclusive boundary (<= max_dist): tree.query(&point).within(max_dist).exclusive_boundaries().execute()

If your points are known up front and the tree will be built once and then queried, start with ImmutableKdTree. It offers the best query performance and pairs well with rkyv for zero-copy loading of prebuilt trees from disk; when used with memory-mapped files, loading can be effectively instant.

If you need to add or remove points after construction, start with MutableKdTree. Mutable trees remain a good fit for many dynamic workloads. They do not continuously rebalance, although a stem strategy may perform a safety rebuild when growth makes its layout pathologically unbalanced. Workloads with substantial growth or heavy churn may still benefit from periodic caller-controlled rebuilds.

ImmutableKdTree and MutableKdTree are convenience aliases for KdTree with sensible defaults for these common read-heavy and mutable workloads.

Kiddo is not intended as a library for high-dimensional vector search or feature matching over hundreds or thousands of dimensions, where k-d trees are usually the wrong data structure and other approaches are more appropriate. The API does not impose a hard dimensional limit, but Kiddo is primarily intended for low-dimensional workloads.

Installation

Add kiddo to Cargo.toml

[dependencies]
kiddo = "6.0.0"

Usage

use std::num::NonZero;

use kiddo::leaf_strategies::VecOfArrays;
use kiddo::SquaredEuclidean;
use kiddo::QueryResultItem;
use kiddo::{Eytzinger, ImmutableKdTree};

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

let kdtree = ImmutableKdTree::new_from_slice(&entries).unwrap();

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

// find the nearest item to [0f64, 0f64].
let nearest = kdtree
    .query(&[0f64, 0f64])
    .nearest_one::<SquaredEuclidean<f64>>()
    .execute();
assert_eq!(nearest.distance, 0f64);
assert_eq!(nearest.item, 0);

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

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

Batch Queries

When many query points are known up front, run them as one batch. A batch query is configured exactly like a single-point query and returns one result per query point, indexed by position in the input slice:

use kiddo::{ImmutableKdTree, SquaredEuclidean};

let entries = vec![[0f64, 0f64], [1f64, 1f64], [2f64, 2f64]];
let kdtree = ImmutableKdTree::new_from_slice(&entries).unwrap();

let queries = [[0.1f64, 0.1], [1.9, 1.9]];

let results = kdtree
    .query_batch(&queries)
    .nearest_one::<SquaredEuclidean<f64>>()
    .execute();

assert_eq!(results[0].item, 0);
assert_eq!(results[1].item, 2);

Batches spread across threads by default, via the multi-threaded feature. How that work is scheduled — ordering, threading, and grouping — is deliberately unspecified so it can keep improving without breaking callers; see the batch module for exactly what is and is not guaranteed.

Optional Features

Kiddo exposes a number of optional crate features:

• fixed enables support for fixed-point coordinate types from the fixed crate.

• f16 enables support for half-precision floating-point coordinates via the half crate.

• serde enables serialization and deserialization via Serde.

• rkyv_08 enables zero-copy serialization and deserialization via rkyv 0.8.x. This is particularly useful for prebuilt immutable trees that you want to load very quickly, especially in conjunction with memory-mapped files.

• simd (NIGHTLY) enables handwritten SIMD and prefetch intrinsics for additional performance where available. This requires a nightly Rust toolchain.

• multi-threaded (default) lets tree construction and batch queries use multiple threads, via the current rayon thread pool, and is what pulls rayon in as a dependency.

  Disabling it drops that dependency and configures the threaded APIs out rather than quietly downgrading them: ParallelConstruction, KdTreeBuilder::with_parallel_construction, the *_parallel constructors, Executor::parallel, Executor::parallel_in_pool and the batch scheduling hints no longer exist, so code that used them fails to compile instead of silently running on one thread. Whatever still compiles keeps working and produces identical trees and results. Use it for WASM, embedded, or single-core targets, or wherever an extra dependency is not worth it.

• huge_pages enables Linux-specific huge-page advice helpers for owned and archived tree storage.

• leaf_nta_prefetch enables additional non-temporal leaf prefetch hints in some query paths. This is an advanced tuning feature and is only useful in specific workloads.

Kiddo also contains a number of additional feature flags used for internal experimentation, benchmarking, simulation, and specialized tuning. Most users will not need them.

MSRV

Kiddo v6’s current minimum supported Rust version (MSRV) is 1.89.0 (1.85.0 for v5.x.x).

Kiddo will aim to support at least N-4 stable Rust releases, which is roughly six months of stable compiler history, when used with the default crate features.

Kiddo will also endeavour to increase MSRV only when doing so would provide a material improvement for users, rather than simply for the sake of using a newer compiler.

Optional features may require a newer toolchain than the default-feature MSRV if their dependency stack requires it. The simd feature is nightly-only and is outside the stable MSRV policy.

NOTE: Support for rkyv 0.7 was removed in Kiddo v6.

Re-exports

pub use kd_tree::DEFAULT_PARALLEL_CONSTRUCTION_THRESHOLD;

pub use kd_tree::KdTreeBuilder;

pub use kd_tree::QueryScratch;

Modules

batch

Batch query execution: running many query points against one tree per call.

dist

Distance metrics

huge_pages

Best-effort Transparent Huge Page helpers for owned and archived tree storage.

kd_tree

The core KdTree struct lives here, around which the whole crate is based.

leaf_strategies

Leaf storage strategies for the kd-tree

stem_strategies

Stem ordering strategies for the kd-tree

traits

Traits used by KdTree.

Structs

BestQueryResultItem

Represents an entry in the results of a best-within query.

QueryResultItem

Represents an entry in the results of a nearest or radius query.

Type Aliases

ImmutableKdTree

Convenience type alias for recommended default params for an immutable KdTree

MutableKdTree

Convenience type alias for recommended default params for a mutable KdTree