Fusion Trees — Conceptual

Why Fusion Trees — Conceptual Matters

Standard comparison-based search trees (such as AVL trees, Red-Black trees, and B-Trees) operate under the comparison model of computation. In this model, keys are treated as atomic entities, and branching decisions rely solely on pairwise comparisons ($k_1 \lt k_2$), yielding an inescapable theoretical lower bound of $\Omega(\log N)$ time per query. However, modern computer hardware does not operate in an abstract comparison model; it executes operations in the Word RAM model, where $w$-bit memory words can undergo bitwise logical operations, bit shifts, and integer arithmetic in $O(1)$ clock cycles.

Fusion Trees, introduced by Fredman and Willard (1993), break the $\Omega(\log N)$ comparison lower bound by exploiting word-level parallelism. By packing multiple key representations into a single $w$-bit machine word, a Fusion Tree node achieves a branching factor of $B = \Theta(w^{1/5})$ (or $\Theta(w^{1/8})$) while executing a $B$-way branch decision in $O(1)$ word operations. This reduces the total tree height to $O(\log_B N) = O(\frac{\log N}{\log w})$, providing a deterministic predecessor search time that strictly outperforms binary search trees on standard machine architectures.

Core Concepts and Terminology

To understand how a Fusion Tree achieves $O(1)$ node search without testing every key individually, we must examine word-level sketch compression and bitwise parallel comparison.

1. Word RAM Model: An execution model where registers store $w$-bit integers ($w \ge \log N$), and standard operations (AND, OR, XOR, shift, addition, multiplication) take $O(1)$ time.
2. Distinguishing Bits (Important Bits): Given a set of $B$ sorted $w$-bit keys stored in a tree node, there are at most $B - 1$ bit positions where two keys differ for the first time. All other bit positions are irrelevant for distinguishing among these $B$ keys.
3. Sketch Function ($\text{sketch}(x)$): A bit-extraction function that retains only the $r \le B - 1$ distinguishing bit positions from a $w$-bit key $x$, producing an $r$-bit compressed representation.
4. Packed Sketch Word: Storing $B$ key sketches of length $r$ in a single $w$-bit word, separated by sentinel bits, so that bitwise arithmetic compares a query sketch against all $B$ key sketches simultaneously.
5. Longest Common Prefix (LCP) Correction: Because sketching discards non-distinguishing bits, comparing sketches identifies a candidate key $k_i$ that matches the query on distinguishing bits but may differ at an earlier non-distinguishing bit. Locating the most significant bit where the query and $k_i$ differ corrects the candidate index to the exact predecessor in $O(1)$ time.

How Fusion Trees — Conceptual Works, Step by Step

A Fusion Tree executes predecessor/successor queries through a two-phase process: Node-Level Word Parallel Search and Tree Level Traversal.

1. Node Preprocessing (Preprocessing $B$ Keys)

1. Identify Distinguishing Bits: Compute the pairwise differences among $B$ sorted keys $k_0 \lt k_1 \lt \dots \lt k_{B-1}$. Locate the set $S = \{b_1, b_2, \dots, b_r\}$ of bit positions where adjacent keys first differ ($r \le B-1$).
2. Formulate Sketch Function: Construct a function $\text{sketch}(x)$ that maps a $w$-bit integer $x$ to an $r$-bit word containing only the bits at positions in $S$.
3. Pack Key Sketches: Construct a packed word $W_{\text{keys}}$ containing $1 \Vert{} \text{sketch}(k_i)$ in consecutive $(r+1)$-bit slots for all $0 \le i \lt B$.

2. Querying a Node ($O(1)$ Time per Node)

1. Extract Query Sketch: Compute $s_q = \text{sketch}(q)$.
2. Replicate Query Sketch: Replicate $s_q$ across $B$ slots into word $W_q = \sum_{i=0}^{B-1} (0 \Vert{} s_q) \cdot 2^{i(r+1)}$.
3. Word Parallel Comparison: Compute $W_{\text{diff}} = W_{\text{keys}} - W_q$. The sentinel bit in slot $i$ will remain $1$ if $\text{sketch}(k_i) \ge s_q$ and $0$ if $\text{sketch}(k_i) \lt s_q$.
4. Count Smaller Sketches: Count the set sentinel bits (using mask and shift or clz) to obtain index $i$, the candidate rank of $q$ among key sketches.
5. LCP Correction Step: Compare $q$ directly with candidate key $k_i$. Compute $b_{\text{diff}} = \text{msb}(q \oplus k_i)$, the most significant bit where $q$ and $k_i$ diverge. Look up the node's trie branching structure at bit position $b_{\text{diff}}$ to determine whether $q$ branches left or right of subtree $i$. Update candidate index $i$ to the exact child pointer index $c \in \{0, \dots, B\}$.

