Kiddo

一个高性能、灵活、易用的 k-d 树 库。可能是世界上速度最快的 k-d 树库？看看你自己。

• 包
• 文档
• 用法
• 示例
• 基准测试
• 变更日志
• 许可证

Kiddo 适用于超快的空间/地理空间查找以及低维度近邻/KNN 查询，您可能需要询问以下问题

• 找到查询点最近的 n 个项目，按距离排序；
• 找到所有位于查询点 指定半径范围内的项目；
• 找到查询点 "最佳"的 n 个项目，其中 "最佳" 有一定的定义。

Kiddo 提供以下功能

• 其标准浮点 k-d 树，作为 kiddo::KdTree 暴露；
• 通过 Fixed 库提供 整数/定点支持；
• 通过 half 库提供 f16 支持；
• 通过 Rkyv (Serde 仍然可用) 提供 即时零拷贝反序列化和序列化；
• 一个具有空间和性能优势的 ImmutableKdTree，用于在创建后不需要修改树的情况

用法

将 kiddo 添加到 Cargo.toml

[dependencies]
kiddo = "4.2.0"

向 kdtree 添加点并使用距离函数查询最近的 n 个点

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)]
);

查看 示例文档 以获取更多详细示例。

可选功能

kiddocrate 提供以下功能。标记为 (NIGHTLY) 的功能在稳定版 Rust 中不可用，因为它们需要一些不稳定的功能。要使用它们，您需要使用 nightly 构建。

• serialize - 通过 Serde 进行序列化和反序列化
• serialize_rkyv - 通过 Rkyv 进行零拷贝序列化和反序列化
• global_allocate (NIGHTLY) - 启用时，Kiddo 将使用 ImmutableKdTree 中的不稳定 allocator_api 功能来为叶节点分配空间，从而获得轻微的性能提升。
• simd (NIGHTLY) - 在 ImmutableKdTree 中启用一些手写的 SIMD 内置代码，这可能提高性能（目前仅在 f64 使用 nearest_one 方法时）
• f16 - 允许在浮点树中使用 half crate 中的 f16

v3.x

版本 3.x 改变了距离度量语法，从函数指针切换到基于 trait 的方法，这允许一些语法和性能改进。但这是一种破坏性变化：在 v3 之前，您的查询可能看起来像这样

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

从 v3 开始，您需要切换到以下语法

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

V3 还引入了 ImmutableKdTree 变体。它适用于所有需要添加到树中的点都已知且无需在树初始填充后进行修改的情况。 ImmutableKdTree 在构建时平衡和优化树，确保更有效的内存使用（并相应地减小序列化树在磁盘上的大小）。由于 ImmutableKdTree 的内部节点在内存中占用的空间较小，因此它们可以更多地放入 CPU 缓存中，从而可能在某些情况下提高性能。

v2.x

版本 2.x 是一次彻底的重写，提供了

• 新的内部架构，性能大幅提升；
• 通过 Fixed 库添加了对整数/固定点支持；
• 通过 Rkyv (Serde 仍然可用) 提供 即时零拷贝反序列化和序列化；
• 有关 v2 中所做的所有更改的详细信息，请参阅 更改日志。

基准测试

所有以下基准测试的结果都可以在 https://sdd.github.io/kd-tree-comparison-webapp/ 上的交互式 webapp 中查看。

比较基准测试套件位于另一个项目中，https://github.com/sdd/kd-tree-comparison。

使用 Criterion 执行了一系列基准测试。我们将 Kiddo v3 与以下版本进行比较

• Kiddo v2.x
• Kiddo v1.x / v0.2.x
• FNNTW v0.2.3
• nabo-rs v0.2.1
• pykdtree v1.3.4
• sklearn.neighbours.KDTree v1.2.2
• scipy.spatial.KDTree v1.10.1

以下活动被基准测试（如果实施）

• 从点列表和索引构建k-d树
• 查询给定查询点最近的点、十个点或一百个点
• 查询给定点周围一定半径内的所有点（包括未排序的结果和按距离排序的结果）
• 查询指定半径内的最近n个项（包括排序和未排序的结果）

每个操作都与包含100、1,000、10,000、100,000、1,000,000和在某些情况下10,000,000个节点的树进行了基准测试。

基准测试针对2d、3d和4d树进行，以及类型为f32和类型为f64的点，以及Kiddo v2的16位定点使用案例。

树使用随机源数据填充，其中所有点都在单位球面上。此用例代表了在地理空间和天文学背景下常见的kd树使用。

许可证

根据您选择之一进行授权

• Apache License，版本2.0（LICENSE-APACHE或https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT License（LICENSE-MIT或http://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义的任何有意提交以包含在您的工作中的贡献，都应如上双授权，不附加任何额外的条款或条件。