Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Fusion_tree> ?p ?o. }
Showing items 1 to 25 of
25
with 100 items per page.
- Fusion_tree abstract "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.".
- Fusion_tree thumbnail FusionTreeSketch.gif?width=300.
- Fusion_tree wikiPageExternalLink lec13.pdf.
- Fusion_tree wikiPageExternalLink lec12.pdf.
- Fusion_tree wikiPageExternalLink lecture4.pdf.
- Fusion_tree wikiPageExternalLink lecture5.pdf.
- Fusion_tree wikiPageID "1051942".
- Fusion_tree wikiPageRevisionID "585893722".
- Fusion_tree hasPhotoCollection Fusion_tree.
- Fusion_tree subject Category:Associative_arrays.
- Fusion_tree subject Category:Trees_(data_structures).
- Fusion_tree type Abstraction100002137.
- Fusion_tree type Arrangement107938773.
- Fusion_tree type Array107939382.
- Fusion_tree type AssociativeArrays.
- Fusion_tree type Group100031264.
- Fusion_tree comment "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_tree label "Fusion tree".
- Fusion_tree sameAs m.041sgy.
- Fusion_tree sameAs Q5510283.
- Fusion_tree sameAs Q5510283.
- Fusion_tree sameAs Fusion_tree.
- Fusion_tree wasDerivedFrom Fusion_tree?oldid=585893722.
- Fusion_tree depiction FusionTreeSketch.gif.
- Fusion_tree isPrimaryTopicOf Fusion_tree.
