{"id":14782,"date":"2022-05-28T20:08:34","date_gmt":"2022-05-29T00:08:34","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14782"},"modified":"2026-06-09T10:59:40","modified_gmt":"2026-06-09T14:59:40","slug":"tr-168-adaptive-list-organizing-for-non-stationary-query-distributions-part-i-the-move-to-front-rule","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-168-adaptive-list-organizing-for-non-stationary-query-distributions-part-i-the-move-to-front-rule\/","title":{"rendered":"TR-168: Adaptive List Organizing for Non-stationary Query Distributions. Part I: The Move-to-Front Rule"},"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-168: Adaptive List Organizing for Non-stationary Query Distributions. Part I: The Move-to-Front Rule\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/\">Technical Report<\/a>&nbsp;<strong>TR-168<\/strong><br>January 1990<\/p>\n\n\n\n<h2 id=\"adaptive-list-organizing-for-non-stationary-query-distributions-part-i-the-move-to-front-rule\" class=\"wp-block-heading\">Adaptive List Organizing for Non-stationary Query Distributions. Part I: The Move-to-Front Rule<\/h2>\n\n\n\n<p>R.S. Valiveti &amp; B.J. Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Consider a linear list \u2018R composed of all the records in the set { R1, R2, \u2022 \u2022 \u2022 , RN }. At a given instant, the records appear in one of the N! permutations of the N elements. It is well known that in order to arrive at the minimum average cost of accesses, the list \u2018R, must be arranged in the decreasing order of probabilities of accessing the elements. Many heuristics to dynamically reorganize the list are known in the literature and include the Move-to-Front (MTF) and the Transposition (TR) rules.<br>The assumption made in all studies of adaptive linear lists has been that the access probability distribution is time invariant, and that the individual accesses are statistically independent. This paper studies the impact of relaxing the time invariance assumption. Two models of non-stationary query distributions are suggested in this paper. The first approach is based on the idea of switching environments [11] and the second model is completely general and allows the probability distribution vector itself to be a random vector.<br>The MTF rule is analyzed under both these models. The theoretical results presented in the paper have been experimentally validated.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-168-1.pdf\">TR-168.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-168January 1990 Adaptive List Organizing for Non-stationary Query Distributions. Part I: The Move-to-Front Rule R.S. Valiveti &amp; B.J. Oommen Abstract Consider a linear list \u2018R composed of all the records in the set { R1, R2, \u2022 \u2022 \u2022 , RN }. At a given instant, the records appear in one of the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11906,"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-14782","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14782","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=14782"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14782\/revisions"}],"predecessor-version":[{"id":24543,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14782\/revisions\/24543"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11906"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14782"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}