This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details.(December 2017) (Learn how and when to remove this message)
In computer science, a fusion tree is a type of tree data structure that implements an associative array 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 key–value pairs, it uses O(n) space and performs searches in O(logwn) 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. Fusion trees were invented in 1990 by Michael Fredman and Dan Willard.[1]
Several advances have been made since Fredman and Willard's original 1990 paper. In 1999[2] 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 AC0, a model of circuit complexity 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 hash tables was proposed in 1996[3] which matched the original structure's O(logwn) runtime in expectation. Another dynamic version using exponential tree was proposed in 2007[4] which yields worst-case runtimes of O(logwn + log log n) per operation. Finally, it was shown that dynamic fusion trees can perform each operation in O(logwn) time deterministically.[5]
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 parallelism to be efficient, performing computation on several small integers, stored in a single machine word, simultaneously to reduce the number of total operations.
^Fredman, M. L.; Willard, D. E. (1990), "BLASTING Through the Information Theoretic Barrier with FUSION TREES", Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC '90), New York, NY, USA: ACM, pp. 1–7, doi:10.1145/100216.100217, ISBN 0-89791-361-2, S2CID 16367160.
^Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Fusion trees can be implemented with AC0 instructions only", Theoretical Computer Science, 215 (1–2): 337–344, doi:10.1016/S0304-3975(98)00172-8, MR 1678804.
^Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Algorithms — ESA '96, Lecture Notes in Computer Science, vol. 1136, Berlin: Springer-Verlag, pp. 121–137, doi:10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, MR 1469229.
^Andersson, Arne; Thorup, Mikkel (2007), "Dynamic ordered sets with exponential search trees", Journal of the ACM, 54 (3): A13, arXiv:cs/0210006, doi:10.1145/1236457.1236460, MR 2314255, S2CID 8175703.
^Patrascu, Mihai; Thorup, Mikkel (2014). "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search". 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. p. 166-175. arXiv:1408.3045. doi:10.1109/FOCS.2014.26. ISBN 978-1-4799-6517-5. S2CID 8943659.
In computer science, a fusiontree is a type of tree data structure that implements an associative array on w-bit integers on a finite universe, where...
WAVL tree Weight-balanced tree Zip tree B-tree B+ tree B*-tree Dancing tree 2–3 tree 2–3–4 tree Queap Fusiontree Bx-tree Heap Min-max heap Binary heap...
"Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusiontree". SIAM Journal on Computing. 29 (3): 1030–1049...
van Emde Boas tree, pp. 531–560. Rex, A. "Determining the space complexity of van Emde Boas trees". Retrieved 2011-05-27. "FusionTree". OpenGenus IQ:...
priority value. The space can be reduced significantly with hashing. The Fusiontree by Fredman and Willard implements the minimum operation in O(1) time...
individual tree "leaves" properly; for example, the separation ((A,B),(C,D)) at a branch tip versus ((A,C),(B,D)) may be unresolved. Treefusion swaps these...
solved the problem using fusiontrees in O ( log w n ) {\displaystyle O(\log _{w}n)} time. Using exponential search trees, a query can be performed...
to solve the problem include balanced binary search trees, van Emde Boas trees, and fusiontrees. In the static predecessor problem, the set of elements...
The album continued the fusion of electronic music and rock and also featured guest appearances from two future Porcupine Tree members, Richard Barbieri...
{\displaystyle S(d)} . A Fusiontree can be used as this data structure. The exponential tree can be searched in the same way as a normal search tree. In each node...
Afro fusion (also spelled afrofusion or afro-fusion) is a dance and musical style that emerged between the 1970s and 2000s. In the same way as the dance...
{\displaystyle O(n{\tfrac {\log n}{\log \log n}})} by an algorithm using their fusiontree data structure as a priority queue. In a follow-up to this work, Fredman...
easily into the world fusion category, the suffix "fusion" in the term world fusion should not be assumed to mean jazz fusion. Western jazz combined...
K and w. The first algorithm of this type was Fredman and Willard's fusiontree sorting algorithm, which runs in time O(n log n / log log n); this is...
known by his stage name Tree or MC Tree G. He is responsible for cultivating his own unique sound called "Soul Trap", the fusion of the soul music of the...
algorithms WHP. Treap: a randomized binary search tree. Its height is logarithmic WHP. Fusiontree is a related data structure. Online codes: randomized...
was published on 24 November 2006, based on the following three concepts: Fusion of neofuturistic design and the traditional beauty of Japan Catalyst for...
differs in the form of leaves and fusion of the outer floral parts. It grows to heights of more than two meters. Tree tobacco is native to South America...
has no biological relation to the Adkisson family. On two episodes of MLW Fusion, Tom Lawlor, who was involved in a feud with the Von Erichs after turning...
Priority queues are frequently implemented using heaps. A (max) heap is a tree-based data structure which satisfies the heap property: for any given node...
Fusion of powers is a feature of some parliamentary forms of government where different branches of government are intermingled or fused, typically the...
Global Information