使用树加速具有周期性边界条件的 3D 数组的最近邻搜索

Question

使用根据 this 问题的答案改编的代码，我可以在考虑周期性边界条件的情况下对 3D 数组进行强力 NN 搜索。然后代码 returns 最近邻居的索引，它对所有邻居都这样做。

import numpy as np
from multiprocessing.dummy import Pool as ThreadPool

N = 10000  # Num of objects
# create random point positions
coords = np.random.random((3, N)).transpose()

def NN(point):
    dist = np.abs(np.subtract(coords, point))  # Distance between point and all neighbors xyz values
    dist = np.where(dist > 0.5, dist - 1, dist)  # checking if distance is closer if it wraps around
    return (np.square(dist)).sum(axis=-1).argsort()[1]  # Calc distance and find index of nearest neighbour

# multi threading for speed increase 
pool = ThreadPool(12)
match = pool.map(NN, coords)
pool.close()
pool.join()

对于 N ~ 50000，它如预期的那样变得非常慢。

我想知道如何使用 sklearn.BallTree or scipy.spacial.cKDTree and would like to do this without duplicating the space 8 more times as suggested here.

等树来实现它

Answer 1

sklearn.BallTree 和 scipy.spatial.cKDTree 都不能轻易修改以处理周期性边界条件。周期性边界需要一组与这些实现中使用的假设完全不同的假设。

您应该考虑使用替代实现，例如 periodic_kdtree，但请注意，这是一个（有些陈旧的）Python 实现并且不会像 [=17] 一样快=]++ 你提到的实现。

使用树加速具有周期性边界条件的 3D 数组的最近邻搜索

Using trees to speed up nearest neighbour search on 3D array with periodic boundary conditions

python

numpy

nearest-neighbor

scipy

scikit-learn