Efficient Management of Multidimensional Data in Structured Peer-to-peer Overlays
Djelloul Boukhelef, Hiroyuki Kitagawa · 2009
Efficient handling of multidimensional data is a challenging issue in P2P systems. DHT-based systems provide mechanisms for handling exact-match lookups that are extremely scalable. However, efficient evaluation of complex queries (such as multi-attributes range search, kNN search...) over huge volumes of multidimensional data is still an open problem in DHTs, mainly because they use hashing that destroys the spatial locality of the stored data, and also due to the high cost of nodes joins and departures. In this paper we propose a new scalable and distributed indexing structure for managing multidimensional data in dynamic P2P systems. Our approach is based on the Content Addressable Networks paradigm. The key idea is to equip each node with long links towards some distant nodes in the system such that a message moves faster to its target during routing, while the cost of maintaining the network during a nodes churn is minimized. Our system is a pure P2P overlay that is fully-decentralized and self-organizing, where no predefined limits are imposed on the sizes of the network or the routing state per node. Each node self-adjusts its routing state to cope with changes in network membership. Specifically, in a network with N nodes, each node maintains O(log N) long links. Exact-match and range queries are routed within O(log N) hops. We also provided an effective load balancing mechanism that assign a new joining node to a heavily loaded area in the key space. This mechanism guarantees a constant load imbalance factor, with an amortized cost of O(log N) messages node join compared to O(log 2 N) in other systems. We implemented a simulator and conducted experiments to study the performance of our design. Experimental results validate the full scalability and efficiency of our approach. 1.