Need a good overview for Succinct Data Structure algorithms

Question

(already asked on main site, but asking also here for better coverage, sorry)

Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in that area.

I have googled and read a lot of articles I could see in top of google results on requests from top of my head. I still suspect I have missed something important here.

Here are topics of particular interest for me:

1. Succinct encoding of binary trees with efficient operations of getting parent, left/right child, number of elements in a subtree.

   The main question here is as following: all approaches I know of assume the tree nodes enumerated in breath-first order (like in the pioneer work in this area Jacobson, G. J (1988). Succinct static data structures), which does not seem appropriate for my task. I deal with huge binary trees given in depth-first layout and the depth-first node indices are keys to other node properties, so changing the tree layout has some cost for me which I'd like to minimize. Hence the interest in getting references to works considering other then BF tree layouts.

2. Large variable-length items arrays in external memory. The arrays are immutable: I don't need to add/delete/edit the items. The only requirement is O(1) element access time and as low overhead as possible, better then straightforward offset and size approach. Here is some statistics I gathered about typical data for my task:

   typical number of items - hundreds of millions, up to tens of milliards;

   about 30% of items have length not more then 1 bit;

   40%-60% items have length less then 8 bits;

   only few percents of items have length between 32 and 255 bits (255 bits is the limit)

   average item length ~4 bit +/- 1 bit.

   any other distribution of item lengths is theoretically possible but all practically interesting cases have statistics close to the described above.

Links to articles of any complexity, tutorials of any obscurity, more or less documented C/C++ libraries, - anything what was useful for you in similar tasks or what looks like that by your educated guess - all such things are gratefully appreciated.

Update: I forgot to add to the question 1: binary trees I'm dealing with are immutable. I have no requirements for altering them, all i need is only traversing them in various ways always moving from node to children or to parent, so that the average cost of such operations was O(1).

Also, typical tree has milliards of nodes and should not be fully stored in RAM.

Answer 1

I assume that you are interested in succinct external memory data structures that are efficient in practice. In that case, you can probably get what you want with a few basic techniques and some engineering.

For trees, I would start with reading Arroyuelo et al.: Succinct Trees in Practice. The paper deals with trees in main memory, but most of the techniques can be used in external memory with similar choices as below.

As for your second question, the most important choice is deciding which encoding you use for the items. Given the distribution you describe, I would first try using $\gamma$-codes or $\delta$-codes. When you have chosen the encoding, the next step is to encode the array in blocks of size $B$, where the block size is chosen so that random disk reads of size $B$ are efficient in practice.

To find the correct block quickly, you need a rank dictionary that resides in main memory. Assuming that you have $n$ items, you build a binary sequence $S$ of length $n$, where $S[i] = 1$ iff item $i$ starts a new block. Gap encoding compresses the sequence well; Gupta et al.: Compressed data structures: dictionaries and data-aware measures gives one example of such index. If you want to find item $j$, then you need to retrieve block $rank(j)$ and decode it to get the item.

If you want to keep the rank index small, you have to make the block size quite large (probably kilobytes or tens of kilobytes), making the above basic solution CPU-intensive. This can be solved by adding a little overhead to the blocks stored on disk. Basically you apply the same solution recursively, so that each disk block stores a number of small blocks as well as another rank index. When you have retrieved the correct disc block, you use the rank index within it to find the right small block to decode, instead of decoding the entire block. With this secondary index, random accesses probably become I/O-bound even with the fastest solid-state drives available.