{"id":14928,"date":"2022-06-13T17:34:41","date_gmt":"2022-06-13T21:34:41","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14928"},"modified":"2026-06-02T14:59:21","modified_gmt":"2026-06-02T18:59:21","slug":"tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/","title":{"rendered":"TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer"},"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-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer\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-1991\/\">Technical Report<\/a> <strong>TR-187<\/strong><br>\nFebruary 1991<\/p>\n\n\n\n<h2 id=\"multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\" class=\"wp-block-heading tr_t1\">Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Mikhail J. Atallah, Frank Dehne, Russ Miller, Andrew Rau-Chaplin, Jyh-Jong Tsay<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>The multisearch problem consists of efficiently performing 0( n) search processes on a data structure modeled as a graph G with n constant-degree nodes. Denote by r the length of the longest search path associated with a search process, and assume that the paths are determined &#8220;on-line&#8221;. In this<br>\npaper, we solve the multisearch problem in 0( fa+ r 1o1,.) time on a fa x Jn mesh-connected computer. For most data structures, the search path traversed when answering one search query has<br>\nlength r = 0(log n). For these cases, our algorithm processes 0( n) such queries in asymptotically optimal time, 0( Jn). The classes of graphs considered contain most of the important data structures that arise in practice (ranging from simple trees to Kirkpatrick hierarchical search DAGs).<br>\nMultisearch is a useful abstraction that models many specific problems and can be used to im\u00adplement parallel data structures on a mesh. As example applications, we consider interval trees and the related multiple interval intersection search, as well as hierarchical representations of polyhedra and its myriads of applications ( e.g., lines-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-187.pdf\">TR-187.pdf<\/a><\/p>\n\n\n\n<p>&nbsp;<\/p>\n\n\n\n<p>&nbsp;<\/p>\n\n\n\n<div class=\"notranslate\" style=\"all: initial;\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-187 February 1991 Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer Mikhail J. Atallah, Frank Dehne, Russ Miller, Andrew Rau-Chaplin, Jyh-Jong Tsay Abstract The multisearch problem consists of efficiently performing 0( n) search processes on a data structure modeled as a graph G with n constant-degree nodes. Denote by [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11908,"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-14928","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14928","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=14928"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14928\/revisions"}],"predecessor-version":[{"id":14929,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14928\/revisions\/14929"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11908"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14928"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14928"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}