{"id":12633,"date":"2021-11-14T20:28:59","date_gmt":"2021-11-15T01:28:59","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12633"},"modified":"2021-11-14T20:28:59","modified_gmt":"2021-11-15T01:28:59","slug":"tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/","title":{"rendered":"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-124<\/strong>
\nOctober 1987<\/p>\n

Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies<\/h2>\n
\n
\n
B.J. Oommen, E.R. Hansen , J.I. Munro<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

Let lt = {R1 ,R2, … , AN} be a list of elements in which Ai is accessed with an (unknown) probability Si. To minimize the cost of accessing the elements, it is advantageous if the elements are sorted in the descending order of the access probabilities. Attempts to achieve this have been made in which a simple list reordering operation is performed on every access.
\nIn this paper we present two simple self-organizing strategies. The strategies are deterministic and absorbing in their Markovian representation and are completely counter-intuitive, in that they are of a Move-To-Rear (MTR) flavour. Whereas the first of the schemes requires linear space (space proportional to the number of elements in the list}, the second requires only constant space. We show that the former scheme is optimal, independent of the distribution of the access probabilities. By this we mean that although the list could converge to one of its N! configurations, by suitably performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired. The second scheme requiring constant space is shown to be expedient. We conjecture its optimality.<\/p>\n<\/div>\n

TR-124.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R. Hansen , J.I. Munro Abstract Let lt = {R1 ,R2, … , AN} be a list of elements in which Ai is accessed with an (unknown) probability Si. To minimize the cost of accessing the elements, it […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/\",\"name\":\"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-15T01:28:59+00:00\",\"dateModified\":\"2021-11-15T01:28:59+00:00\",\"description\":\"Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R.\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1987\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies - School of Computer Science","description":"Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/","name":"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-15T01:28:59+00:00","dateModified":"2021-11-15T01:28:59+00:00","description":"Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R.","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1987","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/"},{"@type":"ListItem","position":5,"name":"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12633"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633\/revisions"}],"predecessor-version":[{"id":12634,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633\/revisions\/12634"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11827"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}