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 :
Reports
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102047
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:50 AM
Last modification on : Thursday, November 21, 2019 - 2:38:39 AM

File

RR1996-23.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102047, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

17

Files downloads

53