java - 使用 MapReduce 构建 kd 树？

Question

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

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

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

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

Answer 1

我认为 kd-tree 不适合您的数据。这是维基百科所说的：

kd 树不适合在高维空间中有效地找到最近邻。作为一般规则，如果维度为 k，则数据中的点数 N 应为 N >> 2^k。否则，当kd树与高维数据一起使用时，树中的大部分点都会被评估，效率并不比穷举搜索好，应该改用近似最近邻方法。

您的特征向量的维数为 1000，这意味着您应该有大约 10^300 张图像，这不太可能。

我建议您查看Locality-sensitive hashing，这是提到的用于高维数据的近似最近邻搜索之一。

由于 Wikipedia 并不总是学习复杂事物的最佳场所，因此我建议您查看ETH Zurich数据挖掘课程的相应讲座幻灯片。碰巧我在本学期选修了这门课。