Startseite > Publikationen > Publikationen

Publikationen

Benter, Markus;Knollmann, Till;Meyer auf der Heide, Friedhelm;Setzer, Alexander;Castenow, Jannik:

A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.

In: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) (accepted), 20. - 21. Aug. 2018

Abstract

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.

Bibtex

@inproceedings{hniid=9775,
author = {Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Castenow, Jannik},
title = {A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension},
booktitle = {Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) (accepted)},
month = {20~-~21~} # aug,
year = {2018},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/9775