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)
    • X,Y 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.


Upper bounds

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

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 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 relabeling cost. Thus, the amortized relabeling cost in this case is .[6]

Polynomial Labels

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

The important properties of are that: these labels are in the range ; and for two nodes with keys and in if then . To see this latter property, notice that the property is true if the least common ancestor of and is neither nor , because and will share bits until their least common ancestor. If , then because is a search tree, will be in the left subtree and will have a next bit of , whereas will be in the right subtree and will have a next bit of .

Suppose instead that, without loss of generality, the least common ancestor of and is , and that has depth . If is in the left subtree of , then and share the first bits. The remaining bits of are all 1s, whereas the remaining bits of must have a , so . If instead is in the right subtree of , then and share the first bits and the st bit of is , whereas the st bit of is . Hence .

We conclude that the function fulfills the monotonicity property of the label() function. Thus if we can balance the binary tree to a depth of , we will have a solution to the list labeling problem for labels in the range .

Weight-balanced trees

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 , which can be done in constant time under usual circumstances, requires 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[] is defined as follows. For every in a root tree , define to be the number of nodes in the subtree rooted at . Let the left and right children of be and , respectively. A tree is -weight balanced if for every internal node in , and

The height of a BB[] tree with nodes is at most Therefore, in order to solve the list-labeling problem, we need to achieve a depth of

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 For the list labeling problem, the cost becomes:

  • : , the cost of list labeling is amortized (Folklore, modification of Itai, Konheim and Rodeh.[7])
  • : , the cost of list labeling is amortized This bound was first achieved by Itai, Konheim, and Rodeh[7] and deamortized by Willard.[8]
  • : If is a power of two, then we can set , and the cost of list labeling is . A more careful algorithm can achieve this bound even in the case where is not a power of two.

Lower bounds and open problems

In the case where , a lower bound of [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 , there is a lower bound of 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 . Indeed, it has been an open problem since 1981 to close the gap between the upper bound and the in the linear case.[7][11]

Applications

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 per insertion and deletion and 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 to hold items so that any subarray of size holds items. This can be solved directly by the 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 . 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.

References

  1. Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin (2005), "Cache-oblivious B-trees" (PDF), SIAM Journal on Computing, 35 (2): 341–358, doi:10.1137/S0097539701389956, MR 2191447.
  2. Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E. (1989), "Making data structures persistent", Journal of Computer and System Sciences, 38 (1): 86–124, doi:10.1016/0022-0000(89)90034-2, MR 0990051.
  3. Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon (1997), "Sparsification—a technique for speeding up dynamic graph algorithms", Journal of the ACM, 44 (5): 669–696, doi:10.1145/265910.265914, MR 1492341.
  4. Katriel, Irit; Bodlaender, Hans L. (2006), "Online topological ordering", ACM Transactions on Algorithms, 2 (3): 364–379, CiteSeerX 10.1.1.78.7933, doi:10.1145/1159892.1159896, MR 2253786.
  5. Aumann, Yonatan; Bender, Michael A. (1996), "Fault tolerant data structures", Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996), pp. 580–589, doi:10.1109/SFCS.1996.548517, ISBN 978-0-8186-7594-2.
  6. Bulánek, Jan; Koucký, Michal; Saks, Michael E. (2015), "Tight Lower Bounds for the Online Labeling Problem", SIAM Journal on Computing, vol. 44, pp. 1765--1797.
  7. Itai, Alon; Konheim, Alan G.; Rodeh, Michael (1981), "A Sparse Table Implementation of Priority Queues", ICALP, pp. 417–431
  8. Willard, Dan E. (1992), "A Density Control Algorithm for Doing Insertions and Deletions in a Sequentially Ordered File in Good Worst-Case Time", Information and Computation, vol. 97, pp. 150–204.
  9. Dietz, Paul F.; Seiferas, Joel I.; Zhang, Ju (1994), "A tight lower bound for on-line monotonic list labeling", Algorithm theory—SWAT '94 (Aarhus, 1994), Lecture Notes in Computer Science, vol. 824, Berlin: Springer, pp. 131–142, doi:10.1007/3-540-58218-5_12, ISBN 978-3-540-58218-2, MR 1315312.
  10. Dietz, Paul F.; Zhang, Ju (1990), "Lower bounds for monotonic list labeling", Algorithm theory—SWAT '90, pp. 173–180.
  11. Saks, Michael (2018), "Online Labeling: Algorithms, Lower Bounds and Open Questions", International Computer Science Symposium in Russia, pp. 23–28.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.