Multidimensiona l sparse arrays using linked lists

[skr13]

Hi,

I am implementing an aggregation model to compute data cubes.
I have implemented the multiway array aggregation statically. That is if there are, say, 4 dimensions each of cardinality 16 and the chunk size of 4, I create chunkArray[4][4][4][4] and insert the measure at the appropriate position and aggregate the measure. The chunkArray is a sparse array and static implementation is not efficient. In order the dynamically create the chunkArray with measure stored only for the instances that occur I need the offset of each of the cell in the chunk.

Eg: Dimension 3
A[8], B[8], C[8] - each dimension with cardinality 8.
If the relational database table is fully populated then there will be 8*8*8 instances in the table.
If not, then some of the instances will be missing.
a1,b1,c1,20
a1,b1,c2,3
.......
.......
a1,b1,c8,12

This will be like the truth table with 3 variables each of which can take upto 8 values as compared to 2 values in the digital truth table.

The aggregation will be done on chunks. If I have instances a1,b1,c1 - a1,b1,c3 - a1,b1,c8 - some of the instances will be missing. What I need then is an offset of the instance from the first instance.
a1,b1,c1 offset=0
a1,b1,c3 offset=2
a1,b1,c8 offset=7

Suppose the chunk size is 2 in all dimensions, the the total number of chunks will be 8. I will bring in the first 8 chunk cells and aggregate. But the problem is, in the first 8 cells only 3 are dense and rest 5 are not there. I am stuck in finding the offset of the chunk cell. If you have any idea, please let me know.

[jkmyoung]

Could you give us a better idea of how you will be using the chunks in the future? I'm not sure what the difference is between this and a table sorted on a then b then c.

[skr13]

I will be using the chunks to aggregate the values present in them. For eg,

chunkArray[0][0][0] = 5;
chunkArray[0][0][7] = 9;

when i aggregate keeping the first 2 indices constant, i ll get 13.

Say A represents CITY, B represent ITEM and C represents TIME.
These are the 3 dimensions for the chunk.

CITY ITEM TIME
0- X 0-i1 0-t1
1- Y 1-i2 1-t2
2- Z 2-i3 2-t3

the measure may be sales. keeing A=0 B=0 and aggregating alon C, I will get the sales in city X for item Y for all the times

[Banfa]

Are you using C or C++? If you are using C++ and you expect the array to be quite sparse I imagine a map would work quite well.

On the other hand if the array is only slightly sparse (only a few missing values) then it might be just as easy and less complicated to use a static array.

[weaknessforcats]

One suggestion is to use an array of struct variables. One member is your data and the other is a binary that is true of the data is present and zero otherwise. This allows you to have zombie elements.

That way your calculations to get to an element will always work out.

[skr13]

I used linked lists to create an element in the list only if the data is present and used the dimensionality to calculate the offset. Now i am storing the data and the offset in each element of the list, thereby I have saved lot of memory.

[jkmyoung]

I agree with using an array (sorted) that only contains the values as opposed to a linked list, giving a small memory savings, and negating the need for offsets.

The advantages I can see to linked lists occur if you are querying the first few elements repeatedly, or adding many elements after the initial creation.

struct Row{
short a, b, c, value;
}
 
Row[] Table = new Row[100];
 

This does really feel like database work

[skr13]

I need to query the table. For eg, SELECT FROM TABLE where CITY=X and TIME=t1.
For this i need to pre-compute the data cubes and store them. Actually I have the table for chunks.

struct chunks
{
int value,offset;
struct chunks *link;
};

It would be easier if the used arrays to compute data cubes but the problem is I will know the array dimension only during runtime. I would appreciate any other idea to compute the data cubes(aggregati on).

[weaknessforcats]

It would be easier if the used arrays to compute data cubes but the problem is I will know the array dimension only during runtime.

You can create the array at run-time after you know the dimensions.

I have written a SQL cursor manager to capture the results of a SELECT using arrays. You really need to avoid linked lists as they are too slow. You also avoid the stack since memory there is often restricted.

BTW: You didn't answer Banfa about whether you are using C or C++. If C++ you should be using a vector.

[skr13]

I am using C++. For each attribute in the table there will be 1 dimension. If the table has 20 dimensions then I will need a 20-dimensional array. This 20 dimensional array will be a sparse array. Linked lists are slow but the memory will not be wasted. And just curious, how do you create 20D array at the runtime?