{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:29:38Z","timestamp":1725506978374},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_35","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"399-410","source":"Crossref","is-referenced-by-count":17,"title":["List Update with Locality of Reference"],"prefix":"10.1007","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[]},{"given":"Reza","family":"Dorrigiv","sequence":"additional","affiliation":[]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/S0097539794277858","volume":"27","author":"S. Albers","year":"1998","unstructured":"Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing\u00a027(3), 682\u2013693 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"35_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2004.08.002","volume":"70","author":"S. Albers","year":"2005","unstructured":"Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. Journal of Computer and System Sciences\u00a070(2), 145\u2013175 (2005)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"35_CR3","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/PL00009217","volume":"21","author":"S. Albers","year":"1998","unstructured":"Albers, S., Mitzenmacher, M.: Average case analyses of list update algorithms, with applications to data compression. Algorithmica\u00a021(3), 312\u2013329 (1998)","journal-title":"Algorithmica"},{"key":"35_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","volume":"56","author":"S. Albers","year":"1995","unstructured":"Albers, S., von Stengel, B., Werchner, R.: A combined bit and timestamp algorithm for the list update problem. Information Processing Letters\u00a056, 135\u2013139 (1995)","journal-title":"Information Processing Letters"},{"key":"35_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0029563","volume-title":"Online Algorithms: The State of the Art","author":"S. Albers","year":"1998","unstructured":"Albers, S., Westbrook, J.: Self-organizing data structures. In: Fiat, A. (ed.) Dagstuhl Seminar 1996. LNCS, vol.\u00a01442, pp. 13\u201351. Springer, Heidelberg (1998)"},{"key":"35_CR6","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-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\u2013237 (2007)"},{"key":"35_CR7","unstructured":"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\u201362 (1997)"},{"key":"35_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-540-30140-0_11","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Becchetti","year":"2004","unstructured":"Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 98\u2013109. Springer, Heidelberg (2004)"},{"key":"35_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica\u00a011, 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"35_CR10","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1007\/3-540-44849-7_13"},{"key":"35_CR12","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, DEC SRC (1994)"},{"issue":"3","key":"35_CR13","first-page":"67","volume":"36","author":"R. Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News (ACM Special Interest Group on Automata and Computability Theory)\u00a036(3), 67\u201381 (2005)","journal-title":"SIGACT News (ACM Special Interest Group on Automata and Computability Theory)"},{"key":"35_CR14","unstructured":"El-Yaniv, R.: There are infinitely many competitive-optimal online list accessing algorithms (manuscript, 1996)"},{"issue":"3","key":"35_CR15","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1145\/5505.5507","volume":"17","author":"J.H. Hester","year":"1985","unstructured":"Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Computing Surveys\u00a017(3), 295 (1985)","journal-title":"ACM Computing Surveys"},{"key":"35_CR16","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","volume":"38","author":"S. Irani","year":"1991","unstructured":"Irani, S.: Two results on the list update problem. Information Processing Letters\u00a038, 301\u2013306 (1991)","journal-title":"Information Processing Letters"},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/11780441_26","volume-title":"Combinatorial Pattern Matching","author":"H. Kaplan","year":"2006","unstructured":"Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of burrows-wheeler based compression. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 282\u2013293. Springer, Heidelberg (2006)"},{"issue":"1\u20132","key":"35_CR18","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0304-3975(98)00264-3","volume":"242","author":"C. Mart\u00ednez","year":"2000","unstructured":"Mart\u00ednez, C., Roura, S.: On the competitiveness of the move-to-front rule. Theoretical Computer Science\u00a0242(1\u20132), 313\u2013325 (2000)","journal-title":"Theoretical Computer Science"},{"key":"35_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/3-540-45253-2_31","volume-title":"Algorithms - ESA 2000","author":"J.I. Munro","year":"2000","unstructured":"Munro, J.I.: On the competitiveness of linear search. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 338\u2013345. Springer, Heidelberg (2000)"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N. Reingold","year":"1994","unstructured":"Reingold, N., Westbrook, J., Sleator, D.: Randomized competitive algorithms for the list update problem. Algorithmica\u00a011, 15\u201332 (1994)","journal-title":"Algorithmica"},{"key":"35_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-49381-6_12","volume-title":"Algorithms and Computation","author":"F. Schulz","year":"1998","unstructured":"Schulz, F.: Two new families of list update algorithms. In: Chwa, K.-Y., H. Ibarra, O. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 99\u2013108. Springer, Heidelberg (1998)"},{"key":"35_CR22","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028, 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"issue":"2","key":"35_CR23","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/PL00009192","volume":"20","author":"E. Torng","year":"1998","unstructured":"Torng, E.: A unified analysis of paging and caching. Algorithmica\u00a020(2), 175\u2013200 (1998)","journal-title":"Algorithmica"},{"key":"35_CR24","unstructured":"I.\u00a0H. Witten and T.\u00a0Bell. The Calgary\/Canterbury text compression corpus. Anonymous ftp from: \n \n ftp.cpsc.ucalgary.ca\/pub\/text.compression\/corpus\/text.compression.corpus.tar.Z"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:21:38Z","timestamp":1619522498000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_35","relation":{},"subject":[]}}