{"id":14818,"date":"2022-05-28T20:32:31","date_gmt":"2022-05-29T00:32:31","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14818"},"modified":"2026-06-09T10:28:30","modified_gmt":"2026-06-09T14:28:30","slug":"tr-181-adaptive-linear-list-reorganization-under-a-generalized-query-system","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-181-adaptive-linear-list-reorganization-under-a-generalized-query-system\/","title":{"rendered":"TR-181: Adaptive Linear List Reorganization under a Generalized Query System"},"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-181: Adaptive Linear List Reorganization under a Generalized Query System\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-181<\/strong><br>October 1990<\/p>\n\n\n\n<h2 id=\"adaptive-linear-list-reorganization-under-a-generalized-query-system\" class=\"wp-block-heading\">Adaptive Linear List Reorganization under a Generalized Query System<\/h2>\n\n\n\n<p>R.S. Valiveti, B.J. Oommen , J.R. Zgierski<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>The problem of reorganizing a linear list, when the individual records are accessed indepen\u00addently, has been well studied. In this paper, self-organizing linear list heuristics are examined under a more general query system which allows accesses to any subset of the list of elements. We propose a pragmatic model for the query generator, characterized by a set of parameters of size equal to the number of elements in the list. We derive the distribution of accesses to the individual records of the list, and show that these records are statistically dependent. Throughout this paper, the set accesses are processed by serializing the set elements.<br>We then present extensions to the classical Move-To-Front (MTF) and Transposition (TR) rules under this generalized query generation mechanism. The resulting heuristics are termed MTF _TQS and TR_TQS respectively. Under this query generation model, the opti\u00admal (static) list is shown to be one in which the elements are ordered in the descending order of the total probability of accessing the records. The expected cost under the MTF _TQS heuristic is shown to be no more than 1r \/2 times the mean access cost for the optimal list. We also prove that MTF _TQS and TR_TQS are superior to the simpler reorganization scheme in which the classical MTF or TR heuristics (respectively) is employed in conjunction with the (serial) stream consisting of individual record accesses. Experimental results for these heuristics are also reported.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-181.pdf\">TR-181.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-181October 1990 Adaptive Linear List Reorganization under a Generalized Query System R.S. Valiveti, B.J. Oommen , J.R. Zgierski Abstract The problem of reorganizing a linear list, when the individual records are accessed indepen\u00addently, has been well studied. In this paper, self-organizing linear list heuristics are examined under a more general query system which [&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-14818","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14818","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=14818"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14818\/revisions"}],"predecessor-version":[{"id":24526,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14818\/revisions\/24526"}],"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=14818"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}