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.
Type de document :
[Research Report] RR-1990, INRIA. 1993
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:05:07
Dernière modification le : samedi 27 janvier 2018 - 01:31:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:21:54



  • 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〉



Consultations de la notice


Téléchargements de fichiers