A fusion tree is a type of tree data structure that implements an associative array on w-bit integers. 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 actually better than the van Emde Boas tree when w is large. It achieves this speed by exploiting certain constant-time operations that can be done on a machine word. Fusion trees were invented in 1990 by Michael Fredman and Dan Willard.
Several advances have been made since Fredman and Willard's original 1990 paper. In 1999 it was shown how to implement fusion trees under the AC0 model, in which multiplication no longer takes constant time. A dynamic version of fusion trees using Hash tables was proposed in 1996 which matched the O(logw n) runtime in expectation. Another dynamic version using Exponential tree was proposed in 2007 which yields worst-case runtimes of O(logw n + log log u) per operation, where u is the size of the largest key. It remains open whether dynamic fusion trees can achieve O(logw n) per operation with high probability.
Read more about Fusion Tree: How It Works, Sketching, Approximating The Sketch, Parallel Comparison, Desketching
Famous quotes containing the words fusion and/or tree:
“Sadism and masochism, in Freud’s final formulation, are fusions of Eros and the destructive instincts. Sadism represents a fusion of the erotic instincts and the destructive instincts directed outwards, in which the destructiveness has the character of aggressiveness. Masochism represents the fusion of the erotic instincts and the destructive instincts turned against oneself, the aim of the latter being self-destruction.”
—Patrick Mullahy (b. 1912)
“Is not disease the rule of existence? There is not a lily pad floating on the river but has been riddled by insects. Almost every shrub and tree has its gall, oftentimes esteemed its chief ornament and hardly to be distinguished from the fruit. If misery loves company, misery has company enough. Now, at midsummer, find me a perfect leaf or fruit.”
—Henry David Thoreau (1817–1862)