How to efficiently store a large but EXTREEMLY sparse amount of data in a 3D representation?

Question

I ran into this problem in the code I an working on: I need to be able to store a large amount of data in RAM, and be able to access it using three integer i,j,k (similar to x,y,z coordinates).

The problem is that if I try to use a 3D array, then even a simple data set will be represented as:

56000^3 bytes = 185000 GB        (where  0 <= i,j,k < 56000)

185 TB is an unreasonable amount of data, and the problems I will be using this on could potentially be much larger than 56000.

To fix this issue, I would like take advantage of the fact that this array is extremely sparse, and in fact, there will only be up 56 KB data in it (for the simple example above).

I am thinking of approaching this using a 3D linked list. This will guarantee that the required RAM will be on the order of magnitude of 100 KB. I got the idea from another page I was looking at online, and basically all I would need to do is:

List <List <List <nodes>>>       (where each list takes an i, j, or k index)

But before I spend several hours coding up a custom linked list solution, I was wondering if anyone had any better suggestions for storing a sparse set of data? The catch is that each node has to take 3 indexes i,j,k.

Thanks for your help and suggestions! :)

Answer 1

What about a dictionary like...

class vector3(){
int x,y,z;
}
Dictionary<vector3,object>