Skip to Main content Skip to Navigation

d-Dimensional Range Search on Multicomputers

Abstract : 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).
Document type :
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:50 AM
Last modification on : Thursday, November 12, 2020 - 2:30:10 PM


Files produced by the author(s)


  • HAL Id : hal-02102047, version 1



Afonso Ferreira, Claire Kenyon, Andrew Rau-Chaplin, Stephane Ubeda. d-Dimensional Range Search on Multicomputers. [Research Report] LIP RR-1996-23, Laboratoire de l'informatique du parallélisme. 1996, 2+18p. ⟨hal-02102047⟩



Record views


Files downloads