Compressing 2D sparse matrix storage

Revision en3, by twoslow, 2019-02-20 23:24:11

Hello, codeforces community

  • I've a 2D sparse matrix of 0's and 1's of size NxN, where N = 16 Million i.e 16,000,000.
  • The number of non zeros(NNZ) in the matrix are ~450 Million. i.e 450,000,000.

What is the most efficient way to store the such matrix, given that I'll get the queries like:

  • What are the non-zero elements in row number x.
  • What are the non-zero elements in column number y.

Currently I'm storing the matrix in CSR format. Which takes an integer array of size NNZ and another array of size N.

Which is taking

  • (450000000 * 4 Bytes) / (1024 * 1024) ~ 1716MB of memory for row storage, and same amount of memory for column storage.

The overall memory to store such structure is about 3.5GB.

I want to compress it in a way such that the memory consumption is reduced and the queries can still be fast.

Any help regarding this is most welcome.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English twoslow 2019-02-21 19:16:05 4 Tiny change: 'nsumption and/or time co' -> 'nsumption or time co'
en5 English twoslow 2019-02-21 10:21:43 130
en4 English twoslow 2019-02-20 23:24:29 0 (published)
en3 English twoslow 2019-02-20 23:24:11 8 Tiny change: ' takes an array of ' -> ' takes an integer array of ' (saved to drafts)
en2 English twoslow 2019-02-20 23:23:18 67
en1 English twoslow 2019-02-20 23:15:06 896 Initial revision (published)