2
$\begingroup$

I'm working with a ragged matrix of considerable size (ByteCount = 47749114088; Length = 563529128). I had seen a suggestion mentioned in other questions (here on StackExchange), that one might be able to reduce memory by packing individual sublists of a ragged matrix, even when the entire matrix itself cannot be packed.

My initial attempt at packing individual sublists on a subset of the data were encouraging, but when I tried the same strategy with the entire matrix, the ByteCount "ballooned" upward to over 99Gb.

Consider the following code to illustrate:

In[1]:= bigmatrix = 
  Import["D:\\Advocate Solutions Data\\tempdata\\mxgenomepos.mx"];

In[2]:= Developer`PackedArrayQ[bigmatrix]

Out[2]= False

In[3]:= ByteCount[bigmatrix]

Out[3]= 47749114088

In[14]:= Length[bigmatrix]

Out[14]= 563529128

In[4]:= snippet = bigmatrix[[1 ;; 5]]

Out[4]= {{1000003366, 3000003502, 8008996525, 9000003338, 9000003355, 
  11000058489, 11000058556, 18000035094, 452000000077}, {1000003367, 
  2030619076, 2037867788, 2037874916, 3000003503, 7000005627, 
  9000003356, 9020814415, 11000058490, 11000058557, 14024858048, 
  17000037826, 18000035095, 22005169803, 227000017826, 398000020922, 
  452000002348, 601000056372, 610000213315}, {1000003368, 2030619077, 
  2037867789, 2037874917, 3000003504, 7000005628, 7000585479, 
  8000068458, 9000003357, 9020814416, 11000058491, 11000058558, 
  17000037827, 22005169804, 227000017827, 398000020923, 452000002349, 
  601000056373, 610000213316}, {1000003369, 3000003505, 7000585480, 
  8000068449, 9000003358, 9006789000, 11000058492, 
  11000058559}, {1000003370, 1000060283, 1000060290, 3000003506, 
  5000016791, 6018399431, 7000585481, 8000068450, 8012412220, 
  9000003359, 11000058840, 12000003521, 17000045433, 174000000051, 
  174000000168, 227000025433}}

In[5]:= Developer`PackedArrayQ[snippet]

Out[5]= False

In[6]:= ByteCount[snippet]

Out[6]= 1984

