About: Fusion tree

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Fusion tree Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Building, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FFusion_tree

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 integer 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(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 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.

Attributes	Values
rdf:type	yago:WikicatAssociativeArrays yago:Abstraction100002137 yago:Arrangement107938773 yago:Array107939382 yago:Group100031264 building
rdfs:label	Fusion tree (en)
rdfs:comment	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 integer 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(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 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. (en)
foaf:depiction
dcterms:subject	Trees (data structures) Associative arrays
Wikipage page ID	1051942 (xsd:integer)
Wikipage revision ID	1118094062 (xsd:integer)
Link from a Wikipage to another Wikipage	Bitwise AND Bitwise XOR Van Emde Boas tree Most significant bit Dan Willard Tree data structure Computer science Michael Fredman B-tree Exponential tree Quasi-polynomial time Hash table Hash tables Attribute–value pair AC0 Trees (data structures) Associative array Associative arrays Circuit complexity C programming language Self-balancing binary search tree Machine word Parallelism (computing)
Link from a Wikipage to an external page	https://web.archive.org/web/20060904224451/http:/theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L4/lecture4.pdf https://web.archive.org/web/20060904224739/http:/theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L5/lecture5.pdf http://courses.csail.mit.edu/6.851/spring07/scribe/lec13.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/lec12.pdf
sameAs	Fusion tree Fusion tree Fusion tree Fusion tree Fusion tree Fusion tree
dbp:wikiPageUsesTemplate	dbt:CS-Trees dbt:Math dbt:Mvar dbt:Reflist dbt:Technical
thumbnail	wiki-commons:Special:FilePath/FusionTreeSketch.gif?width=300
has abstract	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 integer 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(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 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. 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 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 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 n) per operation. It remains open whether dynamic fusion trees can achieve O(logw n) per operation with high probability. This data structure is helpful for predecessor and successor search operations which provide an output as the greatest key value smaller than the queried key or the smallest key value larger than the queried key, respectively. The partial result of most significant bit locator in constant time has also helped a lot of further research. The chief idea why this work is efficient is because it deploys word-level parallelism, which means that the computation on multiple words takes place simultaneously, making the number of overall operations way less than they should be. Other operations that can be performed on this data structure are add a key, and remove a key. (en)
gold:hypernym	Structure
prov:wasDerivedFrom	wikipedia-en:Fusion_tree?oldid=1118094062&ns=0
page length (characters) of wiki page	16768 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Fusion_tree
is Link from a Wikipage to another Wikipage of	List of data structures Binary search algorithm Van Emde Boas tree T-tree Dan Willard Priority queue Predecessor problem Hash table AF-heap Integer sorting With high probability Self-balancing binary search tree Word RAM
is foaf:primaryTopic of	wikipedia-en:Fusion_tree

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 53 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software