Compressing 2D sparse matrix storage

Revision en2, by twoslow, 2019-02-20 23:23:18

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 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)