Tag: kdtree

2D KD树和最近邻搜索

我正在按照此处描述的算法实现KD树和最近邻搜索： http ： //ldots.org/kdtree/ 我遇到了几种不同的方法来实现KD树，其中一个点存储在内部节点中，另一个只存储在叶节点中。 因为我有一个非常简单的用例（我需要做的只是构造一次树，它不需要修改），我采用了仅叶子的方法，它实现起来似乎更简单。 我已成功实现了所有内容，树总是成功构建，并且在大多数情况下，最近邻搜索返回正确的值。 但是，我有一些问题，对于某些数据集和搜索点，算法返回不正确的值。 考虑一下要点： [[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]] 构建一个看起来像这样的树（借口我糟糕的图表）： 方形叶节点是包含点的节点，并且圆形节点包含用于在该深度处分割列表的中值。 当在这个数据集上调用我的最近邻居搜索，并寻找[6, 74]的最近邻居时，算法返回[7, 9] 。 虽然这正确地遵循算法，但它实际上并不是[6, 74]的最接近点。 最近的点实际上是[3, 81] ，其距离为7.6， [7, 9]距离为65。 以下是绘制的点，对于可视化，红点是我试图找到最近邻居的点： 如果有帮助，我的搜索方法如下： private LeafNode search(int depth, Point point, KDNode node) { if(node instanceof LeafNode) return […]

使用map-reduce构建分布式KD树

我正在尝试使用map-reduce构建分布式KD树。 分布式KD树的描述可以在这里找到Dkd-Tree 我有一个维度为20的图像的特征向量。我必须根据上面的链接构建分布式kd树，也看看这个图像Kdtree 我有数百万张图片。 那么我可以使用什么方法来构建树的顶部（图像的第二部分）？ 我对各个节点之间的图像分布感到困惑。 如果树在第一次map-reduce操作中构建了HDFS，那么如何在下一次map-reduce操作中访问它？