A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.

We present a peer-to-peer network that supports the efficient processing of orthogonal range queries Open image in new window in a d-dimensional point space. The network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG’07). We show how to execute such range queries using \(\mathcal {O}\left( 2^{d'}d\,\log m + d\,|R|\right) \) hops (and the same number of messages) in total. Here \([m]^d\) is the ground set, |R| is the size and \(d'\) the dimension of the queried range. Furthermore, if the peers form a distributed network, the query can be answered in \(\mathcal {O}\left( d\,\log m + d\,\sum _{i=1}^{d}(b_i-a_i+1)\right) \) communication rounds. Our algorithms are based on a mapping of the Hilbert Curve through \([m]^d\) to the peers.