If your positions are static (I'm not clear on that from your message), then you might want to check the technique of "slice searching". It only requires one sort of the data for each dimension initially, then uses a simple, but clever look up to find neighbors within some epsilon of a chosen point. Speeds appear to be about equal to k-d trees. Programming is vastly simpler than k-d trees, however.
See,
[1] "A Simple Algorithm for Nearest Neighbor Search in High Dimensions," Sameer A. Nene and Shree K. Nayar, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 19 (9), 989 (1997).
-- Lou Pecora, my views are my own.
--- On Thu, 7/10/08, Dan Lussier
From: Dan Lussier
Subject: [Numpy-discussion] huge array calculation speed To: numpy-discussion@scipy.org Date: Thursday, July 10, 2008, 12:38 PM Hello, I am relatively new to numpy and am having trouble with the speed of a specific array based calculation that I'm trying to do.
What I'm trying to do is to calculate the total total potential energy and coordination number of each atom within a relatively large simulation. Each atom is at a position (x,y,z) given by a row in a large array (approximately 1e6 by 3) and presently I have no information about its nearest neighbours so each its position must be checked against all others before cutting the list down prior to calculating the energy.