{"id":12588,"date":"2021-11-13T17:01:56","date_gmt":"2021-11-13T22:01:56","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12588"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-76-list-organizing-strategies-using-stochastic-move-to-front-and-stochastic-move-to-rear-operations","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1985\/tr-76-list-organizing-strategies-using-stochastic-move-to-front-and-stochastic-move-to-rear-operations\/","title":{"rendered":"TR-76: List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-76: List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1985\/\">Technical Report<\/a> <strong>TR-76<\/strong><br>\nMay 1985<\/p>\n\n\n\n<h2 id=\"list-organizing-strategies-using-stochastic-move-to-front-and-stochastic-move-to-rear-operations\" class=\"wp-block-heading tr_t1\">List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations<\/h2>\n\n\n\n<div class=\"tr_t3\">B. John Oommen<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>Consider a list of elements {R , &#8230; ,RN} in which the element Ri is accessed with an (unknown) probability si. If the cost of accessing R i is proportional to i (as in sequently search) then<br>\nit is advantageous if each access is accompanied by a simple reordering operation. Th is operation is ch osen so that ultimately the list will be sorted in the descending order of the access probabilities.<br>\nIn this paper we present two list organizing schemes &#8212; the first of which uses bounded memory and the second which uses memory proportional to number of elements in the list. Both of the schemes reorder the list by moving only the accessed element. However, as opposed to the schemes discussed in the literature the move operation is performed stochastically in such a way that ultimately no more move operations are performed. When this occurs we say that the scheme has converged. We shall show that:<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-76.pdf\">TR-76.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-76 May 1985 List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations B. John Oommen Abstract Consider a list of elements {R , &#8230; ,RN} in which the element Ri is accessed with an (unknown) probability si. If the cost of accessing R i is proportional to i (as in [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11823,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-12588","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12588","targetHints":{"allow":["GET"]}}],"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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12588"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12588\/revisions"}],"predecessor-version":[{"id":12601,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12588\/revisions\/12601"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11823"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12588"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12588"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}