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?

$\endgroup$
  • $\begingroup$ It is just an example, All parameters will be changed. $\endgroup$ – forumcash Jul 12 '15 at 1:39
  • $\begingroup$ How many GB of ram do you have? $\endgroup$ – Nasser Jul 12 '15 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 '15 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 '15 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 '15 at 20:35
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.

$\endgroup$
  • $\begingroup$ Better yet: you can have your Do[] loop output the rules you can then pass along to SparseArray[]. $\endgroup$ – J. M. will be back soon Jul 13 '15 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 '15 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 '15 at 14:03
  • $\begingroup$ @AxelF, there are i and j. Doesn't it make 2 dimensional process? $\endgroup$ – forumcash Jul 15 '15 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.

$\endgroup$
  • $\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 '15 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 '15 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 '15 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.

$\endgroup$
  • $\begingroup$ How can I do that? Can you write an example code? $\endgroup$ – forumcash Jul 13 '15 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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