{"id":12629,"date":"2021-11-14T20:20:03","date_gmt":"2021-11-15T01:20:03","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12629"},"modified":"2021-11-14T20:20:03","modified_gmt":"2021-11-15T01:20:03","slug":"tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/","title":{"rendered":"TR-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-121<\/strong>
\nOctober 1987<\/p>\n

n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors<\/h2>\n
\n
Frank Dehne & Ivan Stojmenovic<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

[1] presented an optimal O(‘Jn} time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a Mesh-of\u00adProcessors of size n. However, it remained an open problem whether such an optimal solution exists for the d-dimensional ECDF searching problem for d4.
\nIn this paper we solve this problem by presenting an optimal O(“-Jri} time parallel solution to the d-dimensional ECDF searching problem for arbitrary dimension d= 0(1} on a Mesh-of-Processors of size n.
\nThe algorithm has several interesting implications. Among others the following problems can now be solved on a Mesh-of-Processors in (asymptotically optimal} time O(‘Jn} for arbitrary dimension d=0(1}: the d-dimensional maximal element determination problem, the d-dimensional hypercube containment counting problem, and the d-dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2d-dimensional ECDF searching problem but require an efficient solution to this problem for at least d4.<\/p>\n<\/div>\n

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

Carleton University Technical Report TR-121 October 1987 n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors Frank Dehne & Ivan Stojmenovic Abstract [1] presented an optimal O(‘Jn} time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a Mesh-of\u00adProcessors […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11827,"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-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-121 October 1987 n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors\" \/>\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-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/\" \/>\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-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/\",\"name\":\"TR-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-15T01:20:03+00:00\",\"dateModified\":\"2021-11-15T01:20:03+00:00\",\"description\":\"Carleton University Technical Report TR-121 October 1987 n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/#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 1987\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors\"}]},{\"@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-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors - School of Computer Science","description":"Carleton University Technical Report TR-121 October 1987 n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors","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-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/","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-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/","name":"TR-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-15T01:20:03+00:00","dateModified":"2021-11-15T01:20:03+00:00","description":"Carleton University Technical Report TR-121 October 1987 n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-121-n-o-n-algorithm-for-the-ecdf-searching-problem-for-arbitrary-dimensions-on-a-mesh-of-processors\/#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 1987","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/"},{"@type":"ListItem","position":5,"name":"TR-121: n O(\u221an) Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors"}]},{"@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\/12629"}],"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=12629"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12629\/revisions"}],"predecessor-version":[{"id":12630,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12629\/revisions\/12630"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11827"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12629"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}