{"id":12699,"date":"2021-11-15T19:09:35","date_gmt":"2021-11-16T00:09:35","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12699"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-154-ideal-list-organization-for-stationary-environments","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1989\/tr-154-ideal-list-organization-for-stationary-environments\/","title":{"rendered":"TR-154: Ideal List Organization for Stationary Environments"},"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-154: Ideal List Organization for Stationary Environments\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-1989\/\">Technical Report<\/a> <strong>TR-154<\/strong><br>\nMarch 1989<\/p>\n\n\n\n<h2 id=\"ideal-list-organization-for-stationary-environments\" class=\"wp-block-heading tr_t1\">Ideal List Organization for Stationary Environments<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">B. John Oommen &amp; David T.H. Ng<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>We consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We present a strategy which has constant additional space requirements and which achieves the reorganization by performing a data restructuring operation on an element exactly once. The scheme, which is stochastically absorbing, and is of a Move-to-Rear flavour is shown to be asymptotically optimal. In other words, by suitably performing the Move-to-Rear operation the probability of converging to the optimal arrangement can be made as close to unity as desired. Considering all of these features, this strategy is probably the most ideal list organization strategy reported in the literature. Simulation results demonstrating the power of the scheme have been included. The paper also includes a hybrid data reorganization scheme in which an absorbing Move-To-Rear rule and an ergodic rule are used L&#8217;l conjunction with each other to optimize the data retrieval process.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/tr-154.pdf\">TR-154.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-154 March 1989 Ideal List Organization for Stationary Environments B. John Oommen &amp; David T.H. Ng Abstract We consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We present a strategy which has constant additional space requirements and which achieves the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11903,"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":[],"class_list":["post-12699","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12699","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=12699"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12699\/revisions"}],"predecessor-version":[{"id":12700,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12699\/revisions\/12700"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11903"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12699"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12699"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}