Brief Announcement: ART: Sub-Logarithmic Decentralizec Ranqe Query Processing with Probabilistic Guarantees

摘要

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(loglog N) and O(log_b~2 log N + |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.