d-Dimensional Range Search on Multicomputers

Given a set $L$ of $n$ points in the $d$-dimensional Cartesian space $E^d$, and a query specifying a domain $q$ in $E^d$, the Range Search problem consists in identifying the subset $R(q)$ of the points of $L$ contained in $q$. The Range Tree data-structure represents a particularly good balance between storage space and search time. The structure requires $O(n\log^{d-1} n)$ space and construction time, but supports an $O(\log^dn)$ time search algorithm. In this paper, we describe a set of efficient scalable algorithms for the construction and manipulation of a distributed analog to the sequential range tree data structure. We then show how to perform $O(n)$ independent range searches on a distributed range tree, in parallel. These parallel construction and search algorithms are both optimal in the {\em Coarse Grained Multicomputer} model (also referred to as the weak-CREW BSP model), in the sense that their running times are the sequential time divided by the number of processors, plus a constant number of parallel communication rounds (i.e., h-relations in BSP context).Prenons un ensemble de $n$ points dans un espace cartésien $E^d$, ainsi qu'une requête $q$ définissant un domaine de $E^d$. On appelle {\em Range Search} le problème consistant à identifier le sous-ensemble $r(q)$ de points de $L$ contenu dans $q$. Le {\em Range Tree} est une structure de données offrant un excellent compromis entre la taille mémoire nécessaire à son stockage et le temps de réponse au problème. Il nécessite $O(n \log^{d-1} n)$ emplacements mémoire et permet de traiter une requête en $O(\log^dn)$ unités de temps. Dans cet article, nous présentons des algorithmes efficaces et extensibles pour construire et manipuler une version distribuée du {\em Range Tree} comparable à la version séquentielle. Nous montrons comment répondre à $O(n)$ requêtes indépendantes en parallèle. Les algorithmes de construction du {\em Range Tree} distribué et de réponses aux requêtes sont optimaux dans le modèle de machine à gros grains (aussi appelé modèle weak CREW-BSP), optimal signifiant que le temps d'exécution en parallèle est égal au temps d'exécution en séquentiel divisé par le nombre de processeurs, auquel on doit ajouter le temps nécessaire à un nombre constant d'étapes de communication (ou de {\em h-relations} dans le contexte du modèle BSP)