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, data structure persistence, graph algorithms and fault-tolerant data structures. 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.
Upper bounds 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}
Exponential Labels 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)} .
Polynomial Labels 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
… excerpt ends here. Continue reading the full article.
