# What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree on disk, given the following conditions:

• It is very sparse (i.e., not all nodes exist), but potentially deep (a depth of 20 or beyond)
• It is stored depth-first (pre-order)
• All parent nodes up to the root node must be stored (i.e., it is not sufficient to store just the leave nodes)
• The amount of data per node is a global constant

The best I can come up with is 6 7 bits per node: 3 bits to indicate the position of a node with respect to its parent, and 3 4 bits to store how many child nodes exist. However, intuition tells me there should be a more efficient way. Please note that algorithmic efficiency is not part of the question, as its representation in memory will be different anyways.

P.S.: Please let me know if CS is not the right SE venue for this kind of question.

Update

The resulting data structure will be stored in a file on disk, thus the need for an efficient encoding of the octree. There are additional data files that contain information associated with each existing node (e.g., solution data). To have a one-to-one relationship between nodes ("cells") in the octree file and the datasets, it is required to store all internal nodes (i.e., non-leaf nodes) in the octree file as well.

Example

An octree with 5 nodes: 0, 1, ..., 4. Their relationship is the following:

• 0 is the root
• 1 is child 0 of node 0
• 2 is child 1 of node 1
• 3 is child 5 of node 1
• 4 is child 1 of node 0

The resulting tree would look something like this (with missing nodes omitted)

 0 / \ 1 4 / \ 2 3 

and the nodes need to be stored 0 1 2 3 4 (pre-order depth-first).

• Can you clarify what "stored depth-first" means? If you can use pre-order or post-order, it's enough to just store how many children each node has (but not its position with respect to its parents/siblings). If you know something about the distribution of number of children, and it is non-uniform, you might also be able to use a variable-length code for "number of children" (e.g., a Huffman code). – D.W. Jun 23 '17 at 0:20
• @D.W. I updated the question: yes, it is pre-order, but there is no information on the distribution of the number of children. Furthermore, the amount of information per node must be constant to allow efficient parallel I/O. – Michael Schlottke-Lakemper Jun 23 '17 at 6:55
• Could you use a different data structure? For example a PH-Tree is quite compact, it is a bitwise, prefix-sharing, and morton-ordered tree. Each coordinate stores only as many trailing bits as are required to distinguish it from other coordinates/subnodes in the same node. In some scenarios, I found that the whole tree (including coordinate data) requires less memory than a simple array with the same coordinates. – TilmannZ Jun 23 '17 at 14:09
• There is also a C++ version available of the PH-Tree. – TilmannZ Jun 23 '17 at 14:18
• The term to search for in the literature is "succinct data structures". – Raphael Jul 13 '17 at 18:04

Assume simple setting, data is three chars, the coordinates are in fixed-point float

• 0) "tak"
• 1) "kot"
• 2) "mak" [76, 102, 179]
• 3) "las", [51, 76, 153]
• 4) "pas" [179, 179, 153]

The floating point values converted to 8 bit fixed point and z-order curve computed. For example take 3)

51 (110011b), 76 (1001100b), 153 (10011001b)

Interleaved

• 51 -> 000 000 001 001 000 000 001 001
• 76 -> 000 001 000 000 001 001 000 000 shift by one to the left
• 153 -> 001 000 000 001 001 000 000 001 shift by two to the left

• Orred 100 010 001 101 110 010 001 101

Coordinates converted to codes:

1. 100 011 110 100 001 011 110 100
2. 100 010 001 101 110 010 001 101
3. 111 000 011 111 100 000 011 111

sort encoded indices

1. 100 011 110 100 001 011 110 100
2. 100 010 001 101 110 010 001 101
3. 111 000 011 111 100 000 011 111

The index of the child is encoded in the bit triplet at the current level of tree. While traversing the level counter should be kept.

Store to file, add 1 bit per node

• 0 - internal node
• 1 - leaf

Check the location code, while the parent code matches, we are in the same subtree, otherwise traverse up until the next code location matches or to root.

For simplicity I will split it into three files (but it may be one, since the widths are constant)

• type) 0111 (bits)
• data) takkotlasmakpas (3 letter string)
• indices) 100011110100001011110100100011110100001011110100111000011111100000011111 (bits)

How it would work?

Checking the location means to compare bits from the most significant one taking as many bit triplets as level counter shows, here root has level 0

2. Read index, data and type
3. if type is 0, store internal node as n-th child from location index at current level, store data, go to this node, increase level counter read another data and type, repeat 3) until type is 1
4. if type is 1, store child, read next index, data and type. If location code mismatches then traverse up until full match or root encountered. At every step up decrease counter.
5. if not EOF goto 2

Here overhead is 1 bit per existing node only.

How would it work in the example?

create root ("tak")

read first index (100 011 110 100 001 011 110 100), read type (0) and read data ("kot")
create node as the 4-th child (100), store data

read type and data (1, "las"),
store data in node, put the next node as 3-rd (011) child, ++level

read (1, "las"),
create 6-th node (110) and store "las", decode index into coordinates
(100 011 110 100 001 011 110 100 -> [76, 102, 179])

store current location code (100) as last one (triplets up to level)

read another one, (100 010 001 101 110 010 001 101), (mak, 1),
check whether location code matches up the last one (here it is 100 == 100)

put node as 2-nd (010) child, store data, decode index into coordinates (100 010 001 101 110 010 001 101 -> [51, 76, 153])

read another one, (111 000 011 111 100 000 011 111),
the location code mismatches (111 != 100), while no match go up (or until root level)

store node as 7-th (111) child, decode index into coordinates
(111 000 011 111 100 000 011 111 -> [179, 179, 153])