List-labeling problem

In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:

• insert(X), which inserts X into set S;
• delete(X), which removes X from set S;
• label(X), which returns a label assigned to X subject to:
  • label(X) ∈ { 0 , 1 , … , m − 1 } {\displaystyle \in \{0,1,\ldots ,m-1\}}
  • ∀ {\displaystyle \forall } X,Y ∈ {\displaystyle \in } S, X < Y implies label(X) < label(Y)

The cost of a list labeling algorithm is the number of label (re-)assignments per insertion or deletion. List labeling algorithms have applications in many areas, including the order-maintenance problem, cache-oblivious data structures,^[1] data structure persistence,^[2] graph algorithms^[3][4] and fault-tolerant data structures.^[5]

Sometimes the list labeling problem is presented where S is not a set of values but rather a set of objects subject to a total order. In this setting, when an item is inserted into S, it is specified to be the successor of some other item already in S. For example, this is the way that list labeling is used in the order-maintenance problem. The solutions presented below apply to both formulations.

The cost of list labeling is related to m {\displaystyle m} , the range of the labels assigned. Suppose that no more than n {\displaystyle n} items are stored in the list-labeling structure at any time. Four cases have been studied:

• m = 2 Ω ( n ) {\displaystyle m=2^{\Omega (n)}}
• m = n Ω ( 1 ) {\displaystyle m=n^{\Omega (1)}}
• m = O ( n ) {\displaystyle m=O(n)}
• m = ( 1 + ε ) n {\displaystyle m=(1+\varepsilon )n}

In the exponential label case, each item that is inserted can be given a label that is the average of its neighboring labels. It takes Ω ( n ) {\displaystyle \Omega (n)} insertions before two items are at adjacent labels and there are no labels available for items in between them. When this happens, all items are relabelled evenly from the space of all labels. This incurs O ( n ) {\displaystyle O(n)} relabeling cost. Thus, the amortized relabeling cost in this case is O ( 1 ) {\displaystyle O(1)} .^[6]

The other cases of list labeling can be solved via balanced binary search trees. Consider T {\displaystyle T} , a binary search tree on S of height h {\displaystyle h} . We can label every node in the tree via a path label as follows: Let σ ( X ) {\displaystyle \sigma (X)} be the sequence of left and right edges on the root-to- X {\displaystyle X} path, encoded as bits. So if X {\displaystyle X} is in the left subtree of the root, the high-order bit of σ ( X ) {\displaystyle \sigma (X)} is 0 {\displaystyle 0} , and if it is in the right subtree of the root, the high-order bit of σ ( X ) {\displaystyle \sigma (X)} is 1 {\displaystyle 1} . Once we reach X {\displaystyle X} , we complete σ ( X ) {\displaystyle \sigma (X)} to a length of h + 1 {\displaystyle h+1} as follows. If X {\displaystyle X} is a leaf, we append 0 {\displaystyle 0} s as the low order bits until σ ( X ) {\displaystyle \sigma (X)} has h + 1 {\displaystyle h+1} bits. If X {\displaystyle X} is an internal node, we append one 0 {\displaystyle 0} and then 1 {\displaystyle 1} s as the low order bits until σ ( X ) {\displaystyle \sigma (X)} has h + 1 {\displaystyle h+1} bits.

The important properties of σ ( ) {\displaystyle \sigma ()} are that: these labels are in the range { 0 , 1 , … , 2 h + 1 − 1 } {\displaystyle \{0,1,\ldots ,2^{h+1}-1\}} ; and for two nodes with keys X {\displaystyle X} and Y {\displaystyle Y} in T , {\displaystyle T,} if X < Y , {\displaystyle X<Y,} then σ ( X ) < σ ( Y ) {\displaystyle \sigma (X)<\sigma (Y)} . To see this latter property, notice that the property is true if the least common ancestor of X {\displaystyle X} and Y {\displaystyle Y} is neither X {\displaystyle X} nor Y {\displaystyle Y} , because σ ( X ) {\displaystyle \sigma (X)} and σ ( Y ) {\displaystyle \sigma (Y)} will share bits until their least common ancestor. If X < Y {\displaystyle X<Y} , then because T {\displaystyle T} is a search tree, X {\displaystyle X} will be in the left subtree and will have a next bit of 0 {\displaystyle 0} , whereas Y {\displaystyle Y} will be in the right subtree and will have a next bit of 1 {\displaystyle 1} .

