Q-Heap (Fredman & Willard, 1994)

Q-Heaps are similar to fusion trees, in that they, as a data structure, operate based on the different bits in the words they have to sort. Fusion trees are, however, beyond the scope of this project, which will focus mainly on Q-heaps. Q-heaps allow for the use of Boolean logic in algorithms that can lead to a significant speed-up.

The input into a q-heap is a sorted array of numbers, similar to the lists that are attached to each node in the catalog tree. Let b be the number of bits used to represent each number. Given a set S = {u₁,u₂,u₃,u₄…u_k} where u_i>u_i-1 for 0<i<k+1, we construct a set B(S) = {c₁,c₂,c₃,c₄…c_k-1} where c_i = msb(u_i,u_i+1), the most significant bit that is different between each number. This set is not a multi-set and thus, may have fewer than k-1 elements. Let z_s be the sequence c₁,c₂,c₃,c₄…c_k-1 (has k-1 elements). We can also represent z_s with t_s = d₁,d₂,d₃,d₄…d_k-1 where d_i = rank_B(S)(c_i), the rank (position from the maximum) of the element in the set B(S), mapping it from B(S).

Recursively, take the maximum of c, c_j in z_s and construct a binary search tree with the root labeled as c_j, such that for i<j, c_i will label nodes in the left subtree, and the rest, labeling nodes in the right subtree. Querying would work as such: if a number had a 0 at the differing bit, proceed down the left subtree, if not, proceed down the right subtree. We can then augment the tree with leaves numbering from 1 to k, left to right, representing these numbers. Computing the number would be central to querying for a value through the path it takes.

As an example, we will use a set of 8-bit unsigned numbers consisting of 5, 19, 30, 49, 52, 63, 68, 75, 88, 93, 127.

Querying

Lemma: For a query, u, Tree(z_s ), i = Leaf(z_s,u), the leaf traced by the path taken by u through the tree, and rank_B(S)(msb(u,u_i )) can determine rank_s(u) after comparing u with u_i(less than, equal or greater than)

Let r = |B(S)| and m = rank_B(S)(msb(u,u_i )). By induction on r-m, if r-m = 0 and u != u_i , the most significant bit is outside of B(S) and if u < u_i , rank_s(u) = 0, else rank_s(u) = |S|. If u = u_i, there is nothing to prove.

If r-m > 0, the elements in B(S) determine the largest possible bit that can differ between any two elements. As m<r, u has to agree with u_i in terms of what bit lies in the largest possible bit. The subtrees of the root at S, can then be recursed with the same argument from the start, to eventually obtain rank_s(u), by adding up the number of leaves that are to the left of where u's place will be.

This lemma will be used as the basis to construct a look-up table such that traversal is unnecessary.

Calculating rank_B(S)(msb(u,u_i ))

In essence, msb(u,u_i) is the leftmost bit of (u XOR u_i). Let the result of (u XOR u_i) be v. Assume that v != 0, as this can be verified in one machine instruction.

Here, we introduce the concept of sparsity, where we consider a number d-sparse if the position of its one-bits can take the form of {a+d_i| 0<= i< d}. If v is d-sparse, there exists 2 constants y₁ and y₂ such that for a y= (y₁v) AND y₂ , the ith bit of the significant part of y is the bit in position a+d_i| 0<= i< d .

Consider a partition of s = √(b) + 1 bits within v. Two computations are done, the first to find the block with the first one-bit, and the second, to find the bit position of the first one-bit in that block. Define a C₁ such that in each block, the leftmost position is a 1, and a C₂ that is the bit-wise complement of C₁. The first function on v, is to compute (C₁ - [(C₁ - x AND C₂) AND C₁]) OR (x AND C₁) which gives a value, p, in which the leading bit of each block is one, only if there is a one in the block. It is then possible to compress this value, as this value is d-sparse, where d is the size of the block.

Let P = {bin(0), bin(1) ... bin(b/s -1)}. Calculating the rank of obtained p above, in P allows us to know the position of the block containing the leading one. Concatenate together the powers of 2 in P to the length of b/s blocks (for e.g. 0100 0010 0001) if each block was 4 bits in length (can be pre-computed). Compute a value 10..p 10..p.... with each field being the size of the block. This can be obtained through bitwise multiplication and OR instruction. If we subtract the concatenation from the computed value repeating 10..p, and count the number of one-bits in the leading bit of each field by a suitable multiplication, we can obtain the rank, which tells us which block the first one-bit is in.

Repeat this procedure on the block with the first one-bit, performing rank-computation on the bit-block using the method in the previous paragraph. msb(u,u_i) can thus be calculated in constant time.

rank_B(S)(msb(u,u_i )) can then be computed using the same rank computation, replacing the powers of 2 with a concatenation of the elements in B(S).

Getting Leaf(z_s,u)

To compute Leaf(z_s,u), we have to be able to map the nodes to relevant bit values of u.

First we construct a mask to remove the irrelevant bit values of u with reference to the tree. In the example above, the mask would be 01111100. Then, we construct a multiplier to align these bit numbers in contiguous order before extracting a field to be decoded that corresponds to a mapping of bit values from u to z_s. Let bin(a_1, a_2, ... a_k) = 2^a1 + 2^a2 ... + 2^ak . There exists a multiplier M = bin(m_1, m_2, ... m_k) that pairs each m_i with each a_i in B(S), relocating the important bits to a narrow field for extraction.

To figure out which leaf it lands in in constant time, we have to construct a decoder that extracts the path through the tree from the field that results. This decoder holds a tuple of sets, where the ith set corresponds to the bit positions of the extracted field that the ith element within B(S) affected. Let r = |B(S)| and M denote the union of these sets. The ith set can also be defined as {mj+ai-b | 1<=j<= r and b <= mj + ai < b +f}. In our example word size, b, is 8.

We will use the first 4 elements with a possible multiplier as an example.

For any given a' in B(S), let B(S)' denote the set of those a_i s that precede a' (relative to insertion ordering) and let m' denote the m_i value paired with a'. f in this case is 5L³ where L is the size of the Q-heap.

Conditions for the multiplier listed in the paper include the following:

• The residues (mod f) of the various m_j's including m' are distinct.
• For t'=m'+a'-b we have that 2L<=t'<f
• The interval [t'-2L, t'] avoids all members of M', M' given as {m_j+a_i -b | m_j precedes m', a_i precedes a', and b<=m_j+a_i <b+f}
• For no i and h, with a_i and a_h in B(S)', does m'+ a_i - b fall into the protected interval [t_h -2L, t_h].

The idea behind these conditions, is such that we can obtain an algorithm that modifies the multiplier by adding/removing in a power of 2 should a new a_i be added in constant time to B(S), thus preserving the time speed-up when inserting or deleting, by using the table look up to update t_s. A caveat is the L<= O(log^1/5 n) as a bound on the multiplier to prevent an overly large multiplier.

The decoder then should be written such that it can map the values of the extracted field after multiplication to each edge in Tree(z_s ). We construct a table to map this, such that table-lookup can find the leaf in constant time.

Conclusion and Thoughts

As Tree(z_s ), i, rank_B(S)(msb(u,u_i )) and the comparison between u and u_i can determine rank_s(u) pre-processing can be done such that a table can be constructed to accurately map these values to rank_s(u). Table-look up can be done in constant time, such that finding the rank, and subsequently the successor for the purpose of fractional cascading, is constant as well.

The algorithms here however are dependent on |B(S)| and shortcuts through the use of boolean instructions. Although the space complexity is not large, the computations for pre-processing might make this too complicated to be practical. The authors of the paper have acknowledged that it was done from a theoretical perspective.