Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

Question

This question is related to my previous question:

Looking for a set implementation with small memory footprint

I'm looking for information about combined data structures, which can efficiently represent a set S of non-intersecting sub-intervals of the given integer interval [0, MAX) with the single operation:

• testAndInsert(min, max) - test if the interval [min, max] intersects with any of already existing intervals in the S; if no intersections are found, then insert the interval [min, max] into the set S, potentially merging it with one or two neighbor intervals; return success, if and only if the insertion was done.

I'm asking about combined data structures, because it looks like we have two evident choices - linked data structures (for example, various binary trees) and array-based data structures (bitmaps). However, both of them have their own shortages:

• Balanced binary trees will have O(log(n)) time complexity and look good, when number of intervals in the S is much less than the MAX. However each node of the tree will take at least 16 bytes (for links) on 64-bit machine. For example, if we represent all odd integers in the interval [0, 1000), then we'll need 8000 bytes only for links.

• Bitmaps will have O(1) time complexity, but take constant memory, which depends only on the MAX. Representation of all the odd integers in the interval [0, 1000) needs only 125 bytes. However, when the MAX is large and the number of existing intervals is much less than the MAX, then most of the memory, taken by the bitmap, will be wasted.

I'm not actually focused on the time complexity - something between O(1) and O(log(n)) is acceptable, but in real situations the memory footprint of the data structure plays a very important role. If machine begins swapping because of lack of memory, then even O(1) data structure will work for ages.

Are there any data structures, which could automatically adapt themselves to the size of the S in this problem? For example, when we start with the empty S (no intervals at all), the data structure is linked, then it becomes array-based (piece by piece?), then it probably switches to storage of the S complement (free space is small) and becomes linked again?

P.S.: I know about the Boost ICL interval set and use it now, but I'm interested in other possible approaches.

Answer 1

Here is one space-efficient memory-hierarchy-aware in-memory data structure that might be a reasonable choice. The data structure is a binary search tree with 16-byte nodes.

Each node is either an internal node or a leaf node:

• An internal node points to two children. It has a value $v$, a left child $\ell$, and a right child $r$. All integers $\le v$ are in the left child; integers $>v$ are in the right child.

• A leaf node holds a run-length encoding of a bitmap. Notice that an interval has a very short run-length encoding, so this is slightly more general than storing an interval in each leaf (it is a hybrid somewhere between a binary tree of intervals and a binary tree of bitmaps).

Each node of the tree is responsible for some interval of integer values $[s..t]$. The root is responsible for $[0..\text{MAX}-1]$. For an internal node containing the value $v$, its left child is responsible for $[s..v]$ and its right child is responsible for $[v+1..t]$. A leaf that is responsible for $[s..t]$ has a run-length encoding of the bitmap for the integers in the interval $[s..t]$.

How do we pack each node into 16 bytes?

• I'll assume the tree contains at most $2^{32}$ nodes in the tree. Therefore, each node can be referred to by a 32-bit label. We'll have an array $A$ of nodes, and the node with label $i$ will be stored at $A[i]$. With this optimization, each child pointer can be stored in 32 bits (rather than 8 bytes for a 64-bit pointer). Note that the restriction to $2^{32}$ nodes is not very restrictive; unless your machine has more than 64 GB of RAM, you couldn't fit anything larger in memory anyway.

• I'll assume that $\text{MAX} \le 2^{64}$.

• The first bit of the node will indicate whether it is an internal node or a leaf node, leaving 127 bits for the rest.

• Internal nodes: We need 64 bits for the two child pointers. That leaves us 63 bits for the value $v$. We'll store the value $v$ as an offset within the interval for that node. In other words, if the internal node is responsible for the interval $[s..t]$, then we'll store $v$ as the value $v-s$. (We know $v \in [s..t]$, so it follows that $v-s$ is a non-negative integer.) A 63-bit unsigned int is plenty for this offset. (If we wanted to use an offset that is larger than will fit in a 63-bit unsigned int, then we just split the range artificially. Since $\text{MAX} \le 2^{64}$, this will impose at most one or two extra splits at/near the root.)

• Leaf nodes: We have 127 bits for the run-length encoding of the bitmap corresponding to the interval $[s..t]$. We can use any convenient run-length encoding. If the run-length encoding of the bitmap does not fit within 127 bits, we split the interval: we turn it into an internal node with two children.

  If you know something about the typical distribution of lengths of runs (i.e., the lengths of intervals, the lengths of the gaps between intervals), you can choose a run-length encoding that is optimized for that distribution. Otherwise, you can use any convenient generic run-length encoding scheme (e.g., recursive Rice-Golomb encoding); see also this Wikipedia page on compressed bitmaps.

Notice that we don't store $s$ or $t$ in each node, but that's OK. The interval $[s..t]$ for a particular node is determined by the path that we took to reach that node. As we traverse down from the root, we can keep track of the interval $[s..t]$ and update it each time we follow a child pointer.

If you wanted, you could combine with this with some sort of self-balancing binary tree scheme )or a self-optimizing binary tree, such as a splay tree), but it might not be necessary in practice, depending upon the access pattern in your application, and it definitely adds complexity.