Suppose instead that, without loss of generality, the least common ancestor of X {\displaystyle X} and Y {\displaystyle Y} is X {\displaystyle X} , and that X {\displaystyle X} has depth d {\displaystyle d} . If Y {\displaystyle Y} is in the left subtree of X {\displaystyle X} , then σ ( X ) {\displaystyle \sigma (X)} and σ ( Y ) {\displaystyle \sigma (Y)} share the first d + 1 {\displaystyle d+1} bits. The remaining bits of σ ( X ) {\displaystyle \sigma (X)} are all 1s, whereas the remaining bits of σ ( Y ) {\displaystyle \sigma (Y)} must have a 0 {\displaystyle 0} , so σ ( Y ) < σ ( X ) {\displaystyle \sigma (Y)<\sigma (X)} . If instead Y {\displaystyle Y} is in the right subtree of X {\displaystyle X} , then σ ( X ) {\displaystyle \sigma (X)} and σ ( Y ) {\displaystyle \sigma (Y)} share the first d {\displaystyle d} bits and the d + 1 {\displaystyle d+1} st bit of σ ( X ) {\displaystyle \sigma (X)} is 0 {\displaystyle 0} , whereas the d + 1 {\displaystyle d+1} st bit of σ ( Y ) {\displaystyle \sigma (Y)} is 1 {\displaystyle 1} . Hence σ ( X ) < σ ( Y ) {\displaystyle \sigma (X)<\sigma (Y)} .

We conclude that the σ ( ) {\displaystyle \sigma ()} function fulfills the monotonicity property of the label() function. Thus if we can balance the binary tree to a depth of ( log ⁡ m ) − 1 {\displaystyle (\log m)-1} , we will have a solution to the list labeling problem for labels in the range { 0 , … , m − 1 } {\displaystyle \{0,\ldots ,m-1\}} .

In order to use a self-balancing binary search tree to solve the list labeling problem, we need to first define the cost function of a balancing operation on insertion or deletion to equal the number of labels that are changed, since every rebalancing operation of the tree would have to also update all path labels in the subtree rooted at the site of the rebalance. So, for example, rotating a node with a subtree of size k {\displaystyle k} , which can be done in constant time under usual circumstances, requires Ω ( k ) {\displaystyle \Omega (k)} path label updates. In particular, if the node being rotated is the root then the rotation would take time linear in the size of the whole tree. With that much time the entire tree could be rebuilt. We will see below that there are self-balancing binary search tree data structures that cause an appropriate number of label updates during rebalancing.

A weight-balanced tree BB[ α {\displaystyle \alpha } ] is defined as follows. For every X {\displaystyle X} in a root tree T {\displaystyle T} , define s i z e ( X ) {\displaystyle size(X)} to be the number of nodes in the subtree rooted at X {\displaystyle X} . Let the left and right children of X {\displaystyle X} be X . l e f t {\displaystyle X.left} and X . r i g h t {\displaystyle X.right} , respectively. A tree T {\displaystyle T} is α {\displaystyle \alpha } -weight balanced if for every internal node X {\displaystyle X} in T {\displaystyle T} , s i z e ( X . l e f t ) ≥ ⌊ α ⋅ s i z e ( X . r i g h t ) ⌋ {\displaystyle size(X.left)\geq \lfloor \alpha \cdot size(X.right)\rfloor } and s i z e ( X . r i g h t ) ≥ ⌊ α ⋅ s i z e ( X . l e f t ) ⌋ . {\displaystyle size(X.right)\geq \lfloor \alpha \cdot size(X.left)\rfloor .}

The height of a BB[ α {\displaystyle \alpha } ] tree with n {\displaystyle n} nodes is at most log 1 / ( 1 − α ) ⁡ n = − log ⁡ ( n ) / log ⁡ ( 1 − α ) . {\displaystyle \log _{1/(1-\alpha )}n=-\log(n)/\log(1-\alpha ).} Therefore, in order to solve the list-labeling problem, we need α = 1 − 1 / ( 1 − n − 1 / ( log ⁡ ( m ) − 1 ) ) {\displaystyle \alpha =1-1/(1-n^{-1/(\log(m)-1)})} to achieve a depth of log ⁡ ( m ) − 1. {\displaystyle \log(m)-1.}

A scapegoat tree is a weight-balanced tree where whenever a node no longer satisfies the weight-balance condition the entire subtree rooted at that node is rebuilt. This rebalancing scheme is ideal for list labeling, since the cost of rebalancing now equals the cost of relabeling. The amortized cost of an insertion or deletion is ( 1 + 1 / ( 1 − 2 α ) ) log 1 / 1 − α ⁡ n + O ( 1 ) . {\displaystyle (1+1/(1-2\alpha ))\log _{1/1-\alpha }n+O(1).} For the list labeling problem, the cost becomes:

