L. Liu and K.D. Ryu (USA)
Range Queries, Distributed Hash Table, Signature, Peer-to Peer, Distributed Computing
An efficient range query processing support is required for Distributed Hash Table (DHT)-based P2P networks as con sistent hashing destroys the inherent order of numeric keys. In this paper, we present a lightweight and efficient mech anism, called Range Hash Tree (RHT), to support range queries on DHTs. In RHT, key space is partitioned into small ranges such that data items within one range can be stored on one node. To quickly resolve a range query, we introduce a scalable encoding algorithm that can represent the key space partitioning status with a small RHT Sig nature. Compared to other approaches, RHT provides a bounded query delay, which is independent of the size of range query and the number of matching data items. Our experiments show that RHT works efficiently on both uni form and much skewed data distributions.
Important Links:
Go Back
