Sorry, you need to enable JavaScript to visit this website.

On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond

Citation Author(s):
Lloyd Allison, Arun S. Konagurthu, Daniel F. Schmidt
Submitted by:
Arun Konagurthu
Last updated:
24 February 2021 - 4:14pm
Document Type:
Demo
Document Year:
2021
Event:
Presenters:
Lloyd Allison
Paper Code:
DCC21 Paper ID: 139
Categories:
 
up
1 user has voted: Arun Konagurthu

Comments

Slides and presentation talk video for the paper:
On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond
to be presented by Lloyd Allison

Your results are very interesting!
Now having even more universal codes at hand, I think it would be time to have a comprehensive list of integer codes with a recommendation which code fits best to which integer domain (in case that a use case is restricted to dealing with integers in a certain domain).

I would like to ask about the $O(\lg^2 n)$ time bound on slide 16 whether there is some detailed explanation available.
Do you know whether there exists a repetitive subtree structure in the constructed WTC trees such that you can decompose a path traversal into a traversal in subtrees and glue the computed bits together? (For instance with the clustering described in "The Tree Inclusion Problem: In Linear Space and Faster" by Philip Bille and Inge Li Gørtz)?
If so, you could build lookup tables for the small subtrees, and maybe achieve $O(\lg n)$ time?
I am also wondering whether bit-parallel techniques could be applied to compute the WTC codes for multiple integers in parallel as long as they fit into a machine word.