In[10]:= Map[ByteCount[#] &, snippet]

Out[10]= {256, 496, 496, 232, 424}

In[7]:= snippetpack = Map[Developer`ToPackedArray[#] &, snippet];

In[11]:= Map[Developer`PackedArrayQ[#] &, snippetpack]

Out[11]= {True, True, True, True, True}

In[9]:= Map[ByteCount[#] &, snippetpack]

Out[9]= {232, 296, 296, 168, 232}

In[12]:= ByteCount[snippetpack]

Out[12]= 1304

In[13]:= bigmatrixpack = Map[Developer`ToPackedArray[#] &, bigmatrix];

In[15]:= ByteCount[bigmatrixpack]

Out[15]= 99494766416

Any thoughts on why the strategy of packing individual sublists actually makes the memory usage worse? Are there any known ways of wrangling this kind of data (ragged lists of integers) to help minimize ByteCount?

$\endgroup$
5
  • $\begingroup$ Hm. If the ragged list is built in some recursive way in which many rows are reused frequently, then in principle one has to store only one copy of each row and a single pointer to the memory location for every occurence of that row. It pretty much depends on the structure of you dataset. $\endgroup$ Jan 18 at 22:06
  • $\begingroup$ @HenrikSchumacher For this particular data, every integer is unique, and none of the sublists repeat themselves. It is still puzzling why packing a small portion of the sublists works, but not the entire data. I seem to have a talent for "breaking" Mathematica with my use cases. Perhaps not all is lost - I've been thinking intently about the new ByteTrie data structure and might give that a go. $\endgroup$
    – Todd Allen
    Jan 19 at 16:46
  • $\begingroup$ Hm. Admittedly, I would have been surprised if Mathematica applied such a compression scheme under the hood... $\endgroup$ Jan 19 at 16:55
  • $\begingroup$ Just wondering: What is the largest integer in your dataset? And what is this data actually supposed to represent? Maybe there is a better way of expressing this or maybe this provides a hint on how to improve the compression. $\endgroup$ Jan 19 at 16:56
  • $\begingroup$ @HenrikSchumacher The largest integer is 639000023731. The data consists of position information for specific DNA sequences found within the human genome. What I really need is a memory efficient hash table. The data shared in this post would be the values that keys of the hash table point to. I've tried Association but it's just a memory hog. Some playing around with the new HashTable data structure also left me unsatisfied. I still hold a trickle of hope for the ByteTrie. Thanks for your curiosity. $\endgroup$
    – Todd Allen
    Jan 19 at 18:31

1 Answer 1

1
$\begingroup$

I don't think that you need a sophisticated hash data structure for storing and accessing this kind of data. You just need a sparse array A (whose entries are just True = entry present or False = no entry). Then A[[i,j]] tells you whether j lies in row bigmatrix[[i]] or not. Since a sparse array just stores nonzero entries, we can just forget about the True/False values and just exploit the compressed row storage format (CSR). In this format, your dataset would be represented by just two packed arrays of integers: rp (for row pointers) and ci (for column indices):

rp = Accumulate[Developer`ToPackedArray[Prepend[Length /@ bigmatrix, 0]]];
ci = Developer`ToPackedArray[Flatten[bigmatrix]];

All entries of bigmatrix are stored in ci, and the elements of each row are stored consecutively. The array rp tells us where to look for the entries of row i. So if you want to read the i-th row of bigmatrix, you can simply call this function:

getRow[i_] := ci[[rp[[i]] + 1 ;; rp[[i + 1]]]];

This should be the lightweightest hash table that you can get. It needs

Length[bigmatrix] + Length[Flatten[bigmatrix]]

64-bit integers, that is 8 times this number of bytes. (You cannot use 32-bit integers because your greatest number is 639000023731 > 4294967295 and the latter number is the largest number that can be stored in an unsigned 32-bit integer.)

As a toy example consider this:

snippet = {{1000003366, 3000003502, 8008996525, 9000003338, 
    9000003355, 11000058489, 11000058556, 18000035094, 
    452000000077}, {1000003367, 2030619076, 2037867788, 2037874916, 
    3000003503, 7000005627, 9000003356, 9020814415, 11000058490, 
    11000058557, 14024858048, 17000037826, 18000035095, 22005169803, 
    227000017826, 398000020922, 452000002348, 601000056372, 
    610000213315}, {1000003368, 2030619077, 2037867789, 2037874917, 
    3000003504, 7000005628, 7000585479, 8000068458, 9000003357, 
    9020814416, 11000058491, 11000058558, 17000037827, 22005169804, 
    227000017827, 398000020923, 452000002349, 601000056373, 
    610000213316}, {1000003369, 3000003505, 7000585480, 8000068449, 
    9000003358, 9006789000, 11000058492, 11000058559}, {1000003370, 
    1000060283, 1000060290, 3000003506, 5000016791, 6018399431, 
    7000585481, 8000068450, 8012412220, 9000003359, 11000058840, 
    12000003521, 17000045433, 174000000051, 174000000168, 
    227000025433}};
rp = Accumulate[Prepend[Length /@ snippet, 0]];
ci = Developer`ToPackedArray[Flatten[snippet]];
ByteCount[snippet]
ByteCount[rp] + ByteCount[ci]

1984

864

$\endgroup$
3
  • $\begingroup$ I like how you think, Henrik, and I agree that your proposed approach will reduce the ByteCount of my large matrix. I tried a similar approach weeks ago and it reduced the ByteCount of my large matrix from ~48Gb to ~7 Gb. Ultimately, I abandoned this approach because my true project will have many small sequences of DNA that must trigger the return of information in the large matrix. I tried to use a SparseArray to store the locations of data in a flatten version of the large matrix, but this also inflated memory. Thank you for your help and kindness of time. $\endgroup$
    – Todd Allen
    Jan 21 at 18:13
  • $\begingroup$ "Ultimately, I abandoned this approach because my true project will have many small sequences of DNA that must trigger the return of information in the large matrix". How exactly would that look like? Because if you know the row in bigmatrix where to look, the search within the row can be done quickly by binary search because the rows are ordered. $\endgroup$ Jan 21 at 19:06
  • $\begingroup$ Now the problem is probably mapping "small DNA sequences" to the row numbers. You could to that either by a hash map (with DNA sequences as keys and integers as values). Or you can use the lexicographic order of your DNA sequences to perform a binary search there. $\endgroup$ Jan 21 at 19:07

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.