Kd树:仅存储在叶子中的数据与存储在叶子和节点中的数据

Question

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

1. 数据存储在节点和叶子中的那个,例如这里
2. 数据仅存储在叶子中的数据,例如此处

它们似乎基本相同,具有相同的渐近性质.

我的问题是:为什么选择一个而不是另一个？

到目前为止,我认为有两个原因:

1. 在节点中存储数据的树也较浅1级.
2. 仅在叶子中存储数据的树具有更容易实现的delete data功能

在决定选择哪一个之前,我还应该考虑其他一些原因吗？

Answer 1

您可以将节点标记为已删除，并将任何结构更改推迟到下一次树重建。kd-trees 会随着时间的推移而退化，所以你需要经常重建树。kd-trees 非常适合不会改变的低维数据集，或者您可以轻松重建（近似）最佳树的情况。

至于实现树，我建议使用简约的结构。我通常不使用节点。我使用一组数据对象引用。轴由当前搜索深度定义，无需存储在任何地方。左右邻居由数组的二叉搜索树给出。（否则，只需添加一个数组byte，即数据集大小的一半，用于存储您使用的轴）。加载树是由专门的 QuickSort 完成的。从理论上讲，这是O(n^2)最坏的情况，但是使用诸如中位数 5 之类的良好启发式方法，您可以获得O(n log n)非常可靠且恒定开销最小的结果。

虽然它不适用于 C/C++，但在许多其他语言中，您将为管理大量对象付出相当大的代价。Atype*[]是您会发现的最便宜的数据结构，特别是它不需要大量的管理工作。要将元素标记为已删除，您可以使用null它，并在遇到null. 对于插入，我首先将它们收集在缓冲区中。当修改计数器达到阈值时，重建。

这就是它的全部意义所在：如果您的树重建起来真的很便宜（就像使用几乎预先排序的数组一样便宜！）那么频繁重建树并没有什么坏处。对简短的“插入列表”进行线性扫描对 CPU 缓存非常友好。跳过nulls 也很便宜。

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