Fastest way to approximately compare values in large numpy arrays?

Question

I have two arrays, array A with ~1M lines and array B with ~400K lines. Each contains, among other things, coordinates of a point. For each point in array A, I need to find how many points in array B are within a certain distance of it. How do I avoid naively comparing everything to everything? Based on its speed at the start, running naively would take 10+ days on my machine. That required nested loops, but the arrays are too large to construct a distance matrix (400G entries!)

I thought the way would be to check only a limited set of B coordinates against each A coordinates. However, I haven't determined an easy way of doing that. That is, what's the easiest/quickest way to make a selection that doesn't require checking all the values in B (which is exactly the same task I'm trying to avoid)?

EDIT: I should've mentioned these aren't 2D (or nD) Cartesian, but spherical surface (lat/long), and distance is great-circle distance.

You could sort each record into grid areas and only check the relevant grid and the surrounding ones - It depends if you have a maximum distance? If not, you're going to have to compare them all. — Basic
– Basic, Commented Aug 1, 2012 at 18:40
Yes, there is a maximum distance (but see edit to question). — Tristan Klassen
– Tristan Klassen, Commented Aug 1, 2012 at 19:40
I solved it by splitting into latitude bins and checking each bin against itself and adjacent bins. I'd thought it would be complicated because I'd assumed sorting by longitude first (or only), but sorting only by latitude provided sufficient performance improvement. — Tristan Klassen
– Tristan Klassen, Commented Aug 9, 2012 at 21:50
Glad you found a solution. If you don't mind, please post it as an answer and accept it so a) others can find your answer and b) nobody else tries to answer this question when you've solved the problem. Welcome to SO and hope we see you around again :) — Basic
– Basic, Commented Aug 9, 2012 at 23:15

Sven Marnach · Accepted Answer · 2012-08-01 18:43:48Z

1

I cannot give a full answer right now, but some hints to get you started. It will be much more efficient to organise the points in B in a kd-tree. You can use the class scipy.spatial.KDTree to do this easily, and you can use the query() method on this class to request the points within a given distance.

answered Aug 1, 2012 at 18:43

Sven Marnach

608k123 gold badges968 silver badges865 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

segasai · Accepted Answer · 2013-05-12 17:14:54Z

0

Here is one possible implementation of the cross match between list of points on the sphere using k-d tree. http://code.google.com/p/astrolibpy/source/browse/my_utils/match_lists.py

Another way is to use healpy module and their get_neighbors method.

answered May 12, 2013 at 17:14

segasai

8,5581 gold badge31 silver badges40 bronze badges

Collectives™ on Stack Overflow

Fastest way to approximately compare values in large numpy arrays?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related