---
_id: '4375'
abstract:
- lang: eng
  text: "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.\\\\\r\nThe  network is the same for each dimension, namely a distance
    halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe
    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.\r\nFurthermore,
    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.\r\nOur algorithms
    are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers."
author:
- first_name: Markus
  full_name: Benter, Markus
  last_name: Benter
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
- first_name: Jannik
  full_name: Sundermeier, Jannik
  id: '38705'
  last_name: Sundermeier
citation:
  ama: '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>'
  apa: 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>
  bibtex: '@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} }'
  chicago: 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>.
  ieee: 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.
  mla: 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>.
  short: '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.'
conference:
  end_date: 2018-08-21
  location: Helsinki
  name: 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
  start_date: 2018-08-20
date_created: 2018-09-11T05:26:59Z
date_updated: 2022-01-06T07:01:00Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-19759-9_4
file:
- access_level: closed
  content_type: application/pdf
  creator: tillk
  date_created: 2018-11-27T10:03:33Z
  date_updated: 2018-11-27T10:03:33Z
  file_id: '5863'
  file_name: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
    of arbitrary Dimension.pdf
  file_size: 1122875
  relation: main_file
  success: 1
file_date_updated: 2018-11-27T10:03:33Z
has_accepted_license: '1'
keyword:
- Distributed Storage
- Multi-Dimensional Range Queries
- Peer-to-Peer
- Hilbert Curve
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 4th International Symposium on Algorithmic Aspects
  of Cloud Computing (ALGOCLOUD)
status: public
title: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
  Dimension
type: conference
user_id: '14955'
year: '2018'
...