Sparce Data Sets? (Huge Hypermatrix)

[mmxbass]

I am currently storing a hypermatrix of not very many objects over a 4d hyperspace.

I am working with a 100x100x100x100 hypermatrix that is VERY sparsely populated. Only about 500 cells actually contain anything. The problem is that this matrix takes up huge amounts of memory even when it's mostly empty. Is there a python class type available to me that is able to store this type of hypermatrix efficiently?

I need to be able to access objects given w,x,y,z coordinates but I fully expect the vast majority of them to be overwhelmingly EMPTY.

[Murtan]

You could use a dictionary where the key was the composite index, something like key = "%d_%d_%d_%d" % (w,x,y,z) or key="W%dX%dY%dZ%d" % (w,x,y,z) . I think the dictionary would manage the collection fairly well.

[mmxbass]

How will that effect performance when I try to READ 30 empty ana/kata spaces.

My display will be a 2-dimensional top-down ana-katawise/kata-anawise switchable projection. The anamost and katamost hyperside spaces will ALWAYS have at least one fully populated x-y plane (i.e. you can never see outside of the hyperspace given either top-down ana-katawise or top-down kata-anawise projection).

My problem with this projection is that when I am viewing a 2d x-y plane with some width and bredth, when I am centered at location, say 50,50,4,80 on a 100x100x4x100 hypermatrix I run into the problem that I have to attempt to read from ALOT of cells in a top-down ana-katawise 2d projection.

How fast will I be able to read through all that empty hyperspace? Even a projection window of 20x20 cells will require me to read something like 128,000 cells in the earlier example. I need to be able to do this at a managable framerate.

PS: I'm sorry if this is confusing. This took me almost 10 minutes to write and was as difficult to explain as it probably is for anyone to read.

PPS: I also don't know any way I could quick-fetch a hypercolumn of spaces using your method.

[Murtan]

You didn't note any constraints other than "the array is mostly empty, and how can I make it smaller" so I wasn't concerned with any.

In the case of the dictionary, we would only store the data values that exist, the 'empty' spots would not exist. Testing for whether or not something exists in a dictionary is pretty straightforward but I'm not sure about your read/framerate.

So are you saying that for every frame, you might have to read 128,000 cells?

If so, what defines a 'manageable framerate'? (Is this really a 'I need to generate at least X frames a second' requirement?)

The method I proposed probably doesn't support a 'quick-fetch' of anything, let alone a hypercolumn.

To be honest, I'm not familar with the terms you're using. I supposing a hypermatrix is called that because it exceeds three dimensions?

What is a hypercolumn?

How is it defined in terms of the array dimensions?

(Which index values would remain constant? Which would change?
)

I attempted to google for your projection terms and didn't get any hits there either. Could you give a rough overview of how the projection is developed? (pseudo code is probably better than real code) for my purposes.

I'm trying to better understand what you are doing to see if I have (or can find) a 'better' answer.

[mmxbass]

I think I may have come up with a fairly simple solution.

We have 8 directions we can move in.
North, south, east, west, up, down, ana, kata (ana and kata are actual terms to define movement in a 4th spacial dimention, ana would be analogous to up/north/west and kata to down/south/east).

So my idea was, rather than use some kind of array type. Start off with a 2 2d grids of object references. The 1st grid will point to the bottom(downmost) layer of the katamost space. The 2nd grid will point to the bottom(downmost) layer of the anamost space.

Then all i need to do is give every cell a reference to all 8 of its neighbors.

This makes rendering a snap now because all I have to do is play follow the pointer, and because the projection is top down and either ana-katawise or kata-anawise from some point in the hyperspace (4 dimensional analog of space, another not-made-up actual term), all I have to do is, depending which direction view from, start at the bottom layer of either the ana or kata ends, follow the references either anawise or katawise until we reach my camera point. Then we go back and draw the next layer and so on.

This will be very VERY fast and use up almost no extra space because the references will let me instantly skip over the empty space. The only two drawbacks are that each cell needs to know its own location (not a big deal) and that assembling the map in memory may potentially take a while (also don't care as long as its fast once the load is finished).

To explain a few things, I'm basically trying to project a 4 dimentional space onto a computer screen. I know how the math and physics are all supposed to work but there generally aren't many elegant solutions to deal with the fact that modern graphics hardware is not designed to handle 4 dimensional math so I need to get creative.

Using the above method each hypermap will be represented by a 4 dimentional mesh (which is equivalent to a map data structure as long as you don't care about planarity). Think of it like an octupally-linked 4 dimensional analogue of a list.

PS: I'm making a maze. It's going to be hard.

[Murtan]

So ana and kata are moves in the fourth dimension of the matrix.

You mention giving a cell a reference to all 8 of its neighbors. That sounds like it might be the hardest part of building the data structure. (I'm presuming you mean a link to the nearest cell in that direction).

Just to clarify my understanding (seems like you have it all down), the four indices are used for the following directions: east(-)/west(+), north(+)/south(-), up(+)/down(-), ana(+)/kata(-).

So the 'neighbor' link in the east direction would be to the cell that has the last three index values the same and the next lower value in the first index?

Just curious, what if there are no more cells before the edge of the map? Are you going to use a 'null' pointer, a pointer to a signal value or pointer to an edge node?

For this thread, I think you've been more help to me than I was to you :)

[mmxbass]

So the 'neighbor' link in the east direction would be to the cell that has the last three index values the same and the next lower value in the first index?

Yes that is the idea (except I think west would be lower on most coordinate systems, not east). It makes insertion of nodes a linear time operation but I don't care because the hypermatrix can take 3 minutes to build for all I care. As long as it works quickly once it's done being built. That being said, the only way to build up the hypermatrix like this is if every cell knows its own location. This is not a HUGE deal, as it only adds something like 16 bytes extra per node. I think I can keep the framerate over 30 if I do this. My major drawback is that I have to do alot of hard work in software because modern video hardware doesn't know how to do 4 dimentional geomerty. (I wouldn't expect them to add it within the next 20 years either.)

Just curious, what if there are no more cells before the edge of the map? Are you going to use a 'null' pointer, a pointer to a signal value or pointer to an edge node?

They are just going to point to null. I don't worry about this so much because the anamost and katamost ends will ALWAYS have a fully populated x-y plane in lowest z-level (meaning they always have a complete floor). This will make sure that in a top-down ana-katawise or top-down kata-anawise projection that you won't ever accidentally see through out any holes. (This could presumably happen if, for example, the player was hugging the katamost end of the playing field and had a top-down ana-katawise camera angle.) Also I will always know the width of the map in all 4 dimentions.

Believe it or not, this is the easy part. Finding decent sprite artists is MUCH HARDER.