<p>I'm reading the paper <em>Succincter</em> by M. Patrascu (<a href="http://people.csail.mit.edu/mip/papers/succinct/succinct.pdf" rel="nofollow">link</a>).</p>

<p>It introduces on page 7 the <em>aB-tree</em>. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the leaves. Every node is augmented with a value from some alphabet. The value of a leaf is a function of its array element, and the value of an internal node is a function A of the values of its B children, and the size of the subtree.</p>

<p>The query algorithm examines the values of the root’s children, decides which child to recurse to, examines all values of that node’s children, recurses to one of them, etc. When a leaf is examined, the algorithm outputs the query answer. We assume the query algorithm spends constant time per node, if all values of the children are given packed in a word.</p>

<p>The part I'm having difficulties with is the following: <em>The queries can be solved in constant time per node if the values of all children are given packed in a word. This uses very standard ideas from word-level parallelism that we omit.</em></p>

<p>Could somebody please point how does word-level parallelism achieve this ?</p>

<p>Also, is there a practical implementation of this structure (and its application to succinct rank/select bitvectors) ?</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2012-09-29T02:09:38.480Z
Often these data structures aren't meant to be practical. Practice and theory differ. If you want a good practical data structure, don't read theoretical papers.
Yuval Filmus
CC BY-SA 3.0
2012-09-29T02:40:31.417Z
What about this [comment](http://mybiasedcoin.blogspot.com/2008/08/on-simulations.html?showComment=1218345900000#c6378973131067956911) ?
jplot
<ds.data-structures>
On aB-trees and its practical implementation
jplot
# On aB-trees and its practical implementation

(Asked by: username_0 on 2012-09-28)

I'm reading the paper *Succincter* by M. Patrascu ([link](http://people.csail.mit.edu/mip/papers/succinct/succinct.pdf)).

It introduces on page 7 the *aB-tree*. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the leaves. Every node is augmented with a value from some alphabet. The value of a leaf is a function of its array element, and the value of an internal node is a function A of the values of its B children, and the size of the subtree.

The query algorithm examines the values of the root’s children, decides which child to recurse to, examines all values of that node’s children, recurses to one of them, etc. When a leaf is examined, the algorithm outputs the query answer. We assume the query algorithm spends constant time per node, if all values of the children are given packed in a word.

The part I'm having difficulties with is the following: *The queries can be solved in constant time per node if the values of all children are given packed in a word. This uses very standard ideas from word-level parallelism that we omit.*

Could somebody please point how does word-level parallelism achieve this ?

Also, is there a practical implementation of this structure (and its application to succinct rank/select bitvectors) ?

Thanks in advance.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: Often these data structures aren't meant to be practical. Practice and theory differ. If you want a good practical data structure, don't read theoretical papers.  
> **username_0**: What about this [comment](http://mybiasedcoin.blogspot.com/2008/08/on-simulations.html?showComment=1218345900000#c6378973131067956911) ?  

---

## 0 answers

