conference paper Markus Benter author Till Knollmann author 392410000-0003-2014-4696 Friedhelm Meyer auf der Heide author 15523 Alexander Setzer author 11108 Jannik Sundermeier author 38705 63 department 79 department 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) SFB 901 project SFB 901 - Project Area A project SFB 901 - Subproject A1 project 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. https://ris.uni-paderborn.de/download/4375/5863/A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.pdf application/pdf 2018Helsinki eng Distributed StorageMulti-Dimensional Range QueriesPeer-to-PeerHilbert Curve 10.1007/978-3-030-19759-9_4 Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018. <a href="https://doi.org/10.1007/978-3-030-19759-9_4">https://doi.org/10.1007/978-3-030-19759-9_4</a>. M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier, in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), 2018. Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In: <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. ; 2018. doi:<a href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a> @inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018, title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension}, DOI={<a href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a>}, booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik}, year={2018} } Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018, doi:<a href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a>. Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., &#38; Sundermeier, J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. Helsinki. <a href="https://doi.org/10.1007/978-3-030-19759-9_4">https://doi.org/10.1007/978-3-030-19759-9_4</a> M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier, “A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension,” in <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, Helsinki, 2018. 43752018-09-11T05:26:59Z2022-01-06T07:01:00Z