Memory Error when calculating Euclidean distance between points

Question

I want to find the eps of DBSCAN. I have a set of points and need to calculate the distance from each point to each other point. Where an array of shape is (2267436, 2), then find the near and minpoint. Here are my data:

xy= [[  177963.16728699  2506663.75713195]
 [  176147.50406716  2502422.34894945]
 [  178480.33178874  2507299.83467826]
 ..., 
 [  231205.88139267  2684014.30324774]
 [  231207.81085397  2684014.52219471]
 [  231214.870296    2684054.8263628 ]]

I am trying these methods like:

dist = scipy.spatial.distance.cdist(xy, xy,'euclidean')

or

np.sqrt((np.square(npxy[:,np.newaxis]-npxy).sum(axis=2)))

or

dist=scipy.spatial.distance.pdist(npxy)
d_matrix = scipy.spatial.distance.squareform(dist)

I am getting MemoryError for all. Is there any solution to figure out it?

There are 2267436 choose 2 = 2,570,631,873,330 (over 2.5 trillion) distinct pairs of points, and a naive distance matrix will have over 5 trillion entries. Perhaps you should rethink your algorithm. — John Coleman
– John Coleman, Commented Dec 31, 2017 at 13:38
@FenilPatel please read the question again and reconsider whether "knear" was really a typo or if it was referring to knn. If after an edit you still don't understand what a person means, don't edit in the first place. — Andras Deak -- Слава Україні
– Andras Deak -- Слава Україні, Commented Dec 31, 2017 at 15:54

Has QUIT--Anony-Mousse · Accepted Answer · 2017-12-31 19:43:46Z

1

With some very easy math you can figure out that you cannot store all O(n²) distance in memory.

If you compute only the distances of one point at a time, you will be fine.

Also, try to use an index to reduce the runtime from O(n²) to a manageable scale.

Or you use a more modern algorithm like OPTICS.

answered Dec 31, 2017 at 19:43

Has QUIT--Anony-Mousse

77.8k14 gold badges146 silver badges198 bronze badges

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

1 Comment

陳筱潔 Over a year ago

yes! If i compute only one point ,it will be fine! but this is my essay work, i got to figure out it, now i use arcmap tool like point distance and near, it will take lots of time,but won't get memoryerror, maybe when i get up ,it will be ok! anyway, thanks !

Collectives™ on Stack Overflow

Memory Error when calculating Euclidean distance between points

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related