Van Emde Boas trees only exploited that keys are also memory addresses, which is how they beat the comparison-based lower bound (8:59). Fusion trees go "way more overboard" with Word-RAM power — expect heavy bit tricks (9:52).
The four ingredients
- Multiplication — exploit that multiplying word-sized numbers is
O(1). A later variant of fusion trees avoids multiplication entirely, but is not presented here (9:52,10:23). - Sketch compression — the k keys cannot all fit in a word, so they must be compressed (
10:23). - Word-level parallelism — compare the query against all keys simultaneously with a constant number of word operations (
10:52). - Most significant set bit (MSB) in
O(1)— a subroutine needed by the others (11:20).
MSB warm-up: how fast can you find it?
| Approach | Time | How |
|---|---|---|
| Naive loop | O(w) | loop from bit w-1 down to 0, bitwise-AND a mask, test for 0 (11:48, 12:02) |
| Binary search | O(log w) | find the largest i with x > 2^i; 2^i is a single left shift, so each iteration is O(1) (12:19) |
| Word-RAM trick | O(1) | proved at the end of the lecture (12:36) |