问题标签 [kdtree]

我需要实现一个适合作为k -d 树的 B+ 树。作为对此的简短解释，k -d 树就像一棵二叉树，只是在它的节点处它有一个多值键，即具有多个值的键。它也将是 B+ 树，因为内部节点仅用于存储键的 1 个值，而实际数据存储在叶节点处。这是一个简短的图形解释：

我的叶节点有 2 个元素的空间，当我添加前 2 个时一切正常，直到我添加第三个并且我必须进行拆分。为此，由于我选择键的第一个值作为定义顺序的值，因此我取所有三个元素的中值，结果为 27，因此所有小于 27 的元素都向左移动，大于或等于向右走。

当我添加第 4 个元素时，由于 Tom 和 Linda 的年龄小于 27 岁，他们已经完成了一个叶节点，儿子添加 Dom 使节点再次分裂，但是这次我必须切换键的哪个值定义顺序是 Social安全号码。我再次取中间值，结果为 530，因此所有 SS 编号小于 530 的人都向左移动，依此类推。

结果是最终的k -d 树，其中某些键值作为内部节点的索引，而完整的键位于叶节点。

现在我的问题是，在解释了上下文之后，我该如何为键实现解决方案，因为我确实必须在叶节点存储完整的键，但在内部节点我只使用键的值之一.

您可以注意到与数据库的相似之处，其中我们有多个带值的字段，我们可以同时使用不同的字段对信息进行排序，一个比下一个更重要，依此类推。

我想用包含所有值的属性创建一个class命名Key或任何其他名称，对于上面的示例，它可以是int年龄、intSSNumber 和string名称。但我的问题是，如果我的客户决定他想增加更多的价值，那么我的班级会越来越大。这是一个好的 OO 决定吗？我可以用另一种方式实现它并且仍然是 OO 吗？我知道我的想象力可能很差，但是由于我可以假设客户想要更多的值，我可以制作某种包含我的值的列表，那么这意味着我必须制作一个可以支持任何类型数据的列表，这不听起来不像是面向对象的方法。有任何想法吗？

另外我想补充一点，因为在我的树算法的某个时刻，我需要将键的 1 个属性用作树中的索引，所以我也必须支持这一点。

我真的很感激如何通过遵循 OO 方法来解决这个问题。

Python中是否有任何软件包允许对球体表面的经度/纬度进行类似kdtree的操作？（这需要适当考虑球面距离以及经度环绕）。

我将编写一个 KDTree 的模板化实现，它现在只能用作 BarnesHut 实现的 Quadtree 或 Octree。

这里的关键是设计，我想指定树定义为模板参数的维数，然后简单地声明一些常用方法，它们会自动以正确的方式运行（我认为那时需要一些模板专业化）。

我想专门化模板以获得 2^2（四叉树）或 2^3（八叉树）节点。

有人有一些设计理念吗？我想避免继承，因为它限制我进行动态内存分配而不是静态分配。

这里 N 可以是 2 或 3

另一个问题是四叉树有 4 个节点但 2 维，八叉树有 8 个节点但 3 维，即节点数为2^dimension。我可以通过模板元编程指定这个吗？我想保留数字 4 和 8，以便循环展开器可以更快。

谢谢！

目前我正在处理实现一个用于对象识别的 CBIR 系统（详细的对象分类），现在因为我有一些工作的特征检测器和描述符，我试图找到处理这些特征的最佳方法，以完成基于内容的任务图像检索。

据我所知，这项任务有两个主要趋势，离散方法和连续方法。离散代表方法，如视觉词袋和码本，用于建立反向索引以应用引用文本检索的方法，而连续代表方法，如使用 kd 树和最近邻分类的 Best Bin First 搜索。

所以这两种方法之间的一个主要区别是，一种使用视觉词等特征的额外表示，另一种使用从描述符计算的 nD 特征。

我现在的问题是，这两种 CBIR 方法之间是否有任何比较可以帮助我找到适合我的任务的最佳方法？

我正在查看KD trees Nearest Neighbor Search的 Wikipedia 页面。

当点在 2-D(x,y) 中时，维基百科中给出的伪代码有效。

我想知道，当点是 3-D(x,y,z) 时，我应该做些什么改变。

我用谷歌搜索了很多，甚至在堆栈溢出中通过了类似的问题链接，但我在任何地方都没有找到 3-d 实现，以前的所有问题都以 2-D 点作为输入，而不是我的 3-D 点寻找。

构建 KD 树的 Wiki 中的伪代码是：

构建KD树后如何找到最近的邻居？

谢谢！

我正在尝试为图像特征构建 KD 树（独立）。我已经提取了图像特征，该特征包含假设 1000 个浮点值。

使用map-reduce根据分类（例如，猫、狗、枪）在集群的节点之间分配图像，即。每个节点将包含一堆相似的图像，然后在每个节点上构建图像的 KD 树。我对如何建造树感到困惑。

那么如何使用 map-reduce 构建 KD 树呢？每个节点都将包含树，对吗？分发图像的逻辑是什么？在构建 KD 树时，我应该在什么基础上在树中添加图像特征向量（即左子或右子）？

任何帮助表示赞赏。在此先感谢。

我正在尝试使用 map-reduce 构建分布式 KD 树。分布式 KD 树的描述可以在这里找到Dkd-Tree

我有一个尺寸为 20 的图像的特征向量。我必须根据上面的链接构建分布式 kd 树，还可以查看此图像Kdtree

我已经设置了数百万张图像。 那么我可以使用什么方法来构建树的顶部（图像的第二部分）？ 我对各个节点之间的图像分布感到困惑。

如果树是在第一次 map-reduce 操作中构建的 HDFS，那么我如何在下一次 map-reduce 操作中访问它？

我需要索引一个 kd 树，并且以后能够匹配它的一部分。
MySQL有能力吗？有没有其他选择？

我正在使用 BOW 对象检测，并且正在编码阶段。我已经看到了一些kd-Tree在编码阶段使用的实现，但大多数著作都表明K-means集群是要走的路。

两者有什么区别？

我不太了解wikipedia中的 O(log n) 最近邻算法。

1. …</li>
2. …</li>
3. 该算法展开树的递归，在每个节点执行以下步骤：
   1. ...
   2. 该算法检查在分割平面的另一侧是否有任何点比当前最佳点更靠近搜索点。从概念上讲，这是通过将分割超平面与搜索点周围的超球面相交来完成的，该超球面的半径等于当前最近的距离。由于超平面都是轴对齐的，因此这是一个简单的比较，以查看搜索点和当前节点的分割坐标之间的差异是否小于搜索点到当前最佳点的距离（整体坐标）。
      1. 如果超球面穿过平面，则平面的另一侧可能有更近的点，因此算法必须从当前节点向下移动树的另一个分支以寻找更近的点，遵循与整个搜索相同的递归过程.
      2. 如果超球面不与分割平面相交，则算法继续沿树向上走，并消除该节点另一侧的整个分支。

是 3.2 让我感到困惑，我已经看到了这个问题。我正在用 Java 实现算法，但不确定我是否做对了。

上面的代码是否完成了算法的 3.2 方面？特别是我填充“axisAlignedDistance”变量的地方。

您可以在此处找到 KDTree 的完整源代码。

感谢您的任何帮助/指点。