Fusion tree

When operating on a collection of n key–value pairs, it uses O(n) space and performs searches in O(logw n) time, which is asymptotically faster than a traditional self-balancing binary search tree, and also better than the van Emde Boas tree for large values of w. It achieves this speed by using certain constant-time operations that can be done on a machine word.

A dynamic version of fusion trees using hash tables was proposed in 1996[3] which matched the original structure's O(logw n) runtime in expectation.

Finally, it was shown that dynamic fusion trees can perform each operation in O(logw n) time deterministically.

The partial result of most significant bit locator in constant time has also helped further research.

Fusion trees utilize word-level parallelism to be efficient, performing computation on several small integers, stored in a single machine word, simultaneously to reduce the number of total operations.

To achieve the desired runtimes for updates and queries, the fusion tree must be able to search a node containing up to w1/5 keys in constant time.

This is done by compressing ("sketching") the keys so that all can fit into one machine word, which in turn allows comparisons to be done in parallel.

So, a series of computations involving sketching, parallel comparison and most significant bit index locator, help reach the required solution.

Each key x may be thought of as a path in the full binary tree of height w starting at the root and ending at the leaf corresponding to x.

With only standard word operations, such as those of the C programming language, it is difficult to directly compute the perfect sketch of a key in constant time.

For the approximate sketch to work, the following three properties must hold: An inductive argument shows how the mi can be constructed.

If t is also a bit string, st denotes the concatenation of t to s. The node sketch makes it possible to search the keys for any b-bit integer y.

Let z = (0y)k, which can be computed in constant time (multiply y by the constant (0b1)k), to make it as long as the node sketch such that each word in the node sketch can be compared with the query integer y in one operation, demonstrating word-level parallelism.

The length longest common prefix between two w-bit integers a and b can be computed in constant time by finding the most significant bit of the bitwise XOR between a and b.

This chain size is small enough that a fusion tree can handle searches and updates within it in constant time per operation.

[6] The computational model for the Fusion Tree algorithm is a Word RAM with a specific instruction set, including arithmetic instructions - addition, subtraction and multiplication (all performed modulo 2w) and Boolean operations - bitwise AND, NOT etc.