[+] Integer: fusion trees: sketching, parallel comparison, most significant set bit  
This lecture describes a tourdeforce in integer data structures, called fusion trees (so named because they were published a year after the 1989 coldfusion "scandal", and were perhaps just as surprisingthough more correct). Fusion trees solve predecessor and successor among n wbit integers in O(log_{w} n) time per operation on the word RAM. The basic idea is to build a Btree with branching factor w^{ε}. The tricky part is to build a w^{ε}size node supporting constanttime predecessor/successor. We'll see three major techniques for doing so. First, sketching reduces the w^{1+ε} bits in a node down to w “essential” bits, by reducing each word down to w^{1−ε} “essential” bits. The impressive part is sketching a word in constant time using a single multiplication. Second, parallel comparison lets us compare all of these sketches with a single query in constant time. Third, we'll see how to find the most significant set bit of a wbit word in constant time on a word RAM, by using most of the fusion techniques again; this problem has tons of applications beyond fusion trees as well. (As a result, most significant set bit is a builtin instruction on most architectures; see e.g. StackOverflow.)  
Lecture notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/8 • [previous page] • [next page] • [PDF] 

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.