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