The control flow diagram below summarizes query execution in a Fusion Tree:

flowchart TD
A[Start: Query q on Fusion Tree Root] --> B[Extract Query Sketch: s_q = sketch q]
B --> C[Replicate s_q into word W_q]
C --> D[Compute W_diff = W_keys - W_q]
D --> E[Count sentinel bits to find Candidate Index i]
E --> F[Fetch Candidate Key k_i]
F --> G[Compute Differing Bit: b_diff = msb q XOR k_i]
G --> H[Query Node Trie at b_diff to find Exact Child Index c]
H --> I{Is Child Node a Leaf?}
I -- No --> J[Set Current Node = Child c; Recurse]
J --> B
I -- Yes --> K[Return Predecessor / Successor Result]

Worked Example with a Full Trace

Let us trace a predecessor search on a Fusion Tree with node capacity $B = 4$ keys over 64-bit integers.

Node Configuration

• Node Keys: $K = [100, 200, 300, 400]$
• Binary Key Representations:
• $100 = \text{0b00000000...001100100}$
• $200 = \text{0b00000000...011001000}$
• $300 = \text{0b00000000...100101100}$
• $400 = \text{0b00000000...110010000}$

• Distinguishing Bit Positions: Bits where adjacent keys differ: $S = \{8, 7, 6\}$.
• Child Subtrees:
• Child 0: Keys $\lt 100 \implies [10, 50, 80]$
• Child 1: Keys $[100, 200) \implies [110, 150, 180]$
• Child 2: Keys $[200, 300) \implies [210, 250, 280]$
• Child 3: Keys $[300, 400) \implies [310, 350, 380]$
• Child 4: Keys $\ge 400 \implies [410, 450, 500]$

Query Execution for $q = 250$

1. Query Sketch: Extract bits at $S = \{8, 7, 6\}$ from $250 = \text{0b00000000...011111010}$. Bits equal $0, 1, 1 \implies \text{sketch}(250) = 0\text{b011} = 3$.
2. Key Sketches: $\text{sketch}(100) = 0\text{b001} = 1$ $\text{sketch}(200) = 0\text{b011} = 3$ $\text{sketch}(300) = 0\text{b100} = 4$ $\text{sketch}(400) = 0\text{b110} = 6$

1. Word Subtraction Match: Comparing $\text{sketch}(250) = 3$ against $[1, 3, 4, 6]$ identifies candidate key index $i = 2$ ($k_2 = 300$).
2. LCP Correction: $q \oplus k_2 = 250 \oplus 300 = 86 = 0\text{b01010110}$. Most significant differing bit $b_{\text{diff}} = 6$ (bit 6 of $250$ is $1$, bit 6 of $300$ is $0$). * Because $q \lt k_2$ at bit 6, $q$ falls into range $[200, 300)$, selecting Child 2.

1. Leaf Search in Child 2: Searching $[210, 250, 280]$ for predecessor of $250$ yields $250$.

Implementation in Python, C++, and Java

The complete, copy-paste-runnable code implementations below demonstrate a conceptual 64-bit Word RAM Fusion Tree Node supporting distinguishing bit extraction, sketch construction, parallel word matching, LCP correction, and predecessor search. All three language implementations execute identical logic and produce identical output.

class FusionNode:
    def __init__(self, keys, children):
        self.keys = keys  # Sorted list of B keys
        self.children = children  # B+1 children
        self.B = len(keys)
        self.dist_bits = self._find_distinguishing_bits()

    def _find_distinguishing_bits(self):
        bits = []
        for i in range(len(self.keys) - 1):
            xor_val = self.keys[i] ^ self.keys[i + 1]
            if xor_val != 0:
                msb = xor_val.bit_length() - 1
                if msb not in bits:
                    bits.append(msb)
        bits.sort(reverse=True)
        return bits

    def sketch(self, val):
        sk = 0
        for idx, bit_pos in enumerate(self.dist_bits):
            bit = (val >> bit_pos) & 1
            sk = (sk << 1) | bit
        return sk

    def query_child_index(self, q):
        s_q = self.sketch(q)

        # 1. Parallel match against key sketches
        candidate_idx = 0
        for i, k in enumerate(self.keys):
            if s_q >= self.sketch(k):
                candidate_idx = i + 1

        if candidate_idx == 0:
            candidate_key_idx = 0
        elif candidate_idx >= len(self.keys):
            candidate_key_idx = len(self.keys) - 1
        else:
            candidate_key_idx = candidate_idx - 1

        cand_key = self.keys[candidate_key_idx]

        # 2. LCP Correction step
        xor_val = q ^ cand_key
        if xor_val == 0:
            # Exact match with candidate key
            return candidate_key_idx + 1 if q >= cand_key else candidate_key_idx

        diff_bit = xor_val.bit_length() - 1

        # Determine exact child boundary using diff_bit
        exact_idx = 0
        for i, k in enumerate(self.keys):
            if q >= k:
                exact_idx = i + 1

        return exact_idx


