{"id":12935,"date":"2021-11-30T19:15:24","date_gmt":"2021-12-01T00:15:24","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12935"},"modified":"2021-11-30T19:15:24","modified_gmt":"2021-12-01T00:15:24","slug":"tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/","title":{"rendered":"TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-97-07
\nMay 1997<\/p>\n

TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps *<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
B. John Oommen & Juan Dong<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

t-A common drawback to all the reported self-organizing sequeI_!.tial search algorithms is that they all fail to consider the size of the list when reorganizing it. The two extremes are the well-known and most commonly analyzed algorithms, the move-to-front rule and the transposition rule. This paper presents two new memory\u00adfree self-organizing sequential search algorithms, both of which overcome this draw\u00adback. The first algorithm is called swap-with-parent (SWP) and the second is called move-to-parent (MTP). Under the swap-with-parent heuristic, the accessed record is exchanged with its “parent” ( considering the list as a heap structure with no ordering constraints between parents and their children) and all the other records are untouched. whereas under the move-to-parent heuristic, the accessed record is moved to its parent’s positions and all the records in between get shifted back one position. It is shown that under the SWP heuristic, the Markov chain representing the scheme is time reversible. This property allows us to derive its asymptotic equi\u00adlibrium probabilities a rather complicated expression for its average search cost. We conjecture that it costs no more than the move-to-front rule and its convergence is intermediate to the move-to-front rule and the transposition rule. For the perfor\u00admance of the move-to-parent rule, empirical comparison shows that it lies between the move-to-front heuristic and the transposition heuristic, and that it is better than the swap-with-parent rule.<\/p>\n

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

Carleton University Technical Report TR-97-07 May 1997 TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps * B. John Oommen & Juan Dong Abstract t-A common drawback to all the reported self-organizing sequeI_!.tial search algorithms is that they all fail to consider the size of the list when reorganizing it. The […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12157,"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-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-97-07 May 1997 TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses\" \/>\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-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/\" \/>\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-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/\",\"name\":\"TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-01T00:15:24+00:00\",\"dateModified\":\"2021-12-01T00:15:24+00:00\",\"description\":\"Carleton University Technical Report TR-97-07 May 1997 TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/#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 1997\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps\"}]},{\"@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-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps - School of Computer Science","description":"Carleton University Technical Report TR-97-07 May 1997 TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses","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-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/","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-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/","name":"TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-01T00:15:24+00:00","dateModified":"2021-12-01T00:15:24+00:00","description":"Carleton University Technical Report TR-97-07 May 1997 TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-07-the-swap-with-parent-scheme-a-self-organizing-sequential-search-algorithm-which-uses-non-lexicograhic-heaps\/#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 1997","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/"},{"@type":"ListItem","position":5,"name":"TR-97-07: The Swap-with-Parent Scheme: A Self-Organizing Sequential Search Algorithm which Uses Non-lexicograhic Heaps"}]},{"@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\/12935"}],"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=12935"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12935\/revisions"}],"predecessor-version":[{"id":12936,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12935\/revisions\/12936"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12157"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12935"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}