Fast Fractional Cascading

In the section on fractional cascading, we were shown a method of querying items from a set of multiple lists, returning the lists the items belong in, in O(k+log n) time through O(nk) pre-processing, where n is the number of elements in each list and k, the number of lists.

Generally, fractional cascading is conducted on catalog graph, a directed graph where each vertex is linked to an ordered list. A query within this graph then consists of a path through the graph and a singular query value, which would return the position of that value in the lists through the graph, or its successor if necessary. Each vertex is bounded in terms of its incoming and outgoing edges, which determines the degree of augmentation that can be done on the ordered lists while still maintaining a linear space complexity.

In the course, fractional cascading was done on a series of arrays, and the augmented superset was constructed based on half of the previous augmented set. This example can be said to be a directed graph of nodes with one incoming edge and one outgoing edge, with each node containing one array of sorted numbers. In other words, the example in the course note is akin to a singly linked list, which is also a catalog graph. Other catalog graphs allow for data structures to be implemented, and for information to be stored via the arrangement of lists, such as binary trees in an example at the bottom of this page. The graph used in the course notes is represented below.

For the purposes of the fast fractional cascading algorithm, Shi and Jaja (2005) primarily dealt with catalog trees as the initial set-up of the problem, with queries having both a value to query, and a subset of the catalog tree as the sets that are to be queried. p as later mentioned in this paragraph would be the nodes that are to be queried, while c, the bound on the degree of the nodes within the catalog tree. p is essentially k in the course slides.

When fractional cascading is done on catalog trees, its efficiency is limited by the degree of the nodes in the tree, with the time complexity reaching O(log n + p log c). Below is an example of fractional cascading on a more complex catalog tree. With degree 2, the fraction of augmentation has to be less than 1/2, so for this example, 1/3 was chosen. Similarly, each element must have a pointer to the next bridge to access the next augmented lists, and those that form the bridge must be linked to the next successor, such that querying through the gap between the bridges can be done in constant time, and successors can be found in constant time as well. Due to the multiple lines, only the bridges and the links in the first augmented list are shown.

Catalog trees are often used instead, such that the technique of fractional cascading may be applicable to a whole set of problems in computational geometry involving range or segment trees.

For example, Chazelle and Guibas (1986) made use of fractional cascading to aid in their algorithm for solving the problem involving the intersection of a polygonal path with a line. Below is a brief description of how they formulated the problem and its algorithm.

Checking each edge in the polygonal path, and if it intersected with the line would result in the space complexity of O(n) and a query time of O(n). A polygonal path is simply a connected series of line segments.

Their algorithm involved cutting the polygonal path into half at each step (per edge), and computing the intersection between the convex hull of each half and the line. An example with one layer is given below.

In each convex hull, there exists a permutation of the edges in the convex hull, such that the slope of the edges are in non-decreasing order. This permutation is known as the slope-sequence. Let c₁ c_{2 ...} c_n, represent a clockwise order of the vertices in the convex hull. The slope of each edge c_i to c_i+1 is defined as the angle in [0, 2*π) between a horizontal ray from c_i to +∞ and the edge from c_i to c_i+1.

In each node on the catalog tree, each 2-dimensional edge is represented in terms of its slope. The position of each edge in the slope sequence effectively conveys the information of the vertices where tangents parallel to the line might occur. The line would only intersect the edge if the line was between the two tangents. The slope-sequence is the catalog at each node.

Fractional cascading can then be done on these catalogs, and if it is required to descend the subtree (the line not being out of bounds from the convex hull), the slope-sequences of lower subtrees can be searched in constant time for each node and edge intersected.

The resulting time complexity, for a path that intersects with the line at k edges, is O((k+1)log[n/(k+1)]) including the O(log n) used to query the root.

Given the catalog trees use for fractional cascading problems, of which one such problem was described above, Shi and Jaja(2005) proposed a method that seeked to further reduce the time-complexity of fractional cascading.

Shi and Jaja (2005) in their paper, derived a method of fast fractional cascading. Fast fractional cascading utilizes Q-heaps and the RAM model to be able to maintain constant time for searching through the lists with the exception of the list at the root, while still maintaining O(n) space complexity.

The RAM model and Q-heaps' explanations can be found by clicking on their links. The algorithm they used can be found here.