How It Works
A fusion tree is essentially a B-tree with branching factor of w1/5 (any small exponent is also possible), which gives it a height of O(logw n). To achieve the desired runtimes for updates and queries, the fusion tree must be able to search a node containing up to w1/5 keys in constant time. This is done by compressing ("sketching") the keys so that all can fit into one machine word, which in turn allows comparisons to be done in parallel. The rest of this article will describe the operation of a static Fusion Tree; that is, only queries are supported.
Read more about this topic: Fusion Tree
Famous quotes containing the word works:
“Most young black females learn to be suspicious and critical of feminist thinking long before they have any clear understanding of its theory and politics.... Without rigorously engaging feminist thought, they insist that racial separatism works best. This attitude is dangerous. It not only erases the reality of common female experience as a basis for academic study; it also constructs a framework in which differences cannot be examined comparatively.”
—bell hooks (b. c. 1955)