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:
“In doing good, we are generally cold, and languid, and sluggish; and of all things afraid of being too much in the right. But the works of malice and injustice are quite in another style. They are finished with a bold, masterly hand; touched as they are with the spirit of those vehement passions that call forth all our energies, whenever we oppress and persecute..”
—Edmund Burke (1729–97)