8

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

  1. 一种，数据存储在节点和叶子中，例如这里
  2. 一种，数据仅存储在叶子中，例如这里

它们似乎基本相同，具有相同的渐近特性。

我的问题是：有什么理由选择一个而不是另一个？

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

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

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

4

1 回答 1

6

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

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

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

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

If you want a more dynamic structure, I recommend looking at R*-trees. They are actually desinged to balance on inserts and deletions, and organize the data in a disk-oriented block structure. But even for R-trees, there have been reports that keeping an insertion buffer etc. to postpone structural changes improves performance. And bulk loading in many situations helps a lot, too!

于 2013-01-13T10:41:37.393 回答