I have a m*n matrix (m>1000000, n>50000). What I want to do now is to pairwise every two rows of the matrix and do some further computation (e.g computing common elements of two rows, or reveal subsumption relationship between two rows). I wrote applications with naive code (using two for loops) which can work for small matrix, but not for big matrix like the one listed at the beginning. I need some suggestions on how to solve this computation problem in this case.

  • 4
    $\begingroup$ The output of computing something pairwise between $m$ vectors is $m^2/2$ quantities, which is ludicrously large in your case. It is better to look at what you're trying to do using those $m^2$ quantities and avoid computing all of them in the first place, than to try to compute them faster. I think this could be an instance of the X-Y problem. $\endgroup$ – Kirill Oct 27 '17 at 1:02
  • $\begingroup$ What is a "subsumption relationship" between two vectors? $\endgroup$ – Kirill Oct 27 '17 at 1:04
  • $\begingroup$ @Kirill For "subsumption relationship", I want to see if the set of elements of one row (list) is a superset of another one. $\endgroup$ – zfb Oct 29 '17 at 2:30
  • $\begingroup$ At the very least, you can reduce the number of comparisons by a factor of two if you treat each row as a bitstring of zeros and ones, depending on whether a column is nonzero in a row. You can then interpret these bitstrings as numbers. A row can then only be subsumed by another if the number that corresponds to the other is larger or equal (because it needs to have at least the same bits set). This is not a sufficient condition, but if you sort rows in ascending order based on their number, then a row $i$ can only be subsumed by row $j$ if $j\ge i$. So you only have to do $n^2/2$ comparisons $\endgroup$ – Wolfgang Bangerth Oct 29 '17 at 17:57
  • $\begingroup$ There are likely more clever ways to arrange all rows in a tree based on these numbers, and to make decisions based on this tree. $\endgroup$ – Wolfgang Bangerth Oct 29 '17 at 17:58

You can't -- if you want to consider all pairs of rows, then your algorithm is inherently ${\cal O}(m^2)$ in the number $m$ of rows. There is fundamentally nothing you can do about this unless you find a way to avoid looking at all pairs of rows.

However, the problem should be easy to parallelize!

  • 1
    $\begingroup$ I tried to do this in parallel, but it ran out of memory because there are really too many pairs to check. I should then find a way to decrease the number of pairs that I need to go through. Thanks. $\endgroup$ – zfb Oct 29 '17 at 2:27

Your Answer

