Brief Announcement: ART: Sub-Logarithmic Decentralized Range Query Processing With Probabilistic Guarantees

Date Added: Jul 2010
Format: PDF

Existing structured P2P systems can be classified into three categories: Distributed Hash Table (DHT) based systems, skip list based systems, and tree based systems (for details see the survey book). The available solutions for architecting such large-scale systems are inadequate for the authors' purposes, since, at the envisaged scales (trilions of data items at millions of nodes) the classic logarithmic complexity (for point queries) offered by these solutions is still too expensive. And for range queries, it is even more disappointing.