How to efficiently store large sparse array

0
votes

I am tracking particles into a 3D lattice. Each lattice element is labeled with an index corresponding to an unrolled 3D array

  S = x + WIDTH * (y + DEPTH * z)

I am interested in the transition form cell S1 to cell S2. The resulting transition matrix M(S1,S2) is sparsely populated, because particles can reach only near by cells. Unfortunately using the indexing of an unrolled 3D array cells that are geometrically near might have big difference in their indexes. For instance, cells that are siting on top of each other (say at z and z+1) will have their indexes shifted by WIDTH*DEPTH. Therefore if I try accumulating the resulting 2D matrix M(S1,S2) , S1 and S2 will be very different, even dough the cells are adjacent. This is a significant problem, because I can't use the usual sparse matrix storage.

At the beginning I tried storing the matrix in coordinate format:

  I , J VALUE

Unfortunately I need to loop the entire index set to find the proper S1,S2 and store the accumulated M(S1,S2).

Unusually sparse matrices have some underlying structure and therefore the indexing is quite straightforward. In this case however, I have some troubles figuring out how to index my cells.

I would appreciate your help Thank you in advance,

1
arraysmatrixstoragesparse-matrix

1 Answers

1
votes

There are several approaches. Which is best depends on operations that need to be performed on the matrix.

A good general purpose one is to use a hash table where the key is the index tuple, in your case (i,j).

If neighboring (in the Euclidean sense) matrix elements must be discoverable, then an alternate strategy is a balanced tree with a Morton Order key. The Morton order value of a key (i,j) is just the integers i and j with their bits interleaved. You should quickly see that index tuples close to each other in the index 2-space are also close in linear Morton order.

Of course if you are building the matrix all at once, after which it's immutable, then you can build the key-value pairs in an array rather than a hash table or balanced tree, sort them (lexicographically for (i,j) pairs and linearly for Morton keys) and then do reads with simple binary search.