在 N 维 space 中找到距离给定点最近的 N 个点
Find nearest N points to a give point in N-dimentional space
我得到了一个 N 维 space 有数百万个点。我正在寻找构建模型的最有效方法，该模型允许在 运行 时间找到最接近给定点的 K (K<100) 个点。
List FindClosestMatch(Point target, Model模型)
我开始研究 R* 树，但想知道这是否是正确的方法...
您可以将 space 划分为 n 个立方体，这样立方体中的预期点数是 rk，以便确定 r > 1 的某个值。然后对于给定的查询 p:
1. Consider the 3^n n-cubes at most 1 away from the cube p is in.
2. Calculate the shortest distance d between p and one of these cubes.
3. Find the distance between p and each point in these cubes.
4. If the total number of points within d is >= k, return the k closest.
5. If not, expand your radius by one cube and repeat.
当您选择 r 时，您要权衡使用更大的默认点集来搜索，而不是可能必须将半径扩大 1 倍或更多倍。
R-Tree 变体是一个不错的选择，但 M-tree 更适合您的应用程序，因为您只需要计算一个距离即可确定边界球与目标点的接近程度：
您还想看看 Cover Trees, which are especially for kNN-searches. I also found that the PH-Tree（我自己的）在 15 或 25 个维度上的性能几乎与 Cover Tree 一样好，同时在内存方面 space 效率更高，尤其是对于大型数据集，并允许快速 inserts/updates.
许多算法的比较 Java 实现在 ELKI Framework 中可用。
我得到了一个 N 维 space 有数百万个点。我正在寻找构建模型的最有效方法，该模型允许在 运行 时间找到最接近给定点的 K (K<100) 个点。
List FindClosestMatch(Point target, Model模型)
我开始研究 R* 树，但想知道这是否是正确的方法...
您可以将 space 划分为 n 个立方体，这样立方体中的预期点数是 rk，以便确定 r > 1 的某个值。然后对于给定的查询 p:
1. Consider the 3^n n-cubes at most 1 away from the cube p is in.
2. Calculate the shortest distance d between p and one of these cubes.
3. Find the distance between p and each point in these cubes.
4. If the total number of points within d is >= k, return the k closest.
5. If not, expand your radius by one cube and repeat.
当您选择 r 时，您要权衡使用更大的默认点集来搜索，而不是可能必须将半径扩大 1 倍或更多倍。
R-Tree 变体是一个不错的选择，但 M-tree 更适合您的应用程序，因为您只需要计算一个距离即可确定边界球与目标点的接近程度：
您还想看看 Cover Trees, which are especially for kNN-searches. I also found that the PH-Tree（我自己的）在 15 或 25 个维度上的性能几乎与 Cover Tree 一样好，同时在内存方面 space 效率更高，尤其是对于大型数据集，并允许快速 inserts/updates.
许多算法的比较 Java 实现在 ELKI Framework 中可用。