5
$\begingroup$

I have a matrix of data ~(70,000x70,000). I am searching connection between these data points. I use euclidean distance for that purpose. If it is less than my threshold (that means they have connection) I put 1 into adjacency matrix. If it is greater than my threshold I put 0. I need to change elements as following.

import data file
data size n
For[i = 1, i <= n, i++,
  For[j = 1, j < i, j++,
   eucdis[[i, j]] = 
    N[EuclideanDistance[data[[i, All]], data[[j, All]]]];
   If [eucdis[[i, j]] <= epsilon ,
    rp[[i, j]] = 1; rp[[j, i]] = 1;
    ];
   ]; rp[[i, i]] = 1;
  ];

Memory usage gets 100% and PC gets frozen.

Is it possible to limit memory usage, so it can take longer but could be done, or any other method to finish this calculation?

Improve this question
$\endgroup$
9
  • $\begingroup$ It is just an example, All parameters will be changed. $\endgroup$
    – forumcash
    Jul 12, 2015 at 1:39
  • $\begingroup$ How many GB of ram do you have? $\endgroup$
    – Nasser
    Jul 12, 2015 at 2:04
  • 6
    $\begingroup$ That matrix would take up 78GB of RAM if it were a PackedArray. If it wasn't, it'd need hundreds of GB of RAM. 32GB RAM isn't enough. I think Leonid Shifrin had a big-array package, but I've never used it. $\endgroup$
    – DumpsterDoofus
    Jul 12, 2015 at 2:42
  • 2
    $\begingroup$ From the code I will say that it looks that you do NOT have a 70k x 70k matrix. You have rather a 70k set of points, each of probably a much lower dimension. Attempting to form a matrix of the pariwise distances, or any dense matrix derived therefrom, is just not a good idea. $\endgroup$
    – Daniel Lichtblau
    Jul 12, 2015 at 20:34
  • 1
    $\begingroup$ You can use Sow and Reap to keep track of all "close" connections, assuming each entry on averate has but few. Then create a SparseArray from the set of keepers. $\endgroup$
    – Daniel Lichtblau
    Jul 12, 2015 at 20:35

3 Answers 3

Reset to default
2
$\begingroup$

As others have already stated, keeping the whole 70000x70000 matrix will require too much memory. Storing just the relevant information in a SparseArray will help.

Let me create some sample data and define a distance function:

nd = 70000;  
data = RandomReal[{0, 1}, {nd, 3}];
eps = 0.01;  
ed[i_, j_] := EuclideanDistance[data[[i]], data[[j]]]

Now we need an empty sparse array to start with:

rp = SparseArray[{}, {nd, nd}];

We loop through the data to find the distances, keeping only the relevant information:

Do[  
   dist = ed[i,j];  
   If[dist < eps,  
       rp[[i, j]] = 1; rp[[j, i]] = 1  
   ],  
   {i, 1, nd}, {j, 1, i}  
]; // Timing

This will take a while, but will not use a lot of memory at all. Note that the obvious one-liner

rp = SparseArray[{{i_, j_} /; ed[i,j] < eps -> 1}, {nd, nd}];

will use much more memory, I couldn't get it to work on my 32 GB computer, which was frozen after the kernel consumed about 24 GB...

I recommend testing tis approach with a smaller subset of your data, I could manage 7000 data points even with the one-liner.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Better yet: you can have your Do[] loop output the rules you can then pass along to SparseArray[]. $\endgroup$
    – J. M.'s eventual burnout ♦
    Jul 13, 2015 at 9:32
  • $\begingroup$ I am running since yesterday. It is significantly slower, but it uses reasonable amount of ram. Thank you. I did not get how it runs one-liner because there are two variable in Do loop. Can you explain a little bit? $\endgroup$
    – forumcash
    Jul 14, 2015 at 13:47
  • $\begingroup$ @forumcash: The variables of the Do loop are the patterns in the one-liner. I assume that internally this will be expanded to some kind of loop, with i and j going from 1 to nd. $\endgroup$
    – AxelF
    Jul 14, 2015 at 14:03
  • $\begingroup$ @AxelF, there are i and j. Doesn't it make 2 dimensional process? $\endgroup$
    – forumcash
    Jul 15, 2015 at 14:21
9
$\begingroup$

Note: the answer below referred to a previous version of the question

You may have more success with SparseArray. For instance:

SparseArray[
   {{i_, i_} -> 1, {i_, j_} /; Abs[i - j] == 1 -> 2},
   {20000, 20000},
   0
]; // RepeatedTiming

(* Out: {0.21, Null} *)

You would use patterns to assign values to positions within the matrix determined by conditions on their indices. You can also assign default values for the rest of the positions that match no pattern explicitly (e.g. the $0$ value in the example above).

This format is vastly more memory efficient than a dense array since the rules to generate the values are stored, rather than the values themselves.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for suggestion. It has huge benefit if I was trying to change some of the data. I tried to use it. SparseArray[{{i_, j_} :> N[EuclideanDistance[data[[i]], data[[j]]]]}, {n, n}] Same problem continues. $\endgroup$
    – forumcash
    Jul 12, 2015 at 16:57
  • $\begingroup$ @forumcash So you want to build a matrix that contains the pairwise distances between data points stored in another array, called data? If that is the case, then SparseArray won't help you because your desired array is not sparse. You just don't have enough memory to construct such an array (see the comments on your original question). Can you edit your question to include a better example of what you actually want to accomplish, and why you need such an array? You might be able to calculate those distances when needed, instead of pre-calculating and storing them ahead of time. $\endgroup$
    – MarcoB
    Jul 12, 2015 at 17:43
  • $\begingroup$ Thank you for feedback. I rewrite the question. Please let me know if there is anything confusing. $\endgroup$
    – forumcash
    Jul 12, 2015 at 18:22
0
$\begingroup$

Instead of a matrix, could you store only a list of the indices for which the distance is below your threshold? If there are relatively few of these, that would be efficient and easy to search.

Improve this answer
$\endgroup$
1
  • $\begingroup$ How can I do that? Can you write an example code? $\endgroup$
    – forumcash
    Jul 13, 2015 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.