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:
“The difference between de jure and de facto segregation is the difference open, forthright bigotry and the shamefaced kind that works through unwritten agreements between real estate dealers, school officials, and local politicians.”
—Shirley Chisholm (b. 1924)