MemoryError в Python при использовании cKDTree(). Query_ball_tree

Question

У меня есть большие 2D-массивы с несортированными (X, Y) точками, для которых мне нужно знать, какие точки находятся в непосредственной близости друг от друга (поиск ближайших соседей). Я использовал cKDTree и query_ball_tree с результатами для массивов с 500 000 (X, Y) точками. Тем не менее, когда я пытаюсь использовать один и тот же алгоритм для наборов данных из более чем 1 000 000 точек, query_ball_tree приводит к MemoryError.

Я использую 64-разрядную Windows с 16 ГБ встроенной памяти и попробовал как 32-битную, так и 64-разрядную версии Python и модулей расширения (scipy и numpy).

def Construct_SearchTree(AllXyPoints): 
    KDsearch = cKDTree(AllXyPoints) 
    return KDsearch.query_ball_tree(KDsearch, Maxdist) 

Мои вопросы:

1) Кто-нибудь знает о качестве альтернативы cKDTree/query_ball_tree, который потребляет меньше памяти? В этом случае скорость менее важна для использования памяти.

2) Я надеялся, что переключение с 32-битного на 64-битный python & расширений решит MemoryError. Что может быть причиной того, что этого не произошло?

Благодарим за предоставленную помощь и совет.

Answer 1

я испытал MemoryError с SciPy-х cKDTree во время строительства и scikit-узнать-х KDTree при вызове .query_radius(). Я обнаружил, что Scikit-learn'sBallTree был более эффективным с точки зрения памяти, и использование BallTree решило проблему для меня. Я проверил BallTree с 1 миллионом точек данных на моей 64-битной системе. Он по-прежнему потребляет всю доступную память (12 ГБ) и некоторое пространство подкачки, но я не получаю MemoryError.

Запросы на BallTree не будет столь же быстро, как KDTree, так как ваши данные 2D и BallTree s медленнее, чем KDTree s при d < = 3 (см объяснение here). Однако, учитывая, что cKDtree и scikit-learn's KDTree оба повышают MemorError (в моей системе, во всяком случае), самым простым решением является использование BallTree.

from sklearn.neighbors import BallTree 
import numpy as np 

max_dist = .1 
points = np.random.normal(size=2000000).reshape(1000000, 2) #1 million points 
ball_tree = BallTree(points) 

neighbors = ball_tree.query_radius(points, max_dist) 

В зависимости от вашего Maxdist, возвращаемый результат может потреблять много памяти (до O (N^2)), но scikit учиться-х BallTree.query_radius() возвращает np.array из np.array сек, а не list из list с поэтому он должен сохранить вам некоторую память там (см. this answer для объяснения).