0

我正在使用静态KD-Tree在 3D 空间中进行最近邻搜索。但是，客户端的规范现在已经更改，因此我需要加权最近邻搜索。例如，在一维空间中，我有一个权重为 5 的点 A 为 0，一个点 B 的权重为 2 在 4；如果查询点是从 -5 到 5，则搜索应该返回 A，如果查询点是从 5 到 6，则应该返回 B。换句话说，在其半径内，较高权重的点优先。

谷歌没有任何帮助——我得到的只是关于K-nearest neighbors algorithm的信息。

我可以简单地删除完全被较高权重点包含的点，但通常情况并非如此（通常较低权重点仅部分包含，如上面的一维示例中）。我可以使用范围树查询以查询点为中心的 NxNxN 立方体中的所有点并确定权重最大的点，但是这种简单的实现是浪费的 - 我需要将 N 设置为整个树中权重最大的点，即使在立方体中可能没有具有该权重的点，例如，假设树中权重最大的点是 25，那么我需要将 N 设置为 25，即使任何权重最高的点给定立方体的重量可能要低得多；在 1D 情况下，如果我有一个位于 100 且权重为 25 的点，那么即使我在该点的半径之外，我的简单算法也需要将 N 设置为 25。

总而言之，我正在寻找一种可以查询 KD 树（或一些替代/变体）的方法，以便我可以快速确定其半径覆盖查询点的最高权重点。

FWIW，我正在用 Java 编写代码。

如果我可以动态地改变一个点的权重而不会产生太高的成本，那也很好——目前这不是一个要求，但我预计这可能是未来的一个要求。

编辑：我在优先级范围树上找到了一篇论文，但这并不能完全解决相同的问题，因为它没有考虑具有更大半径的更高优先级点。

4

2 回答 2

4

为重量使用额外的尺寸。(x,y,z)具有权重的点w放置在 处(N-w,x,y,z)，其中N是最大权重。

4D 中的距离由…定义

d((a, b, c, d), (e, f, g, h)) = |a - e| + d((b, c, d), (f, g, h))

…第二个 d 是您的 3D 距离。

要查找所有可能的结果(x,y,z)，请查询半径为 的N球(0,x,y,z)。

于 2013-05-10T20:27:18.337 回答
0

我想我找到了一个解决方案：嵌套区间树，它是 3D 区间树的实现。我没有存储具有关联半径的点然后需要查询，而是直接存储和查询半径。这有一个额外的好处，即每个维度不需要具有相同的权重（因此半径是一个矩形框而不是一个立方体），这目前不是项目要求，但将来可能会成为一个（仅限客户最近增加了“加权分数”要求，谁知道他还会想出什么）。

于 2013-05-11T04:56:18.333 回答