Caching in '3D' - data-structures and octree recursion - hrrm!

Question

The Situation:

I have 68GB of data that is conceptually realized as a 3D matrix of 8-bit values with dimension 4096*4096*4096.

I need to access multiple sections of this data for processing in a time critical setting (multiple as in sequential one after another). Each section would be approximately 50MB in size.

The sections can be thought of as arbitrary planar slices through the cube (but constrained within it). The sections can go through the cube at any orientation and placement, they will not line up with the 3-axes often.

I cannot load 68GB in to RAM – Let's say I only have 8GB, of which the OS etc. is using already.

I need a way to efficiently partition the 68GB of data so that I can access the data required by the sections.

Proposal:

As the data is conceptually 3D I propose to recursively partition it as octants (2^3=8). Starting at ‘the data’ at the top layer, and moving all the way down the octree to the data points themselves.

Each layer of recursive detail would have a 3-bit address for each of its octants – so if the original data were just a 4*4*4 cube, each data point would have a 6-bit ‘address’:

For the real example we would need log2(4096*4096*4096) = 36bits to address each data-point.

---

More Situation:

While the section orientations and positions are arbitrary – two factors work in my favor:

1. The data points required are constrained on the plane, (obvious maybe, but it bears repeating)
2. The required sections will be reasonably close to each other over time - i.e. requiredSection1 will be close to requiredSection2 which will be close to requiredSection3. By ‘close’ I mean that it is very likely there will be crossover in data points required for the sections. It is very likely also, but less so, that section3 will have an overlap with section1 … and so on.

More Proposal:

I see potential for a Least Recently Used (LRU) cache here where at some ‘depth’ of the recursive octant partitioning I stop and decide that this is the new ‘smallest’ element. It is these chunks of data that are actually loaded and unloaded into RAM. (might be worth pointing out I'm not caching results, I'm caching input data to a function)

As an example, say I partitioned it into 32*32*32 chunks, I would need log2(32*32*32) = 15bits of data to address each chunk. These would each contain 4096^3/32^3 = 2097152 points of data (log2(2097152)=128) and be approximately (4096^3/32^3)*8 = 2MB large.

(Size would be experimented with)

It is these chunks that would be loaded into and out of the RAM via the LRU cache - the idea being that the data in the cache from prior iterations would already contain the chunks that contained the required data points for the current iteration.

Win! (right?)

As the required sections moved about sooner or later a new 32*32*32 chunk of data would be required - assuming the RAM allocated to the task was full already, the new section would be loaded (taking a hit on disk access), and it would take the place in RAM of the ‘least recently used’ chunk, which is likely (but not garunteed) to be the one least likely to be needed in the future.

---

The Questions (sorry, no TL;DR here):

I don’t see the LRU management to be an issue - however, what I am interested in is:

• Is this viable?
• How can I best manage the data in terms of data-structures, both on disk and while in RAM?
• How can I best leverage the recursive nature of this in code?
• How not to blow up RAM just dealing with addressing itself?

Likely I'll be using openCV in either a C++ or Python environment.

Answer 1

What I would do.

Repackage the data on disk in small cubes, a few KB each. That is, if the data are represented as a typical array of arrays of arrays, the points that are close in the 3D space are not close in the representation. I'd try to overcome that. The result would be a the same amount of data, addressable in two steps. First step would be finding the address of the small cube, the next (slightly trickier) step would be finding the point within that cube. You already have a right picture, it's just has too many levels. Just one additional level may be enough.

If we make the small cube's dimension 16 * 16 * 16, it will take up 4 KB. To find the address of the cube, each coordinate would have to be shifted left 4 bits. Coincidentally, 4 KB is the typical OS RAM page size.

The repackaging process would need to keep in RAM the amount of data one small cube thick, that is 4096 * 4096 * 16 = 256 MB. Quite doable; several small cube layers can be calculated at once with a few GBs available.

Now I would plainly access the new file that uses small cubes, translating the coordinates.

The OS cache would keep the small cubes in RAM for me pretty efficiently. Since one layer of cubes is merely 256 MB, and an arbitrary planar section cannot require more that 2 layers worth of small cubes to include all the points, the whole working set would require 512 MB worth of small cubes.

The OS cache would happily keep all of them in RAM for you, provided that your program leaves slightly more than 512 MB of RAM free when running. Now, when you try to access data for a particular cube, it will be served from RAM, provided that it has been touched in the past.

You can make things even more explicit by memory-mapping your file (read-only) and accessing the whole 64 GB worth of address space of it; only the pages (small cubes) you actually access will be mapped, that is, loaded from the disk.

This rids you of implementing any caching yourself (always tricky), and rids you of spending RAM on an explicit octree structure. With a space as regular and simple as a cube, you can as well use an implicit pre-built one :)