I'm reading the paper Succincter by M. Patrascu (link).

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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 29 '12 at 2:09
  • $\begingroup$ What about this comment ? $\endgroup$ – jplot Sep 29 '12 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.