Fusion tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a fusion tree is a type of <a href="/facts/Tree_data_structure/RcXz9noF">tree data structure</a> that implements an <a href="/facts/Associative_array/IFGd2xcP">associative array</a> on w-bit integers on a finite universe, where each of the input integers has size less than 2w and is non-negative. When operating on a collection of n <a href="/facts/Attribute%E2%80%93value_pair/buweLY96">key–value pairs</a>, it uses O(n) space and performs searches in O(logw n) time, which is asymptotically faster than a traditional <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search tree</a>, and also better than the <a href="/facts/Van_Emde_Boas_tree/X2L5WtU0">van Emde Boas tree</a> for large values of w. It achieves this speed by using certain constant-time operations that can be done on a <a href="/facts/Machine_word/2e5umRaj">machine word</a>. Fusion trees were invented in 1990 by <a href="/facts/Michael_Fredman/KynAwavf">Michael Fredman</a> and <a href="/facts/Dan_Willard/EFn9KKzE">Dan Willard</a>.
Several advances have been made since Fredman and Willard's original 1990 paper. In 1999 it was shown how to implement fusion trees under a model of computation in which all of the underlying operations of the algorithm belong to <a href="/facts/AC0/UGJ79CeY">AC0</a>, a model of <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a> that allows addition and bitwise Boolean operations but does not allow the multiplication operations used in the original fusion tree algorithm. A dynamic version of fusion trees using <a href="/facts/Hash_tables/Ht4ptDPF">hash tables</a> was proposed in 1996 which matched the original structure's O(logw n) runtime in expectation. Another dynamic version using <a href="/facts/Exponential_tree/IlXLv1Fn">exponential tree</a> was proposed in 2007 which yields worst-case runtimes of O(logw n + log log n) per operation. Finally, it was shown that dynamic fusion trees can perform each operation in O(logw n) time deterministically.
This data structure implements add key, remove key, search key, and predecessor (next smaller value) and successor (next larger value) search operations for a given key. The partial result of most significant bit locator in constant time has also helped further research. Fusion trees utilize word-level <a href="/facts/Parallelism_(computing)/nQzcpzQt">parallelism</a> to be efficient, performing computation on several small integers, stored in a single machine word, simultaneously to reduce the number of total operations.

Fusion tree open-in-new

Fusion tree