Orthogonal Range Search using a Distributed Computing Model
Pouya Bisadi, Bradford G. Nickerson · 2011
We present a novel approach for distributed orthogonal rangesearchonasetofN pointsstoredonnnodes. The non-redundant rainbow skip graph [Goodrich et al [12] is used to coordinate message passing among nodes. We show that the maximum number of levels L in such a graph is L = W(nln2)/ln2, where W is the lambertW function. Experimental validation is performed using 24 nodes, with N = 2.4 × 10 7 points distributed in a uniform random fashion in a [0,1] 2 space. Each node stores an equal number of points, with the distribution ofpointsamongnodescontrolledbypointxcoordinates. The experiments were implemented using the Message Passing Interface (MPI) communication model running on a high performance computer cluster. Our results show that the expected number of messages required to answerapointqueryoriginatingfromanynodematches the theoretical bound of Θ(logn) messages. 1