{"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":"2022-06-13T17:34:41","modified_gmt":"2022-06-13T21:34:41","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":"

Carleton University
\nTechnical Report<\/a> TR-187<\/strong>
\nFebruary 1991<\/p>\n

Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer<\/h2>\n
\n
Mikhail J. Atallah, Frank Dehne, Russ Miller, Andrew Rau-Chaplin, Jyh-Jong Tsay<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

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 “on-line”. In this
\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
\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).
\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

TR-187.pdf<\/a><\/p>\n

<\/p>\n

<\/p>\n

<\/div>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11908,"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-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-187 February 1991 Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer Mikhail J.\" \/>\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-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/\" \/>\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-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/\",\"name\":\"TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2022-06-13T21:34:41+00:00\",\"dateModified\":\"2022-06-13T21:34:41+00:00\",\"description\":\"Carleton University Technical Report TR-187 February 1991 Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer Mikhail J.\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/#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 1991\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer\"}]},{\"@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-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer - School of Computer Science","description":"Carleton University Technical Report TR-187 February 1991 Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer Mikhail J.","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-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/","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-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/","name":"TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2022-06-13T21:34:41+00:00","dateModified":"2022-06-13T21:34:41+00:00","description":"Carleton University Technical Report TR-187 February 1991 Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer Mikhail J.","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-187-multisearch-techniques-for-implementing-data-structures-on-a-mesh-connected-computer\/#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 1991","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/"},{"@type":"ListItem","position":5,"name":"TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer"}]},{"@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_button":"no","banner_image_type":"none"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14928"}],"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=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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}