Scalable Range Query Processing for Large-Scale Distributed Database Applications

Peer-to-peer (P2P) systems provide a robust, scalable and decentralized way to share and publish data. Although highly efficient, current P2P index structures based on Distributed Hash Tables (DHTs) provide only exact match data lookups. This compromises their use in database applications where more advanced query facilities, such as range queries, are a key requirement. In this paper, we give a new P2P indexing structure that supports range searches over shared data while maintaining DHTs logarithmic search time. Our index structure can be seen as an extension of the Chord P2P overlay so that data items are mapped to the Chord address space in an order-preserving way, hence supporting range query executions. Load balancing of skewed data is then achieved deterministically using the underlying DHT infrastructure. Experimental evaluations show that our mechanism provides strong load-balancing guarantees in systems with high data skews