HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On the multisearching problem for hypercubes

Abstract : We build on the work of Dehne and Rau-Chaplin and give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q'. This problem is fundamental in computational geometry, for example it models planar point location in a slab. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S and a set Q of n queries and we need to find for each query q [??]Q its location in the sorted S. Note that one cannot solve this problem by sorting S[??] Q, because every comparison- based parallel sorting algorithm needs to compare a pair q, q' [??]Q in constant time. We present an improved algorithm for the multisearch problem, one that takes 0(log n(log log n)3) time on a n-processor hypercube. This essentially replaces a logarithmic factor in the time complexities of previous schemes by a (log log n)3 factor. The hypercube model for which we claim our bounds is the standard one, with 0(1) memory registers per processor, and with one-port communication. Each register can store 0(log n) bits, so that a processor knows its ID.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:05:07 PM
Last modification on : Friday, February 4, 2022 - 3:17:36 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:21:54 PM


  • HAL Id : inria-00074682, version 1



Mikhail J. Atallah, Andreas Fabri. On the multisearching problem for hypercubes. [Research Report] RR-1990, INRIA. 1993. ⟨inria-00074682⟩



Record views


Files downloads