###
A. Ferreira, C. Kenyon, A. Rau-Chaplin, and S. Ubeda, "Scalable
Algorithms for d-Dimensional Range Search on Coarse Grained Multicomputers,"
1996.

###
Abstract

The range tree is a fundamental data structure for multi-dimensional
point sets, and as such, is central in a wide range of geometric and
database applications.
In this paper, we describe
the first non-trivial 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^{d-1} n$ is the
size of the sequential data structure and $T_{c}(s,p)$ is the time to
perform an h-relations 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 associative-function 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.

Home* Publications