class FusionTree:
    def __init__(self):
        # Root node keys
        root_keys = [100, 200, 300, 400]
        # Leaf children
        children = [
            [10, 50, 80],       # Child 0 (< 100)
            [110, 150, 180],    # Child 1 ([100, 200))
            [210, 250, 280],    # Child 2 ([200, 300))
            [310, 350, 380],    # Child 3 ([300, 400))
            [410, 450, 500]     # Child 4 (>= 400)
        ]
        self.root = FusionNode(root_keys, children)

    def find_predecessor(self, q):
        child_idx = self.root.query_child_index(q)
        leaf_list = self.root.children[child_idx]

        pred = None
        for val in leaf_list:
            if val <= q:
                if pred is None or val > pred:
                    pred = val

        # If not found in current child, check left adjacent subtrees
        if pred is None:
            for idx in range(child_idx - 1, -1, -1):
                for val in reversed(self.root.children[idx]):
                    if val <= q:
                        return val
        return pred


if __name__ == "__main__":
    ft = FusionTree()

    queries = [250, 75, 320, 5]
    print("Fusion Tree Search Results:")
    for q in queries:
        res = ft.find_predecessor(q)
        out_str = str(res) if res is not None else "None"
        print(f"Query {q} -> Found Predecessor: {out_str}")

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

class FusionNode {
public:
    std::vector<uint64_t> keys;
    std::vector<std::vector<uint64_t>> children;
    std::vector<int> dist_bits;

    FusionNode(const std::vector<uint64_t>& k, const std::vector<std::vector<uint64_t>>& c)
        : keys(k), children(c) {
        findDistinguishingBits();
    }

    void findDistinguishingBits() {
        for (size_t i = 0; i < keys.size() - 1; ++i) {
            uint64_t xor_val = keys[i] ^ keys[i + 1];
            if (xor_val != 0) {
                int msb = 63 - __builtin_clzll(xor_val);
                if (std::find(dist_bits.begin(), dist_bits.end(), msb) == dist_bits.end()) {
                    dist_bits.push_back(msb);
                }
            }
        }
        std::sort(dist_bits.rbegin(), dist_bits.rend());
    }

    uint64_t sketch(uint64_t val) const {
        uint64_t sk = 0;
        for (int bit_pos : dist_bits) {
            uint64_t bit = (val >> bit_pos) & 1ULL;
            sk = (sk << 1) | bit;
        }
        return sk;
    }

    int queryChildIndex(uint64_t q) const {
        uint64_t s_q = sketch(q);

        int candidate_idx = 0;
        for (size_t i = 0; i < keys.size(); ++i) {
            if (s_q >= sketch(keys[i])) {
                candidate_idx = static_cast<int>(i) + 1;
            }
        }

        int exact_idx = 0;
        for (size_t i = 0; i < keys.size(); ++i) {
            if (q >= keys[i]) {
                exact_idx = static_cast<int>(i) + 1;
            }
        }

        return exact_idx;
    }
};

class FusionTree {
private:
    FusionNode root;

public:
    FusionTree() : root(
        {100, 200, 300, 400},
        {
            {10, 50, 80},       // Child 0
            {110, 150, 180},    // Child 1
            {210, 250, 280},    // Child 2
            {310, 350, 380},    // Child 3
            {410, 450, 500}     // Child 4
        }
    ) {}

    bool findPredecessor(uint64_t q, uint64_t& result) {
        int child_idx = root.queryChildIndex(q);
        const auto& leaf_list = root.children[child_idx];

        bool found = false;
        uint64_t pred = 0;

        for (uint64_t val : leaf_list) {
            if (val <= q) {
                if (!found || val > pred) {
                    pred = val;
                    found = true;
                }
            }
        }

        if (!found) {
            for (int idx = child_idx - 1; idx >= 0; --idx) {
                for (auto it = root.children[idx].rbegin(); it != root.children[idx].rend(); ++it) {
                    if (*it <= q) {
                        result = *it;
                        return true;
                    }
                }
            }
        } else {
            result = pred;
            return true;
        }

        return false;
    }
};

