Reading time: 35 minutes | Coding time: 15 minutes
Fusion tree is a tree data structure that implements associative array in a known universe size. Fusion trees, like Van Emde Boas Trees are used to solve predecessor and successor problem. While Emde Boas tree is useful when universe size is small, fusion tree is used when universe size is large, while providing linear space complexity.
Fusion tree is essentially a B-tree with degree wc where w is the word size and c is some constant smaller than 1. This means the a height of tree will be logwn where n is number of elements stored in the tree.
An important operation used by fusion trees is sketch which is used to compress w bit keys:
Consider the tree given above representing numbers 17, 21, 23. Let this be the fusion tree. Then the sketch operation would give the bits only at branching positions, which are labeled as b0 and b1 in above figure. In above figure, bit positions 1 and 2 (0 indexed) are the branching levels. So sketch will give bits at these position compressed into a single integer.
sketch(21) = sketch(10101) = 1 0 1 0 1 = 01
sketch(17) = sketch(10001) = 1 0 0 0 1 = 00
sketch(23) = sketch(10001) = 1 0 1 1 1 = 11
Considering a general case, we will get r sketch bits: b0, b1, ... br - 1.
Let c be 10 here giving a branching factor of k = w1/10, i.e. each node will have w1/10 - 1 keys and w1/10children. This is where sketch operation comes into play. Since it is not possible to compare all O(k) keys of a node in constant time, sketch operation compresses the keys for faster comparisons between all keys within a node allowing for constant time predecessor queries. Since there are k - 1 keys in a node, r is always less than k.
So the number of bits used to store the sketches of all the keys in a node is O(w2/10). Let keys be x0, x1, ... xk-1. Then sketch(x0) < sketch(x1) < ... < sketch(xk-1) since sketch only considers distinguishing bits.
This sketch is called exact sketch.
- Sketch(x): In practice, approximate sketch is used instead of exact sketch because exact sketch cannot be computed in constant time. Prefect sketch requires the distinguishing bits to be compressed which a computation expensive operation. Approximate sketch doesn't try to compress the distinguishing bits together tightly, rather it adds a fixed pattern of zeroes between every two distinguishing bits. This is done by multiplication with a predetermined constant. The result will be of order O(r4) where r is count of distinguishing bits.
- Let Mask be the mask that will filter out distinguishing bits and m be a predetermined constant.
- x' = x AND Mask. After bitwise AND, x' will have only distinguishing bits.
- result = x' * m. Right shift result until it is r4 bits long. result is the approximate sketch.
To calculate the constant m, a inductive definition is used. Let bi, 0 <= i <= r - 1, be the distinguishing bit positions and Xbr - 1, Xbr - 2, ... ,Xb0 be set bits of the sketch of b. After multiplication of b with m, each bit at bi will be shifted to location bi + mi such that Xi = bi + mi . The word formed after multiplication must follow following properties:
- bi + mj are distinct for all pairs (i, j). This will make sure that no distinguishing bits overlap each other after multiplication.
- bi + mi is a strictly increasing with respect to i. This means that order of distinguishing bits, and thus the order of original words is preserved.
- (br-1 + mr-1) - (b0 + m0) <= r4, i.e. sketch is r4 bits long.
The basic strategy to make m is:
For every t, 0 <= t <= r-1, select smallest value for mt that satisfies mt != bi - bj + mk for every 0 <= i, j <= r-1 and 0 <= k <= t-1.
This is basically equivalent to bi + mj != bk + ml for 0 <= i, j, k , l <= r-1, thus satisfying condition 1. Selecting smallest integers first satisfies condition 2.
Since there are r3 possibilities for mt, condition 3 is also satisfied.
So m will a binary number with positions m0, ..., mr - 1 set as 1, and every 1's will have a padding of r3.
- Parallel comparison: Parallel comparison is used to find position of a value withing the set of keys in a node in constant time. A node will have atmost r + 1 keys. The sketches of all those keys can be concatenated to form a word. This word is used to compare query value q directly with all the keys at once rather than comparing with time one by one.
1. Let X0, X1, ... ,Xr be the keys. 2. Then the sketch of a node is 1sketch(X0)1sketch(X1)... 1sketch(Xr). 3. Convert sketch(a) to sketch(q)' = 0sketch(q)0sketch(q)... 0sketch(q). 4. After subtracting value at step 3 from value at step 2, we will get a number that will be like : 0________0__ ... ___0________1________1________1. Call it diff. 6. There are 0's where sketch of Xi is less than sketch(q) and 1 when Xi is greater than sketch(q). The dashes represent garbage bits where sketch values used to be. It will always be a series of 0's followed by a series of 1's since sketch operation maintains order of keys.The position where the series of 0 turns into 1 is the position where sketch(q) should be placed. So sketch(Xi) < sketch(q) < sketch(Xi + 1), when bit of diff for sketch(Xi) = 0, and for sketch(Xi + 1) is 1
Note that parallel comparison gives index such that sketch of k is tightly bound with the sketches of keys, not the keys itself.
Predecessor and Successor
- Predecessor and Successor: This is also called de-sketching. The algorithm below finds predecessor or successor of q in a node of fusion tree. It will be applied recursively to find children nodes until leaf node is reached.
1. Compute sketch(q), which will give approximate sketch of q. 2. Use parallel comparison to get Xi and Xi + 1 such that sketch(Xi) <= sketch(q) <= sketch(Xi + 1). 3. Find y = common prefix of (Xi or Xi + 1) and k. 4. For successor: Append y with suffix 1000...000 to fill the non_common bits and store it in a variable e. Then e = y100...00. For example: let Xi = 0 1 1 0 0 1 0 1 1 and k = 0 1 1 0 0 0 0 0 0 then y = 0 1 1 0 0 and e = 0 1 1 0 0 1 0 0 0 For predecessor: Append y with suffix 0111...11 to fill the non_common bits and store it in a variable e. Then e = y011...11 5. Use parallel comparison to get Xj and Xj + 1 such that sketch(Xj) < sketch(e) < sketch(Xi + 1). 6. Predecessor of q = Xj. Successor of q = Xj + 1
After sketching, the order is maintained only for the keys. There is no gurantee that if sketch(Xi) < sketch(q) < sketch(Xi + 1) then Xi < q < Xi + 1. That is why steps 3 to 5 are used.
- insert(k): The insertion is almost exactly same as a normal B-tree insertion.
1. Start with current node as root node. 2. Use parallel search to find appropriate position for k. If current node is not a leaf node, set current node as the child at found position. Repeat step 2. 3. Current node is now leaf node. Insert key into correct position. If number of keys is more than max-keys, split the node at middle, and add key at mid position to parent node, with it pointing to current node. If parent node also exceeds max-keys, keep splitting until root is reached. If the root node also exceeds man-keys, split root and make mid key as new root. 4. If the keys in current node have been modified, recalculate node sketch and m.
- Time complexity:
- Find, Successor, Predecessor: O(logwN)
- Insert: O(log2w)
- Delete: O(log2w)
- Space complexity: O(N)
Where N is count of values stored and W is the size of word, i.e. size of data type used to store the values. Complexity of insertion and deletion depends heavily on the strategy used to implement dynamic properties.
class Node: """Class for fusion tree node""" def __init__(self, max_keys = None): self.keys =  self.children =  self.key_count = 0 self.isLeaf = True self.m = 0 self.b_bits =  # distinguishing bits self.m_bits =  # bits of constant m self.gap = 0 self.node_sketch = 0 self.mask_sketch = 0 self.mask_q = 0 # used in parallel comparison self.mask_b = 0 self.mask_bm = 0 self.keys_max = max_keys if max_keys != None: # an extra space is assigned so that splitting can be # done easily self.keys = [None for i in range(max_keys + 1)] self.children = [None for i in range(max_keys + 2)] class FusionTree: """Fusion tree class. initiateTree is called after all insertions in this example. Practically, node is recalculated if its keys are modified.""" def getDiffBits(self, keys): res =  bits = 0 for i in range(len(keys)): if keys[i] == None: break; for j in range(i): w = self.w while (keys[i] & 1 << w) == (keys[j] & 1 << w) and w >= 0: w -= 1 if w >= 0: bits |= 1 << w i = 0 while i < self.w: if bits & (1 << i) > 0: res.append(i) i += 1 return res def getConst(self, b_bits): r = len(b_bits) m_bits = [0 for i in range(r)] for t in range(r): mt = 0 flag = True while flag: flag = False for i in range(r): if flag: break for j in range(r): if flag: break for k in range(t): if mt == b_bits[i] - b_bits[j] + m_bits[k]: flag = True break if flag == True: mt += 1 m_bits[t] = mt m = 0 for i in m_bits: m |= 1 << i return m_bits, m def getMask(self, mask_bits): res = 0 for i in mask_bits: res |= 1 << i return res def initiateNode(self, node): if node.key_count != 0: node.b_bits = self.getDiffBits(node.keys) node.m_bits, node.m = self.getConst(node.b_bits); node.mask_b = self.getMask(node.b_bits) temp =  # bm[i] will be position of b[i] after its multiplication # with m[i]. mask_bm will isolate these bits. for i in range(len(node.b_bits)): temp.append(node.b_bits[i] + node.m_bits[i]) node.mask_bm = self.getMask(temp); # used to maintain sketch lengths r3 = int(pow(node.key_count, 3)) node.node_sketch = 0 sketch_len = r3 + 1 node.mask_sketch = 0 node.mask_q = 0 for i in range(node.key_count): sketch = self.sketchApprox(node, node.keys[i]) temp = 1 << r3 temp |= sketch node.node_sketch <<= sketch_len node.node_sketch |= temp node.mask_q |= 1 << i * (sketch_len) node.mask_sketch |= (1 << (sketch_len - 1)) << i * (sketch_len) return def sketchApprox(self, node, x): xx = x & node.mask_b res = xx * node.m res = res & node.mask_bm return res def __init__(self, word_len = 64, c = 1/5): # print(word_len) self.keys_max = int(pow(word_len, c)) self.keys_max = max(self.keys_max, 2) self.w = int(pow(self.keys_max, 1/c)) self.keys_min = self.keys_max // 2 print("word_len = ", self.w, " max_keys = ", self.keys_max) self.root = Node(self.keys_max) self.root.isLeaf = True; def splitChild(self, node, x): # a b-tree split function. Splits child of node at x index z = Node(self.keys_max) y = node.children[x] # y is to be split # pos of key to propagate pos_key = (self.keys_max // 2) z.key_count = self.keys_max - pos_key - 1 # insert first half keys into z for i in range(z.key_count): z.keys[i] = y.keys[pos_key + i + 1] y.keys[pos_key + i + 1] = None if not y.isLeaf: for i in range(z.key_count + 1): z.children[i] = y.children[pos_key + i + 1] y.key_count = self.keys_max - z.key_count - 1 # insert key into node node.keys[x] = y.keys[pos_key] # same effect as shifting all keys after setting pos_key # to None del y.keys[pos_key] y.keys.append(None) # insert z as child at x + 1th pos node.children[x + 1] = z node.key_count += 1 def insertNormal(self, node, k): # print(node, node.keys,'\n', node.key_count) # insert k into node when no chance of splitting the root if node.isLeaf: i = node.key_count while i >= 1 and k < node.keys[i - 1]: node.keys[i] = node.keys[i - 1] i -= 1 node.keys[i] = k node.key_count += 1 return else: i = node.key_count while i >= 1 and k < node.keys[i - 1]: i -= 1 # i = position of appropriate child if node.children[i].key_count == self.keys_max: self.splitChild(node, i) if k > node.keys[i]: i += 1 self.insertNormal(node.children[i], k) def insert(self, k): # This insert checks if splitting is needed # then it splits and calls normalInsert # if root needs splitting, a new node is assigned as root # with split nodes as children if self.root.key_count == self.keys_max: temp_node = Node(self.keys_max) temp_node.isLeaf = False temp_node.key_count = 0 temp_node.children = self.root self.root = temp_node self.splitChild(temp_node, 0) self.insertNormal(temp_node, k) else: self.insertNormal(self.root, k) def successorSimple(self, node, k): i = 0 while i < node.key_count and k > node.keys[i]: i += 1 if i < node.key_count and k > node.keys[i]: return node.keys[i] elif node.isLeaf: return node.keys[i] else: return self.successor2(node.children[i], k) def parallelComp(self, node, k): # this function should basically give the index such # that sketch of k lies between 2 sketches sketch = self.sketchApprox(node, k) # This will give repeated sketch patterns to allow for comparison # in const time sketch_long = sketch * node.mask_q res = node.node_sketch - sketch_long # mask out unimportant bits res &= node.mask_sketch # find the leading bit. This leading bit will tell position i of # such that sketch(keyi-1) < sketch(k) < sketch(keyi) i = 0 while (1 << i) < res: i += 1 i += 1 sketch_len = int(pow(node.key_count, 3)) + 1 return node.key_count - (i // sketch_len) def successor(self, k, node = None): if node == None: node = self.root if node.key_count == 0: if node.isLeaf: return -1 else: return self.successor(k, node.children) # the corner cases are not concretely defined. # other alternative to handle these would be to have # -inf and inf at corners of keys array if node.keys >= k: if not node.isLeaf: res = self.successor(k, node.children) if res == -1: return node.keys else: return min(node.keys, res) else: return node.keys if node.keys[node.key_count - 1] < k: if node.isLeaf: return -1 else: return self.successor(k, node.children[node.key_count]) pos = self.parallelComp(node, k) # print("pos = ", pos) if pos >= node.key_count: print(node.keys, pos) dump = input() if pos == 0: pos += 1 # x = node.keys[pos] # find the common prefix # it can be guranteed that successor of k is successor # of next smallest element in subtree x = max(node.keys[pos - 1], node.keys[pos]) # print("x = ", x) common_prefix = 0 i = self.w while i >= 0 and (x & (1 << i)) == (k & (1 << i)): # print(i) common_prefix |= x & (1 << i) i -= 1 if i == -1: return x temp = common_prefix | (1 << i) pos = self.parallelComp(node, temp) # if pos == 0: # possible error? # pos += 1 # print("pos = ", pos, bin(temp)) if node.isLeaf: return node.keys[pos] else: res = self.successor(k, node.children[pos]) if res == -1: return node.keys[pos] else: return res def predecessor(self, k, node = None): if node == None: node = self.root if node.key_count == 0: if node.isLeaf: return -1 else: return self.predecessor(k, node.children) # the corner cases are not concretely defined. # other alternative to handle these would be to have # 0 and inf at corners of keys array if node.keys > k: if not node.isLeaf: return self.predecessor(k, node.children) else: return -1 if node.keys[node.key_count - 1] <= k: if node.isLeaf: return node.keys[node.key_count - 1] else: ret = self.predecessor(k, node.children[node.key_count]) return max(ret, node.keys[node.key_count - 1]) pos = self.parallelComp(node, k) if pos >= node.key_count: print(node.keys, pos, "ERROR? pos > key_count") dump = input() if pos == 0: pos += 1 # find the common prefix # it can be guranteed that successor of k is successor # of next smallest element in subtree x = node.keys[pos] common_prefix = 0 i = self.w while i >= 0 and (x & (1 << i)) == (k & (1 << i)): common_prefix |= x & (1 << i) i -= 1 if i == -1: # i.e. if x is exactly equal to k return x temp = common_prefix | ((1 << i) - 1) pos = self.parallelComp(node, temp) if pos == 0: if node.isLeaf: return node.keys[pos] res = self.predecessor(k, node.children) if res == -1: return node.keys[pos] else: return res if node.isLeaf: return node.keys[pos - 1] else: res = self.predecessor(k, node.children[pos]) if res == -1: return node.keys[pos - 1] else: return res def initiate(self, node): if node == None: node = Node(self.keys_max) self.initiateNode(node) if not node.isLeaf: for i in range(node.keys_max + 1): self.initiate(node.children[i]) def initiateTree(self): self.initiate(self.root) if __name__ == "__main__": # create a fusion tree of degree 3 tree = FusionTree(243) tree.insert(1) tree.insert(5) tree.insert(15) tree.insert(16) tree.insert(20) tree.insert(25) tree.insert(4) print(tree.root.keys) for i in tree.root.children: if i is not None: print (i, " = ", i.keys) if not i.isLeaf: for j in i.children: if j is not None: print( j.keys) tree.initiateTree() # the tree formed should be like: # [| 5 | | 16 |] # / | \ # / | \ # [1, 4]  [20, 25] print("\nKeys stored are:") print("1, 4, 5, 15, 16, 20, 25\n") print("Predecessors:") for i in range(26): print(i, "------------------->", tree.predecessor(i), sep = '\t') print("Successor:") for i in range(26): print(i, "------------------->", tree.successor(i), sep = '\t')
- Fusion tree are used extensively in database systems.
- Fusion tree and Van Emde boas tree are together. When word size is large, fusion tree are used. When word size is smaller, Van Emde Boas tree is used.
References/ Further reading
- Try to change insert function to use parallel comparison as an exercise.