Skiptree: A new scalable distributed data structure on multidimensional data supporting range-queries

This paper presents a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. It supports range queries as well as single point queries which are routed in O(logn)O(logn) hops. Our structure, called SkipTree, is fully decentralized with each node being connected to O(logn)O(logn) other nodes. We propose modifications to the structures, so that the memory usage for maintaining the link structure at each node is reduced from the worst case of O(n)O(n) to O(lognloglogn)O(lognloglogn) on the average and O(log2n)O(log2n) in the worst case. It is also shown that the load balancing is guaranteed to be within a constant factor. Our experimental results verify our theoretical proofs.