research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleBrief Announcement: ART: Sub-Logarithmic Decentralized Range Query Processing with Probabilistic Guarantees
Bibtex cite IDRACTI-RU1-2010-38
Booktitle Twenty-Ninth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Year published 2010
Location Zurich, Switzerland
Note to appear
We focus on range query processing on large-scale, typically distributed infrastructures. In this work we present the ART (Autonomous Range Tree) structure, which outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. ART supports the join/leave and range query operations in O(log logN) and O(log2 b logN +|A|) expected w.h.p number of hops respectively, where the base b is a double-exponentially power of two, N is the total number of peers and |A| the answer size.
Sioutas, Spyros
Papaloukopoulos, Goerge
Sakkopoulos, E.
Tsichlas, Kostas
Manolopoulos, Yiannis
Triantafillou, Peter
p118-sioutas.pdf (main file)
Publication ID781