Since I Knew About Brief Data Structures I desperately need good information about recent developments in this area.
I searched googled and read a lot of articles that I could see at the top of google results for queries from the head. I still suspect that I missed something important.
Here are topics of particular interest to me:
Short encoding of binary trees with efficient operations of obtaining the parent, left / right child element, the number of elements in the subtree.
The main question here is this: all the approaches that I know suggest that the tree nodes are listed in first breath order (for example, in pioneering work in this area by Jacobson, J.J. (1988). Brief static data structures) that not suitable for my task. I am dealing with huge binary trees specified in a layout with depth, and node depth indices are keys to other node properties, so changing the layout of the tree has some cost for me that I would like to minimize. Hence the interest in obtaining links to works examining other layouts of the BF tree.
Large arrays of variable length elements in external memory. Arrays are immutable: I do not need to add / remove / edit elements. The only requirement is the access time to the O (1) element and the lowest possible overhead is better than a simple offset and size approach. Here are some statistics that I have collected about typical data for my task:
a typical number of items - hundreds of millions, up to tens of billions,
about 30% of the elements have a length of not more than 1 bit ;
40% -60% of elements are less than 8 bits long;
only a few percent of the elements are 32 to 255 bits long (255 bits is the limit)
average element length ~ 4 bits +/- 1 bit.
theoretically, any other distribution of the lengths of objects is possible, but all practically interesting cases have statistics close to those described above.
Links to articles of any complexity, textbooks of any unknown, more or less documented C / C ++ libraries - everything that was useful to you in similar tasks or something similar to your educated guess - all these things were gratefully appreciated.
Update: I forgot to add to question 1: the binary trees I'm dealing with are immutable. I have no requirements for changing them, all I need is just to move them differently, always moving from node to children or to parents, so the average cost of such operations was O (1).
In addition, a typical tree has millions of nodes and should not be fully stored in RAM.
Update 2 Simple, if anyone is interested. I got a couple of good links at https://cstheory.stackexchange.com/a/11265/9276 .
source share