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 <>
Submitted on : Wednesday, May 24, 2006 - 4:05:07 PM
Last modification on : Saturday, January 27, 2018 - 1:31:05 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