Efficient support for range queries in DHT-based systems

Abstract: "In recent years, Distributed Hash Tables (DHTs) have been proposed as a fundamental building block for Internet-scale distributed applications. Important functionalities such as searching has been added to the DHT's basic look up capability. However, supporting range queries efficiently remains a difficult problem. In this paper, we describe an efficient algorithm that decomposes a range query with length R[subscript q] into O(log R[subscript q]) sub-queries that are resolved by separate nodes corresponding to each sub-query. Our system utilizes a novel logical tree data structure, the Range Search Tree (RST), which automatically groups registrations based on their values explicitly. Coupled with a dynamic load balancing mechanism, our system can handle both point and range queries efficiently regardless of the distribution of the registrations and queries. Our algorithm is fully distributed and we avoid conventional bottleneck problems encountered by tree-based systems. Extensive simulation results validate the effectiveness of the system."