Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Fusion_tree> ?p ?o }
Showing triples 1 to 54 of
54
with 100 triples per page.
- Fusion_tree abstract "In computer science, a fusion tree is a type of tree data structure that implements an associative array on w-bit integers. 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 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 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 disallows the multiplication operations used in the original fusion tree algorithm. A dynamic version of fusion trees using hash tables was proposed in 1996 which matched the original structure's 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 wikiPageLength "14193".
- Fusion_tree wikiPageOutDegree "23".
- Fusion_tree wikiPageRevisionID "700670460".
- Fusion_tree wikiPageWikiLink AC0.
- Fusion_tree wikiPageWikiLink Associative_array.
- Fusion_tree wikiPageWikiLink Attribute–value_pair.
- Fusion_tree wikiPageWikiLink B-tree.
- Fusion_tree wikiPageWikiLink Bitwise_operation.
- Fusion_tree wikiPageWikiLink C_(programming_language).
- Fusion_tree wikiPageWikiLink Category:Associative_arrays.
- Fusion_tree wikiPageWikiLink Category:Trees_(data_structures).
- Fusion_tree wikiPageWikiLink Circuit_complexity.
- Fusion_tree wikiPageWikiLink Computer_science.
- Fusion_tree wikiPageWikiLink Dan_Willard.
- Fusion_tree wikiPageWikiLink Exponential_tree.
- Fusion_tree wikiPageWikiLink Hash_table.
- Fusion_tree wikiPageWikiLink Michael_Fredman.
- Fusion_tree wikiPageWikiLink Most_significant_bit.
- Fusion_tree wikiPageWikiLink Self-balancing_binary_search_tree.
- Fusion_tree wikiPageWikiLink Time_complexity.
- Fusion_tree wikiPageWikiLink Tree_(data_structure).
- Fusion_tree wikiPageWikiLink Van_Emde_Boas_tree.
- Fusion_tree wikiPageWikiLink Word_(computer_architecture).
- Fusion_tree wikiPageWikiLink File:FusionTreeSketch.gif.
- Fusion_tree wikiPageWikiLinkText "Fusion tree".
- Fusion_tree wikiPageWikiLinkText "fusion tree".
- Fusion_tree wikiPageUsesTemplate Template:CS-Trees.
- Fusion_tree wikiPageUsesTemplate Template:Math.
- Fusion_tree wikiPageUsesTemplate Template:Mvar.
- Fusion_tree wikiPageUsesTemplate Template:Reflist.
- Fusion_tree subject Category:Associative_arrays.
- Fusion_tree subject Category:Trees_(data_structures).
- Fusion_tree hypernym Structure.
- Fusion_tree type Building.
- Fusion_tree type Array.
- Fusion_tree type Structure.
- Fusion_tree type Technique.
- Fusion_tree comment "In computer science, a fusion tree is a type of tree data structure that implements an associative array on w-bit integers. 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 exploiting certain constant-time operations that can be done on a machine word.".
- Fusion_tree label "Fusion tree".
- Fusion_tree sameAs Q5510283.
- Fusion_tree sameAs درخت_تلفیقی.
- Fusion_tree sameAs m.041sgy.
- Fusion_tree sameAs Fuziono_stablo.
- Fusion_tree sameAs Q5510283.
- Fusion_tree wasDerivedFrom Fusion_tree?oldid=700670460.
- Fusion_tree depiction FusionTreeSketch.gif.
- Fusion_tree isPrimaryTopicOf Fusion_tree.