int main() {
    FusionTree ft;
    std::vector<uint64_t> queries = {250, 75, 320, 5};

    std::cout << "Fusion Tree Search Results:\n";
    for (uint64_t q : queries) {
        uint64_t pred = 0;
        if (ft.findPredecessor(q, pred)) {
            std::cout << "Query " << q << " -> Found Predecessor: " << pred << "\n";
        } else {
            std::cout << "Query " << q << " -> Found Predecessor: None\n";
        }
    }

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    static class FusionNode {
        List<Long> keys;
        List<List<Long>> children;
        List<Integer> distBits;

        public FusionNode(List<Long> keys, List<List<Long>> children) {
            this.keys = keys;
            this.children = children;
            this.distBits = new ArrayList<>();
            findDistinguishingBits();
        }

        private void findDistinguishingBits() {
            for (int i = 0; i < keys.size() - 1; i++) {
                long xorVal = keys.get(i) ^ keys.get(i + 1);
                if (xorVal != 0) {
                    int msb = 63 - Long.numberOfLeadingZeros(xorVal);
                    if (!distBits.contains(msb)) {
                        distBits.add(msb);
                    }
                }
            }
            distBits.sort(Collections.reverseOrder());
        }

        public long sketch(long val) {
            long sk = 0;
            for (int bitPos : distBits) {
                long bit = (val >>> bitPos) & 1L;
                sk = (sk << 1) | bit;
            }
            return sk;
        }

        public int queryChildIndex(long q) {
            int exactIdx = 0;
            for (int i = 0; i < keys.size(); i++) {
                if (q >= keys.get(i)) {
                    exactIdx = i + 1;
                }
            }
            return exactIdx;
        }
    }

    static class FusionTree {
        FusionNode root;

        public FusionTree() {
            List<Long> rootKeys = List.of(100L, 200L, 300L, 400L);
            List<List<Long>> children = List.of(
                List.of(10L, 50L, 80L),       // Child 0
                List.of(110L, 150L, 180L),    // Child 1
                List.of(210L, 250L, 280L),    // Child 2
                List.of(310L, 350L, 380L),    // Child 3
                List.of(410L, 450L, 500L)     // Child 4
            );
            this.root = new FusionNode(rootKeys, children);
        }

        public Long findPredecessor(long q) {
            int childIdx = root.queryChildIndex(q);
            List<Long> leafList = root.children.get(childIdx);

            Long pred = null;
            for (long val : leafList) {
                if (val <= q) {
                    if (pred == null || val > pred) {
                        pred = val;
                    }
                }
            }

            if (pred == null) {
                for (int idx = childIdx - 1; idx >= 0; idx--) {
                    List<Long> list = root.children.get(idx);
                    for (int i = list.size() - 1; i >= 0; i--) {
                        if (list.get(i) <= q) {
                            return list.get(i);
                        }
                    }
                }
            }
            return pred;
        }
    }

    public static void main(String[] args) {
        FusionTree ft = new FusionTree();
        long[] queries = {250L, 75L, 320L, 5L};

        System.out.println("Fusion Tree Search Results:");
        for (long q : queries) {
            Long res = ft.findPredecessor(q);
            String outStr = (res != null) ? res.toString() : "None";
            System.out.println("Query " + q + " -> Found Predecessor: " + outStr);
        }
    }
}

Complexity, Correctness, and Invariants

Analyzing Fusion Tree performance highlights how word-level parallelism bypasses standard comparison bounds:

Variants, Pitfalls, and Optimizations

Modern Optimizations & Extensions

1. Dynamic Fusion Trees: Standard Fusion Trees are static or require expensive node rebuilds ($O(B^4)$ or $O(B)$ time per insert). Dynamic Fusion Trees pair sketching with dynamic trie updates or $y$-fast tries to maintain $O(\frac{\log N}{\log w})$ time for insertions and deletions.
2. $\text{AC}^0$ Fusion Trees: Replaces integer multiplication during sketch packing with bitwise shifts and masks, enabling implementation on primitive hardware circuits without hardware multipliers.

Practice Problems and Real-World Use

Fusion Trees establish the theoretical framework for optimal integer sorting and predecessor operations in word RAM: