mic*_*ard 5 algorithm performance computational-geometry
我在尺寸为m的超球面上(在10 ^ 4到10 ^ 6之间)有n个(大约10 ^ 5)个点.
我要做一堆形式的查询"给定一个点p,找到最接近的n个点到p".我将讨论其中的n个问题.
(不确定超球面事实是否有帮助.)
解决此问题的简单朴素算法是,对于每个查询,将p与所有其他n个点进行比较.这样做n次最终会得到O(n ^ 2 m)的运行时间,这对我来说太大了,无法计算.
我可以使用更高效的算法吗？如果我能用O(nm)得到一些很好的对数因子.
可能不会。拥有多个维度使得高效索引变得极其困难。这就是为什么人们寻找机会将维度数量减少到可管理的程度。
有关更多信息，请参阅https://en.wikipedia.org/wiki/Curse_of_Dimensionality和https://en.wikipedia.org/wiki/Dimensionality_reduction。
| 归档时间： |
|
| 查看次数： |
108 次 |
| 最近记录： |