• m = n Ω ( 1 ) {\displaystyle m=n^{\Omega (1)}} : α = O ( 1 ) {\displaystyle \alpha =O(1)} , the cost of list labeling is amortized O ( log ⁡ n ) . {\displaystyle O(\log n).} (Folklore, modification of Itai, Konheim and Rodeh.^[7])
• m = O ( n ) {\displaystyle m=O(n)} : α = 1 + Θ ( 1 / log ⁡ n ) {\displaystyle \alpha =1+\Theta (1/\log n)} , the cost of list labeling is amortized O ( log 2 ⁡ n ) . {\displaystyle O(\log ^{2}n).} This bound was first achieved by Itai, Konheim, and Rodeh^[7] and deamortized by Willard.^[8]
• m = ( 1 + ε ) n {\displaystyle m=(1+\varepsilon )n} : If m {\displaystyle m} is a power of two, then we can set α = 1 + Θ ( ε / log ⁡ n ) {\displaystyle \alpha =1+\Theta (\varepsilon /\log n)} , and the cost of list labeling is O ( ε − 1 log 2 ⁡ n ) {\displaystyle O(\varepsilon ^{-1}\log ^{2}n)} . A more careful algorithm can achieve this bound even in the case where m {\displaystyle m} is not a power of two.

In the case where m = n 1 + Θ ( 1 ) {\displaystyle m=n^{1+\Theta (1)}} , a lower bound of Ω ( log ⁡ n ) {\displaystyle \Omega (\log n)} ^[9] has been established for list labeling. This lower bound applies to randomized algorithms, and so the known bounds for this case are tight.

In the case where m = ( 1 + Θ ( 1 ) ) n {\displaystyle m={(1+\Theta (1))}n} , there is a lower bound of Ω ( log 2 ⁡ n ) {\displaystyle \Omega (\log ^{2}n)} list labeling cost for deterministic algorithms.^[6] Furthermore, the same lower bound holds for smooth algorithms, which are those whose only relabeling operation assigns labels evenly in a range of items^[10] This lower bound is surprisingly strong in that it applies in the offline cases where all insertions and deletions are known ahead of time.

However, the best lower bound known for the linear case of algorithms that are allowed to be non-smooth and randomized is Ω ( log ⁡ n ) {\displaystyle \Omega (\log n)} . Indeed, it has been an open problem since 1981 to close the gap between the O ( log 2 ⁡ n ) {\displaystyle O(\log ^{2}n)} upper bound and the Ω ( log ⁡ n ) {\displaystyle \Omega (\log n)} in the linear case.^[7][11] Substantial progress on closing the gap has been made by Bender et al. who gave a randomized upper bound of O ( log 1.5 ⁡ n ) {\displaystyle O(\log ^{1.5}n)} ^[12] and subsequently gave a randomized amortized upper bound of O ( log ⁡ n log 3 ⁡ log ⁡ n ) {\displaystyle O(\log n\log ^{3}\log n)} .^[13]

The best known applications of list labeling are the order-maintenance problem and packed-memory arrays for cache-oblivious data structures. The order-maintenance problem is that of maintaining a data structure on a linked list to answer order queries: given two items in the linked list, which is closer to the front of the list? This problem can be solved directly by polynomial list labeling in O ( log ⁡ n ) {\displaystyle O(\log n)} per insertion and deletion and O ( 1 ) {\displaystyle O(1)} time per query, by assigning labels that are monotone with the rank in the list. The time for insertions and deletions can be improved to constant time by combining exponential polynomial list labeling with exponential list labeling on small lists.

The packed-memory array is an array of size ( 1 + ε ) n {\displaystyle (1+\varepsilon )n} to hold n {\displaystyle n} items so that any subarray of size k {\displaystyle k} holds Θ ( k ) {\displaystyle \Theta (k)} items. This can be solved directly by the m = ( 1 + ε ) n {\displaystyle m=(1+\varepsilon )n} case of list labeling, by using the labels as addresses in the array, as long as the solution guarantees that the space between items is O ( 1 ) {\displaystyle O(1)} . Packed-memory arrays are used in cache-oblivious data structures to store data that must be indexed and scanned. The density bounds guarantee that a scan through the data is asymptotically optimal in the external-memory model for any block transfer size.