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

Question

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).

Answer 1

The number of octrees with $n$ nodes is OEIS sequence A007556:

$$T(n) = {8n \choose n}/(7n+1)$$

I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it.

If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$. (We're doing information theory here, so all logarithms are in base 2 unless otherwise specified.) Using Stirling's approximation to the logarithm of the factorial:

$$\log n! = n \log n - n \log e + O(\log n)$$

We find:

$$\log\,T(n) = (24 - 7 \log 7) n + O(\log n)$$

Which works out to $24 - 7 \log 7 \approx 4.349$ bits per node. So to answer the first part of your question, this is the theoretical minimum. You cannot do better than this.

Now we just have to address the second part: How close can we get?

Consider a bit vector of size $8n$, $8$ bits per node, where you put a 1 if the node has a child in that slot, and a 0 if it doesn't. This obviously uses about twice the space theoretically needed.

However, 0's and 1's don't occur with the same frequency. Specifically, given an octree with $n$ nodes, exactly $n-1$ of the bits must be 1 (exercise: why?), leaving $7n+1$ of them 0. The entropy of a bit is, therefore, approximately:

$$H = -\frac{1}{7} \log \frac{1}{7} - \frac{6}{7} \log \frac{6}{7} \approx 0.59$$

So you should be able to compress the bit vector to $8nH \approx 4.733n$ bits.

The actual compression method that I will suggest, because it's easy to understand and doesn't use anything complicated to implement like arithmetic coding, is Elias-Fano coding with parameter $b=2$.

We'll use your octree as an example. The bit vector corresponding to your exanple is:

11000000 01000100 00000000 00000000 00000000

We know that because $n=5$, the number of bits that are set must be $n-1=4$. We work out the indexes of the bits that are set:

$$\left\{0, 1, 9, 13\right\}$$

Or in binary, using $\left\lceil \log(8n) \right\rceil = 6$ bits per entry:

0000 00
0000 01
0010 01
0011 01

I've separated the low order $b$ bits for a reason. The compressed representation has two parts, one for the high-order bits and one for the low-order bits.

For the low-order bits, we just store these in an array. That is:

00 01 01 01

For the high-order bits, we count the patterns. Since there are no indexes that are larger than $8n-1=39$, There are only 10 possible patterns for the high-order bits:

$$\{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001\}$$

We count the number of indices with each of the high-order patterns, and then encode those counts using a unary code:

110 0 10 10 0 0 0 0 0 0

(In practice, you probably don't need to work out all the high-order bit patterns, just stop when you run out of indices. But I digress.)

On this example, the representation uses 8 bits for the first array, and 14 bits for the unary-encoded bit vector, for a total of 22 bits, or 4.4 bits per node.

Recall that the asymptotic theoretical minimum is 4.349 bits per node.

Working out the asymptotic size of this representation as $n \rightarrow \infty$ is left as an exercise. So is actual code to do the compression and decompression.

Finally, I know you didn't ask about algorithmic efficiency, but storing the bit vector in an SDArray with succinct rank/select indices (there are implementations all over the place; look them up), you should be able to make this data structure random access in close to constant time. That is, you should be able to query the octree in its compressed form. The details are, again, left as an exercise.

Answer 2

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:

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

sort encoded indices

3. 100 011 110 100 001 011 110 100
4. 100 010 001 101 110 010 001 101
5. 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

1. Read data, create root
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])

Answer 3

fixed-size node

Pseudonym has almost convinced me that it's not possible to store such a tree with only 4 extra bits per node. Here's one way to store it with a fixed overhead of 5 extra bits per node:

• 3 bits to indicate this node's position relative to its parent
• 1 bit to indicate whether or not it is a leaf (i.e., whether or not it has any children)
• 1 bit to indicate whether this node is the last of its siblings.

Reading each node one fixed-size block at a time in depth-first pre-order, we have something like:

node_list = []
total_nodes = 0

read_branch( parent_index, current_index, file, node_list ):
    disk_node = read_node( file )
    node_list[current_index].data = disk_node.data
    node_list[current_index].parent = parent_index
    node_list[current_index].position_relative_to_parent = disk_node.relative_position
    global total_nodes += 1
    # read all children and their descendents first, if any
    if( disk_node.has_children ):
        total_children =
            read_branch( current_index, current_index + 1, file )
    else:
        total_children = 0
    # read next sibling, and all other siblings, and their descendents, if any
    if( disk_node.has_sibling ):
        total_siblings_and_their_descendents =
            read_branch( parent_index, current_index + 1 + total_children, file )
    else:
        total_siblings_and_their_descendents = 0
    return (1 + total_children + total_siblings_and_their_descendents)

read_entire_tree():
    file = open_file("the_octree")
    root_index = 1
    estimated_total_nodes = read_branch( null, root_index, file, node_list )
    assert( estimated_total_nodes == total_nodes )

Other alternatives

Here are some ways of compressing it even more, but in ways that are significantly more complex and bug-prone.

The octree could be stored in even less space if it used some variable-sized encoding that used less than 5 bits per node most of the time (even if it required much more than 5 bits per node occasionally). (Huffman coding, arithmetic coding, gzip, LZJB, etc).

Whenever a node had more than 2 children, rather than always store the children in some fixed order, a little information could be encoded into the order the children were stored. For example, perhaps each node could have 2 bits that indicated whether it was a leaf (0 children), or had 1, 2, or "more" children. Then if it had "more" children -- i.e., at least 3 children -- then the first 3 children could be read, and the order of those children -- ABC, ACB, BAC, BCA, CAB, CBA -- could be decoded into a number 0..5 and interpreted as indicating 0 to 5 more children past the 3 already read.

I suspect that storing the tree in some other order -- perhaps breadth-first or leaf-first -- might allow the tree to be stored in less space.