10.1007/978-3-030-19759-9_4
Benter, Markus
Markus
Benter
Knollmann, Till
Till
Knollmann0000-0003-2014-4696
Meyer auf der Heide, Friedhelm
Friedhelm
Meyer auf der Heide
Setzer, Alexander
Alexander
Setzer
Sundermeier, Jannik
Jannik
Sundermeier
A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension
2018
2018-09-11T05:26:59Z
2020-05-07T05:25:34Z
conference
https://ris.uni-paderborn.de/record/4375
https://ris.uni-paderborn.de/record/4375.json
1122875 bytes
application/pdf
We present a peer-to-peer network that supports the efficient processing of orthogonal range queries $R=\bigtimes_{i=1}^{d}[a_i,\,b_i]$ 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.