Abstract
The list update problem was first studied by McCabe [47] more than 45 years ago under distributional analysis in the context of maintaining a sequential file. In 1985, Sleator and Tarjan [55] introduced the competitive ratio framework for the study of worst case behavior on list update algorithms. Since then, many deterministic and randomized online algorithms have been proposed and studied under this framework. The standard model as originally introduced has a peculiar cost function for the rearrangement of the list after each search operation. To address this, several variants have been introduced, chiefly the MRM model (Martínez and Roura, [46]; Munro, [49]), the paid exchange model, and the compression model. Additionally, the list update problem has been studied under locality of reference assumptions, and several models have been proposed to capture locality of input sequences. This survey gives a brief overview of the main list update algorithms, the main alternative cost models, and the related results for list update with locality of reference. Open problems and directions for future work are included.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27, 682–693 (1998)
Albers, S.: Online algorithms: a survey. Math. Program. 97(1-2), 3–26 (2003)
Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. J. Comput. Systems Sci. 70(2), 145–175 (2005)
Albers, S., Lauer, S.: On list update with locality of reference. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 96–107. Springer, Heidelberg (2008)
Albers, S., Mitzenmacher, M.: Average case analyses of list update algorithms, with applications to data compression. Algorithmica 21(3), 312–329 (1998)
Albers, S., von Stengel, B., Werchner, R.: A combined BIT and TIMESTAMP algorithm for the list update problem. Inform. Process. Lett. 56, 135–139 (1995)
Albers, S., Westbrook, J.: Self-organizing data structures. In: Fiat, A. (ed.) Online Algorithms 1996. LNCS, vol. 1442, pp. 13–51. Springer, Heidelberg (1998)
Ambühl, C.: Offline list update is NP-hard. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 42–51. Springer, Heidelberg (2000)
Ambühl, C., Gärtner, B., von Stengel, B.: Optimal projective algorithms for the list update problem. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 305–316. Springer, Heidelberg (2000)
Ambühl, C., Gärtner, B., von Stengel, B.: A new lower bound for the list update problem in the partial cost model. Theoret. Comput. Sci. 268, 3–16 (2001)
Ambühl, C., Gärtner, B., von Stengel, B.: Optimal projective algorithms for the list update problem. CoRR, abs/1002.2440 (2010)
Angelopoulos, S., Dorrigiv, R., López-Ortiz, A.: On the separation and equivalence of paging strategies. In: Proc. 18th Symp. on Discrete Algorithms (SODA), pp. 229–237 (2007)
Angelopoulos, S., Dorrigiv, R., López-Ortiz, A.: List update with locality of reference. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 399–410. Springer, Heidelberg (2008)
Angelopoulos, S., Schweitzer, P.: Paging and list update under bijective analysis. In: Proc. 20th Symp. on Discrete Algorithms (SODA), pp. 1136–1145 (2009)
Bachrach, R., El-Yaniv, R.: Online list accessing algorithms and their applications: Recent empirical evidence. In: Proc. 8th Symp. on Discrete Algorithms (SODA), pp. 53–62 (1997)
Bachrach, R., El-Yaniv, R., Reinstadtler, M.: On the competitive theory and practice of online list accessing algorithms. Algorithmica 32(2), 201–245 (2002)
Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 98–109. Springer, Heidelberg (2004)
Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica 11, 73–91 (1994)
Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11, 2–14 (1994)
Bentley, J.L., Sleator, D., Tarjan, R.E., Wei, V.K.: A locally adaptive data compression scheme. Commun. ACM 29, 320–330 (1986)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Systems Sci. 50, 244–258 (1995)
Boyar, J., Favrholdt, L.M.: The relative worst order ratio for online algorithms. ACM Trans. Algorithms 3(2) (2007)
Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst-order ratio applied to paging. J. Comput. Systems Sci. 73(5), 818–843 (2007)
Boyar, J., Gupta, S., Larsen, K.S.: Access graphs results for LRU versus FIFO under relative worst order analysis. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 328–339. Springer, Heidelberg (2012)
Boyar, J., Medvedev, P.: The relative worst order ratio applied to seat reservation. ACM Trans. Algorithms 4(4) (2008)
Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, DEC SRC (1994)
Chrobak, M., Noga, J.: LRU is better than FIFO. Algorithmica 23(2), 180–185 (1999)
Denning, P.J.: The working set model for program behaviour. Commun. ACM 11(5), 323–333 (1968)
Denning, P.J.: Working sets past and present. IEEE Trans. Softw. Eng. 6, 64–84 (1980)
Dorrigiv, R., López-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36, 67–81 (2005)
Dorrigiv, R., López-Ortiz, A., Munro, J.I.: An application of self-organizing data structures to compression. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 137–148. Springer, Heidelberg (2009)
Ehmsen, M.R., Kohrt, J.S., Larsen, K.S.: List factoring and relative worst order analysis. Algorithmica 66(2), 287–309 (2013)
El-Yaniv, R.: There are infinitely many competitive-optimal online list accessing algorithms. Manuscript (1996)
Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Separating online scheduling algorithms with the relative worst order ratio. J. Comb. Optim. 12(4), 363–386 (2006)
Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Comparing online algorithms for bin packing problems. J. Sched. 15(1), 13–21 (2012)
Golynski, A., López-Ortiz, A.: Optimal strategies for the list update problem under the MRM alternative cost model. Inform. Process. Lett. 112(6), 218–222 (2012)
Hagerup, T.: Online and offline access to short lists. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 691–702. Springer, Heidelberg (2007)
Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Computing Surveys 17, 295–312 (1985)
Irani, S.: Two results on the list update problem. Inform. Process. Lett. 38, 301–306 (1991)
Irani, S., Karlin, A.R., Phillips, S.: Strongly competitive algorithms for paging with locality of reference. SIAM J. Comput. 25, 477–497 (1996)
Irani, S., Reingold, N., Sleator, D., Westbrook, J.: Randomized competitive algorithms for the list update problem. In: Proc. 2nd Symp. on Discrete Algorithms (SODA), pp. 251–260 (1991)
Kamali, S., Ladra, S., López-Ortiz, A., Seco, D.: Context-based algorithms for the list-update problem under alternative cost models. In: Proc. Data Compression Conf., (DCC) (to appear, 2013)
Karlin, A., Phillips, S., Raghavan, P.: Markov paging. In: Proc. 33rd Symp. on Foundations of Computer Science (FOCS), pp. 208–217 (1992)
Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for online problems. In: Proc. 20th Symp. on Theory of Computing (STOC), pp. 322–333 (1988)
Martínez, C., Roura, S.: On the competitiveness of the move-to-front rule. Theoret. Comput. Sci. 242(1-2), 313–325 (2000)
McCabe, J.: On serial files with relocatable records. Oper. Res. 12, 609–618 (1965)
Mohanty, R., Narayanaswamy, N.S.: Online algorithms for self-organizing sequential search - a survey. Elect. Coll. on Comput. Complexity 16, 97 (2009)
Munro, J.I.: On the competitiveness of linear search. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 338–345. Springer, Heidelberg (2000)
Reingold, N., Westbrook, J.: Randomized algorithms for the list update problem. Technical Report YALEU/DCS/TR-804, Yale University (1990)
Reingold, N., Westbrook, J.: Off-line algorithms for the list update problem. Inform. Process. Lett. 60(2), 75–80 (1996)
Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica 11, 15–32 (1994)
Rivest, R.: On self-organizing sequential search heuristics. Commun. ACM 19, 63–67 (1976)
Schulz, F.: Two new families of list update algorithms. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 99–108. Springer, Heidelberg (1998)
Sleator, D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202–208 (1985)
Teia, B.: A lower bound for randomized list update algorithms. Inform. Process. Lett. 47, 5–9 (1993)
Torng, E.: A unified analysis of paging and caching. Algorithmica 20(2), 175–200 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kamali, S., López-Ortiz, A. (2013). A Survey of Algorithms and Models for List Update. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds) Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40273-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-40273-9_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40272-2
Online ISBN: 978-3-642-40273-9
eBook Packages: Computer ScienceComputer Science (R0)