[Numpy-discussion] Large symmetrical matrix

Hoyt Koepke hoytak@gmail....
Wed Jun 11 15:26:34 CDT 2008

> The factor of two memory hit is not really the problem, it is the scaling
> O(N^2) which is the limitation

Have you thought about using kd-trees or similar structures?  If you
are only concerned about the minimum distances between two points,
that is the ideal data structure.  It would reduce your running time /
memory usage for generating / using the data from O(n^2) to O(n log
n), with a O(log n) lookup time for the closest distance to each

Without doing something like that, looking at the distance between
each pair of points is \Omega(n^2).


Hoyt Koepke
UBC Department of Computer Science

More information about the Numpy-discussion mailing list