Fusion Trees
Recall from Wednesday:
A fusion tree is a B-tree whose minimum degree is
w1/6 = log1/6(u). A node in this tree contains k keys that are
compressed to fit into a single word.
Our goal is to find the rank of a key x within this node using O(1)
arithmetic and bitwise operations. It suffices to find the rank of the
compressed key x within y ,...,y .
(cid:98) (cid:98)1 (cid:98)k
Ongoing example.
y =00000100, y =00001101, y =01001010, y =01001101
1 2 3 4
y =001, y =011, y =110, y =111
(cid:98)1 (cid:98)2 (cid:98)3 (cid:98)4
1/9
Fusion Trees
Now let us address the problem of finding the rank of a
compressed key x
(cid:98)
in Y(cid:98) in O(1) time. Consider x (cid:98)= 101.
Let
X = 10x 10x 10x 10x
(cid:98) (cid:98) (cid:98) (cid:98)
= 10101 10101 10101 10101
Let
K = 00y 00y 00y 00y
(cid:98)4 (cid:98)3 (cid:98)2 (cid:98)1
= 00111 00110 00011 00001
Each of these numbers consists of 4 blocks of digits.
2/9
Fusion Trees
Now calculate X −K:
X −K = 01110 01111 10010 10100
If x ≥ y , the leading digit in the corresponding block is of X −K
(cid:98) (cid:98)j
is 1. Otherwise, the leading digit in that block is 0.
By taking a bitwise AND with an appropriate number, we can zero
out all but the leading digit in each block. The result is
00000 00000 10000 10000
To find the rank of x
(cid:98)
in Y(cid:98), we need to count how many leading 1’s
remain. In other words, we need the sum of the leading digits of
the blocks.
3/9
Fusion Trees
Luckily, we can get that sum with a single multiplication. Multiply
by 00001 00001 00001 00001:
00000 00000 10000 10000
00000 00000 10000 10000
00000 00000 10000 10000
+ 00000 00000 10000 10000
00000 00000 10001 00001 00001 00000 100000
Then extract the required sum of digits by bit-shifting the product.
4/9
Fusion Trees
Source. Fredman, Willard. Surpassing the Information Theoretic
Bound with Fusion Trees. JCSS 47. pp. 424-436. 1993.
Questions
(1) What arithmetic and bitwise operations do the authors
assume can be done in O(1) time?
(2) What is the smallest value of k you can find such that there
exist binary numbers y ,...,y that can be distinguished by
1 k
strictly fewer than k −1 bits? Give a small example of such
y ,...,y .
1 k
(3) What is the purpose of the number M = bin(m ,m ,...,m )?
1 2 r
How is a key x converted into its compressed form x in O(1)
(cid:98)
time?
(4) Why do the authors require B ≤
(cid:4) b1/6(cid:5)
?
5/9
Fusion Trees
(1) Under the model of computation in this paper, the following
are O(1) operations.
• Add two words
• Subtract two words
• Multiply two words
• Compare two words
• Perform a bitwise AND of two words.
Assuming the appropriate constants are available, the
following operations can also be performed in O(1) time.
• Right shift by r bits
• Bitwise OR of two words
• Bitwise XOR of two words
6/9
Fusion Trees
(2) Two binary numbers clearly require one bit to distinguish
them.
Three binary numbers require two bits to distinguish them,
since any one bit can only take on two distinct values.
However, once k = 4 or more, we might require fewer than
k −1 bits. For example, the four numbers
y = 001, y = 011, y = 100, y = 110
1 2 3 4
can all be distinguished from each other by looking at the first
two most significant bits.
7/9
Fusion Trees
(3) Start with a key x. Suppose that the bits that need to be
preserved in the compressed form occur at positions
c < ... < c .
1 r
Take the bitwise AND of x with bin(c ,...,c ). Then the
1 r
values of the r bits of interest remain unchanged, but the
other digits of x are set to 0. Call the result x′.
Find a collection of numbers m ,...,m such that
1 r
m +c = b, all of the sums c +m are distinct,
1 1 i j
m < c < ... < m +c , and (m +c )−(m +c ) ≤ r4.
1 1 r r r r 1 1
Construct the number M = bin(m ,m ,...,m ), and
1 2 r
calculate Mx′. The result consists of two words. Within the
more significant word, the compressed bits of x′ can be found
among the r4 least significant bits.
8/9
Fusion Trees
Simplified Example. On Wednesday, we considered the key
x = 0100 0100. The bits to be preserved in the compressed form –
now counting from least significant to most significant, starting at
0 – were c = 2, c = 3, c = 6.
1 2 3
All the other bits in x are already 0, so converting x to x′ doesn’t
change anything.
Let M = 0101 0000. (I didn’t follow the procedure in Lemma 2 to
get this M.) I claim that multiplication by M shifts c → 8,
1
c → 9, c → 10:
2 3
0100 0100 0000
+ 0001 0001 0000 0000
0001 0101 0100 0000
9/9
