Advertisement
Published in:
2019 | OriginalPaper | Chapter
A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension
Authors : Markus Benter, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander Setzer, Jannik Sundermeier
Published in: Algorithmic Aspects of Cloud Computing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We present a peer-to-peer network that supports the efficient processing of orthogonal range queries
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.
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.