Fast Fractional Cascading (Jaja and Shi, 2005)

With Non-Linear Space

From the fractional cascading problem described on the homepage, we keep the pointers to the next down-bridge (children in the case of a tree). The number of pointers is at most c pointers (degree of node) for each element in the augmented catalog.

For each gap in the fractional cascading problem described on the homepage, we construct a Q-heap, containing distinct elements (first of duplicate elements) which correspond to the node the gap is in. This gap refers to the gap between two bridges from the node's parent, that is, the root of the whole has no gaps. Using Q-heaps, we can find the successor of a query in the gap in constant time, while allowing for constant time access to the next gap using pointers, by being supported with an O(n) space table to look-up.

This structure allows for the use of O(p + t(n)), where t(n) is the time it takes to find a successor in the root, and p, the number of vertices. The picture below illustrates the use of Q-heaps within a fractional cascading structure, representing the gap that includes only elements of the unaugmented list within the gap, yet retaining the pointers referred to in the original fractional cascading.

With Linear Space

We can partition each augmented catalog A(u) into |A(u)|/c blocks (rounded up) containing c elements each, B₁ ... B_p . For each B_i , starting from the lth element(the first bridge to the children augmented list), we can construct a set C_i of <= 7c - 1 elements each. This value is essentially the upper bound of the gap (6c -1 in the paper) + c, where c is the bound for the degree of each node in the tree.

For every dth element that has a pointer to the children node's augmented list (a down-bridge), where l<= d <= l + 7c - 2, we include in the set C_i a record r, that includes a pointer and a key. The pointer points to the bridge to the child's augmented list. The value of the key defined by Jaja and Shi is given by j * (7c -1) + (d-l) for the down-bridge that links the current node to its (j+1)th child.

We can determine the block any down-bridge g belongs to, as well as its position in the block, in constant time. If g does not connect the two nodes our input demands, due to the gap size invariant of augmenting each list with child node elements, h which links the two nodes must exist in C_i . Since (d-l) <7c-1, it is trivial to find the next down-bridge by finding the successor of an element with knowledge of degree of the node, and thus correspondingly, the j-values that are required to query. Finding the successor can be done by turning each C_i into a Q-heap, such that it is still possible to access each successor in constant time, without resorting to pointers from every element, thus allowing a bound of O(n) for space complexity due to the number of blocks. This conclusion can also be observed from the fact that there are at most O(n) distinct keys produced.

As it takes constant time to find a block, and constant time to determine the rank within C_i, and then at most query C_i+1 for the next bridge, it is possible to retain constant time querying per list and access to a child augmented catalog, without cn number of pointers.

A benefit to using Q-heaps also exists in that we no longer need an O(1) gap between the bridges in the augmented lists, and can use Q-heaps to ensure constant time access to elements in the gaps with O(log^1/5 n) as stated by Jaja and Shi (2005), given a sufficiently large n.