{"id":12937,"date":"2021-11-30T19:18:06","date_gmt":"2021-12-01T00:18:06","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12937"},"modified":"2021-11-30T19:19:05","modified_gmt":"2021-12-01T00:19:05","slug":"tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/","title":{"rendered":"TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists"},"content":{"rendered":"

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

TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists *<\/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

Self organizing linear search algorithms have been in the literature for al\u00admost 30 years, and numerous schemes have been proposed during that time. Among all the previous algorithms, the move-to-front rule and the transposition rule are the most extensively analyzed schemes. Recently we have proposed and thoroughly analyzed a new scheme, the swap-with-parent rule, which views the list as a heap structure with no ordering constraints between parents and their children {15}. From the analyses of the transposition rule and the swap-with-parent rule, it can be seen that the fundamental property of the corresponding Markov chain being time re\u00adversible greatly simplifies the analysis of the algorithm. In this paper, we shall show the existence of a class of time reversible Markov chains resulting from performing swaps on “implicit” tree structures (called ss_trees) which generalize and extend the results concerning the transposition heuristic and the swap-with-parent heuristic.
\nThis paper introduces a generalization of the transposition rule and the swap\u00adwith-parent rule – the swap-with-parent-in-an-ss_tree heuristic and its modification the move-to-parent-in-an-ss_tree heuristic. Detailed expressions for the asymptotic probabilities and the asymptotic search cost of the scheme have been derived.<\/p>\n

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

Carleton University Technical Report TR-97-08 May 1997 TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists * B. John Oommen & Juan Dong Abstract Self organizing linear search algorithms have been in the literature for al\u00admost 30 years, and numerous schemes have been proposed during that time. Among all the previous […]<\/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-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-97-08 May 1997 TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent\" \/>\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-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/\" \/>\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-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/\",\"name\":\"TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-01T00:18:06+00:00\",\"dateModified\":\"2021-12-01T00:19:05+00:00\",\"description\":\"Carleton University Technical Report TR-97-08 May 1997 TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/#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-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists\"}]},{\"@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-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists - School of Computer Science","description":"Carleton University Technical Report TR-97-08 May 1997 TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent","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-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/","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-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/","name":"TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-01T00:18:06+00:00","dateModified":"2021-12-01T00:19:05+00:00","description":"Carleton University Technical Report TR-97-08 May 1997 TR-97-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1997\/tr-97-08-time-reversibility-a-mathematical-tool-for-creating-arbitrary-generalized-swap-parent-self-organizing-lists-2\/#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-08: Time reversibility: a mathematical tool for creating arbitrary generalized swap-parent self-organizing lists"}]},{"@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\/12937"}],"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=12937"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12937\/revisions"}],"predecessor-version":[{"id":12940,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12937\/revisions\/12940"}],"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=12937"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}