{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:46:04Z","timestamp":1742928364775,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_9","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"96-107","source":"Crossref","is-referenced-by-count":21,"title":["On List Update with Locality of Reference"],"prefix":"10.1007","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Sonja","family":"Lauer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"670","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, 670\u2013681 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"9_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, 145\u2013175 (2005)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR3","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":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/3-540-45253-2_5","volume-title":"Algorithms - ESA 2000","author":"C. Amb\u00fchl","year":"2000","unstructured":"Amb\u00fchl, C.: Offline List update is NP-hard. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 42\u201351. Springer, Heidelberg (2000)"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(00)00257-7","volume":"268","author":"C. Amb\u00fchl","year":"2001","unstructured":"Amb\u00fchl, C., G\u00e4rtner, B., von Stengel, B.: A new lower bound for the list update problem in the partial cost model. Theoretical Computer Science\u00a0268, 3\u201316 (2001)","journal-title":"Theoretical Computer Science"},{"key":"9_CR6","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with locality of reference: MTF outperforms all other algorithms. Technical Report CS-2006-46, School of Computer Science, University of Waterloo (2006)"},{"key":"9_CR7","unstructured":"Bachrach, R., El-Yaniv, R.: Online list accessing algorithms and their applications: Recent empirical evidence. In: Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 53\u201362 (1997)"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0069-8","volume":"32","author":"R. Bachrach","year":"2002","unstructured":"Bachrach, R., El-Yaniv, R., Reinst\u00e4dtler, M.: On the competitive theory and practice of online list accessing algorithms. Algorithmica\u00a032, 201\u2013245 (2002)","journal-title":"Algorithmica"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1145\/3341.3349","volume":"28","author":"J.L. Bentley","year":"1985","unstructured":"Bentley, J.L., McGeoch, C.C.: Amortized analyses of self-organizing sequential search heuristics. Communication of the ACM\u00a028, 404\u2013411 (1985)","journal-title":"Communication of the ACM"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1145\/5684.5688","volume":"29","author":"J.L. Bentley","year":"1986","unstructured":"Bentley, J.L., Sleator, D.S., Tarjan, R.E., Wei, V.K.: A locally adaptive data compression scheme. Communications of the ACM\u00a029, 320\u2013330 (1986)","journal-title":"Communications of the ACM"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A. Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. Journal of Computer and System Sciences\u00a050, 244\u2013258 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR12","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. DEC SRC Research Report 124 (1994)"},{"key":"9_CR13","unstructured":"Calgary Corpus, http:\/\/links.uwaterloo.ca\/calgary.corpus.html"},{"key":"9_CR14","unstructured":"The Canterbury Corpus, http:\/\/corpus.canterbury.ac.nz\/"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Fiat, A., Mendel, M.: Truly online paging with locality of reference. In: Proc. 38rd Annual Symposium on Foundations of Computer Science, pp. 326\u2013335 (1997)","DOI":"10.1109\/SFCS.1997.646121"},{"key":"9_CR16","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, 295\u2013312 (1985)","journal-title":"ACM Computing Surveys"},{"key":"9_CR17","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":"9_CR18","doi-asserted-by":"crossref","unstructured":"Karlin, A., Phillips, S., Raghavan, P.: Markov paging. In: Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 24\u201327 (1992)","DOI":"10.1109\/SFCS.1992.267771"},{"key":"9_CR19","unstructured":"Karp, R., Raghavan, P.: Personal communication cisted in [22] (1990)"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Proc. 35th Annual Symposium on Foundations of Computer Science, pp. 394\u2013400 (1994)","DOI":"10.1109\/SFCS.1994.365677"},{"key":"9_CR21","unstructured":"Reingold, N., Westbrook, J.: Optimum off-line algorithms for the list update problem. Technical Report YALEU\/DCS\/TR-805, Yale University (1990)"},{"key":"9_CR22","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.D.: Randomized competitive algorithms for the list update problem. Algorithmica\u00a011, 15\u201332 (1994)","journal-title":"Algorithmica"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/359997.360000","volume":"19","author":"R. Rivest","year":"1976","unstructured":"Rivest, R.: On self-organizing sequential search heuristics. Communications of the ACM\u00a019, 63\u201367 (1976)","journal-title":"Communications of the ACM"},{"key":"9_CR24","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"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:31Z","timestamp":1738325611000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}