List Update with Locality of Reference | SpringerLink
Skip to main content
Springer Nature Link
Log in

List Update with Locality of Reference

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

It is known that in practice, request sequences for the list update problem exhibit a certain degree of locality of reference. Motivated by this observation we apply the locality of reference model for the paging problem due to Albers et al. [STOC 2002/JCSS 2005] in conjunction with bijective analysis [SODA 2007] to list update. Using this framework, we prove that Move-to-Front (MTF) is the unique optimal algorithm for list update. This addresses the open question of defining an appropriate model for capturing locality of reference in the context of list update [Hester and Hirschberg ACM Comp. Surv. 1985]. Our results hold both for the standard cost function of Sleator and Tarjan [CACM 1985] and the improved cost function proposed independently by Martínez and Roura [TCS 2000] and Munro [ESA 2000]. This result resolves an open problem of Martínez and Roura, namely proposing a measure which can successfully separate MTF from all other list-update algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing 27(3), 682–693 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  2. Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. Journal of Computer and System Sciences 70(2), 145–175 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Albers, S., Mitzenmacher, M.: Average case analyses of list update algorithms, with applications to data compression. Algorithmica 21(3), 312–329 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Albers, S., von Stengel, B., Werchner, R.: A combined bit and timestamp algorithm for the list update problem. Information Processing Letters 56, 135–139 (1995)

    Article  MATH  Google Scholar 

  5. Albers, S., Westbrook, J.: Self-organizing data structures. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol. 1442, pp. 13–51. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  6. Angelopoulos, S., Dorrigiv, R., López-Ortiz, A.: On the separation and equivalence of paging strategies. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 229–237 (2007)

    Google Scholar 

  7. Bachrach, R., El-Yaniv, R.: Online list accessing algorithms and their applications: Recent empirical evidence. In: Proc. 8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 1997), pp. 53–62 (1997)

    Google Scholar 

  8. 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)

    Google Scholar 

  9. Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica 11, 73–91 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  10. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  11. Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. In: Proceedings of the 5th Italian Conference on Algorithms and Complexity (2003)

    Google Scholar 

  12. Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, DEC SRC (1994)

    Google Scholar 

  13. Dorrigiv, R., López-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News (ACM Special Interest Group on Automata and Computability Theory) 36(3), 67–81 (2005)

    Google Scholar 

  14. El-Yaniv, R.: There are infinitely many competitive-optimal online list accessing algorithms (manuscript, 1996)

    Google Scholar 

  15. Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Computing Surveys 17(3), 295 (1985)

    Article  Google Scholar 

  16. Irani, S.: Two results on the list update problem. Information Processing Letters 38, 301–306 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of burrows-wheeler based compression. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 282–293. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  18. Martínez, C., Roura, S.: On the competitiveness of the move-to-front rule. Theoretical Computer Science 242(1–2), 313–325 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  19. Munro, J.I.: On the competitiveness of linear search. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 338–345. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  20. Reingold, N., Westbrook, J., Sleator, D.: Randomized competitive algorithms for the list update problem. Algorithmica 11, 15–32 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  21. Schulz, F.: Two new families of list update algorithms. In: Chwa, K.-Y., H. Ibarra, O. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 99–108. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  22. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28, 202–208 (1985)

    Article  MathSciNet  Google Scholar 

  23. Torng, E.: A unified analysis of paging and caching. Algorithmica 20(2), 175–200 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  24. I. H. Witten and T. Bell. The Calgary/Canterbury text compression corpus. Anonymous ftp from: ftp.cpsc.ucalgary.ca/pub/text.compression/corpus/text.compression.corpus.tar.Z

Download references

Author information

Authors and Affiliations

  1. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ont., N2L 3G1, Canada

    Spyros Angelopoulos, Reza Dorrigiv & Alejandro López-Ortiz

  2. Max-Planck-Institut für Informatic, Saarbrücken, Germany

    Spyros Angelopoulos

Authors
  1. Spyros Angelopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Reza Dorrigiv
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alejandro López-Ortiz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Angelopoulos, S., Dorrigiv, R., López-Ortiz, A. (2008). List Update with Locality of Reference. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_35

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_35

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics