The two families
| Structure | Reference | Query | Update | Space |
|---|
| van Emde Boas tree | van Emde Boas, 1970s 19:36 | O(log w) | O(log w), dynamic 20:23 | Θ(u) as published; Θ(n) with randomization 20:51, 21:16 |
| y-fast trie | Willard, IPL 1983 22:03 | same bounds as vEB 21:16 | dynamic | linear |
| Fusion tree | Fredman & Willard, JCSS '93 22:48 | O(log_w n) | static in class; dynamic exists 22:48 | linear |
Θ(u) space is unacceptable in practice: on a 64-bit machine u = 2^64 21:16.- The
u → linear space fix turns out to be simple (see topic 6); the original vEB paper did not achieve linear space 22:03.
Fusion trees already beat BSTs
log_w n = log n / log w, and since w ≥ log n, this is never more than log n / log log n 23:35.
Combining the two
- The machine's
w is known at coding time, so pick the better of fusion trees and vEB/y-fast tries, achieving min(log w, log_w n) 23:58.
- The worst case of that min is where the two are equal:
log w = log n / log w, i.e. log n = (log w)^2, so the bound is always at most √(log n) 24:23.
graph LR
A["word size w"] --> B["w small<br/>(near log n)"]
A --> C["w large"]
B --> D["van Emde Boas / y-fast<br/>O(log w)"]
C --> E["Fusion tree<br/>O(log_w n)"]
D --> F["pick the better:<br/>min(log w, log_w n) ≤ √(log n)"]
E --> F
Sorting consequences in the word-RAM
- Dynamic fusion trees ⇒
O(n √(log n)) sorting 25:01.
- Not covered in class, but better is known:
O(n log log n) deterministic — Han & Stock, 2002 26:18.O(n √(log log n)) expected time, randomized — Han & Thorup, FOCS 2002, about five months later 26:18, 27:03.
- Open question: whether linear-time sorting is possible in this model — nothing rules it out
27:03.
Why the static fusion tree isn't enough for sorting
- A student asks why the dynamic version matters. Answer: pre-processing time. Building the static fusion tree costs polynomial time, which ruins the sorting application; a dynamic structure starts empty, so that cost never appears
25:40, 25:55.
These bounds are optimal
- A later paper proves a matching lower bound: you can never beat the min of van Emde Boas (or a slightly tweaked version) and fusion trees. So both are optimal for linear or nearly linear space predecessor structures
1:27:49.
Audience calibration
- Only one student had seen vEB trees, and none had seen fusion trees
30:01, 30:32.