  We focus on range query processing on large-scale, typically distributed
infrastructures, such as clouds of thousands of nodes of shared-datacenters, of
p2p distributed overlays, etc. In such distributed environments, efficient
range query processing is the key for managing the distributed data sets per
se, and for monitoring the infrastructure's resources. We wish to develop an
architecture that can support range queries in such large-scale decentralized
environments and can scale in terms of the number of nodes as well as in terms
of the data items stored. Of course, in the last few years there have been a
number of solutions (mostly from researchers in the p2p domain) for designing
such large-scale systems. However, these are inadequate for our purposes, since
at the envisaged scales the classic logarithmic complexity (for point queries)
is still too expensive while for range queries it is even more disappointing.
In this paper we go one step further and achieve a sub-logarithmic complexity.
We contribute the ART, which outperforms the most popular decentralized
structures, including Chord (and some of its successors), BATON (and its
successor) and Skip-Graphs. We contribute theoretical analysis, backed up by
detailed experimental results, showing that the communication cost of query and
update operations is $O(\log_{b}^2 \log N)$ hops, where the base $b$ is a
double-exponentially power of two and $N$ is the total number of nodes.
Moreover, ART is a fully dynamic and fault-tolerant structure, which supports
the join/leave node operations in $O(\log \log N)$ expected w.h.p number of
hops. Our experimental performance studies include a detailed performance
comparison which showcases the improved performance, scalability, and
robustness of ART.
