Scalable Algorithms for dDimensional Range Search on Coarse Grained Multicomputers. 

A. Ferreira, C. Kenyon, A. RauChaplin, and S. Ubeda 

Abstract: The range tree is a fundamental data structure for multidimensional point sets, and as such, is central in a wide range of geometric and database applications. In this paper, we describe the first nontrivial adaptation of range trees to the parallel distributed memory setting (BSP like models). Given a set $L$ of $n$ points in $d$dimensional Cartesian space, we show how to construct on a coarse grained multicomputer a distributed range tree $T$ in time $O(\frac{s}{p} + T_{c}(s,p))$, where $s = n \log^{d1} n$ is the size of the sequential data structure and $T_{c}(s,p)$ is the time to perform an hrelations with $h=\Theta (s/p)$. We then show how $T$ can be used to answer a given set $Q$ of $m = O(n)$ range queries in time O($\frac{s\log n}{p} + T_{c}(s,p)$) and O($\frac{s\log n}{p} + T_{c}(s,p) + \frac{k}{p}$), for the associativefunction and report modes respectively, where $k$ is the number of results to be reported. These parallel construction and search algorithms are both highly efficient, in that their running times are the sequential time divided by the number of processors, plus a constant number of parallel communication rounds. 

paper.pdf 
paper.ps 

