Jan Bulánek
ABSTRACT
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m ≥ n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r ≤ m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves the algorithm has to do. This problem is non-trivial when n ≤ m < r.
In the case that m = Cn for some C>1, algorithms for this problem with cost O(log(n)2) per item have been given [Itai et al. (1981), Willard (1992), Bender et al. (2002)]. When m=n, algorithms with cost O(log(n)3) per item were given [Zhang (1993),Bird and Sadnicki (2007)]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Ω(log(n)2) for the restricted class of smooth algorithms [Dietz et al. (2005), Zhang (1993)].
We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
Supplemental Material
- Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, and Michael E. Saks. Local management of a global resource in a communication network. J. ACM, 43(1):1--19, 1996. Google Scholar
Digital Library
- Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, and Michael E. Saks. On online labeling with polynomially many labels. In preparation, 2012.Google Scholar
- Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In ESA, pages 152--164, 2002. Google ScholarDigital Library
- Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. Cache-oblivious B-trees. SIAM J. Comput., 35(2):341--358, 2005. Google ScholarDigital Library
- Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms, 53(2):115--136, 2004. Google ScholarDigital Library
- Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache oblivious search trees via binary trees of small height. In SODA, pages 39--48, 2002. Google ScholarDigital Library
- Richard S. Bird and Stefan Sadnicki. Minimal on-line labelling. Inf. Process. Lett., 101(1):41--45, 2007. Google ScholarDigital Library
- Paul F. Dietz, Joel I. Seiferas, and Ju Zhang. A tight lower bound for online monotonic list labeling. SIAM J. Discrete Math., 18(3):626--637, 2004. Google ScholarDigital Library
- Paul F. Dietz, Joel I. Seiferas, and Ju Zhang. Lower bounds for smooth list labeling. Manuscript, 2005. (Listed in the references of Dietz-SIAM).Google Scholar
- Paul F. Dietz and Ju Zhang. Lower bounds for monotonic list labeling. In SWAT, pages 173--180, 1990. Google ScholarDigital Library
- Yuval Emek and Amos Korman. New bounds for the controller problem. Distributed Computing, 24(3--4):177--186, 2011.Google Scholar
- Alon Itai, Alan G. Konheim, and Michael Rodeh. A sparse table implementation of priority queues. In ICALP, pages 417--431, 1981. Google ScholarDigital Library
- Amos Korman and Shay Kutten. Controller and estimator for dynamic networks. In PODC, pages 175--184, 2007. Google ScholarDigital Library
- Dan E. Willard. A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Inf. Comput., 97(2):150--204, 1992. Google ScholarDigital Library
- Ju Zhang. Density Control and On-Line Labeling Problems. PhD thesis, University of Rochester, 1993.Google Scholar
Index Terms
- Tight lower bounds for the online labeling problem
Recommendations
Tight Lower Bounds for the Online Labeling Problem
We consider the file maintenance problem (also called the online labeling problem) in which $n$ integer items from the set $\{1,\ldots,r\}$ are to be stored in an array of size $m \geq n$. The items are presented sequentially in an arbitrary order, and ...
On Online Labeling with Large Label Set
In the online labeling problem with parameters $n$ and $m$ we are presented with a sequence of $n$ items from a totally ordered universe $U$ and must assign each arriving item a label from the label set $\left\{1,\ldots,m\right\}$ so that the order of ...
Tight Bounds for Adopt-Commit Objects
We give matching upper and lower bounds of $\varTheta(\min(\frac{\log m}{\log \log m},\, n))$ for the individual step complexity of a wait-free m -valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is deterministic, the lower bound ...
Comments