c++ - Kd 树 : data stored only in leaves vs stored in leaves and nodes

标签 c++ computer-science kdtree

我正在尝试实现 Kd 树以在 C++ 中执行最近邻和近似最近邻搜索。到目前为止,我遇到了最基本的 Kd 树的 2 个版本。

  1. 一种,数据存储在节点和叶子中,例如 here
  2. 一种,数据只存储在叶子中,例如here

它们看起来基本相同,具有相同的渐近特性。

我的问题是:选择其中一个而不是另一个有什么原因吗?

到目前为止我想出了两个原因:

  1. 在节点中存储数据的树也较浅 1 级。
  2. 只在叶子中存储数据的树更容易 实现删除数据功能

在决定制作哪一个之前,我还应该考虑其他一些原因吗?

最佳答案

您可以将节点标记为已删除,并将任何结构更改推迟到下一次树重建。 k-d-trees 会随着时间的推移而退化,因此您需要经常重建树。 k-d-trees 非常适合不会改变的低维数据集,或者您可以轻松负担得起重建(近似)最优树的地方。

至于实现树,我建议使用简约结构。我通常使用节点。我使用一组数据对象引用。轴由当前搜索深度定义,无需将其存储在任何地方。左右邻居由数组的二叉搜索树给出。 (否则,只需添加一个 byte 数组,即数据集大小的一半,用于存储您使用的轴)。加载树是由专门的 QuickSort 完成的。理论上它是 O(n^2) 最坏的情况,但是如果有一个很好的启发式算法,例如中位数为 5,您可以非常可靠地得到 O(n log n)并以最小的持续开销。

虽然它对 C/C++ 来说不那么重要,但在许多其他语言中,您将为管理大量对象付出相当大的代价。 type*[] 是您能找到的最便宜的数据结构,尤其是它不需要大量的管理工作。要将元素标记为已删除,您可以将其null,并在遇到null 时搜索两侧。对于插入,我首先将它们收集在缓冲区中。当修改计数器达到阈值时,重建。

这就是它的全部意义所在:如果您的树的重建成本真的很低(就像求助于一个几乎预先排序的数组一样便宜!),那么频繁重建树并没有什么坏处。 对一个简短的“插入列表”进行线性扫描对 CPU 缓存非常友好。跳过 null 也非常便宜。

如果您想要更动态的结构,我建议您查看 R* 树。它们实际上旨在平衡插入和删除,并以面向磁盘的 block 结构组织数据。但即使对于 R 树,也有报告称保留插入缓冲区等以推迟结构更改可以提高性能。在许多情况下,批量加载也有很大帮助!

关于c++ - Kd 树 : data stored only in leaves vs stored in leaves and nodes,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14292585/

相关文章:

java - Java 和 C++ 在对象创建方面的主要区别是什么?

machine-learning - 智能代码完成?有没有AI可以通过学习写代码?

固定大小的 char 数组到相对 64 位整数

c++ - 如何在 matlab 中使用 kd-tree 文件交换和 mex?

c# - 用于检索基础类型的空类

c++ - boost 线程同步

algorithm - KD 树 : meaning of `leafsize` parameter

c++ - 使用 throw() 说明符模拟方法

algorithm - 递归树和二叉树成本计算