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:
- The data points required are constrained on the plane, (obvious maybe, but it bears repeating)
- 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.