SkipTree: A scalable range-queryable distributed data structure for multidimensional data This paper presents the SkipTree, a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. The SkipTree supports range queries as well as single point queries which are routed in O(logn) hops. SkipTree is fully decentralized with each node being connected to O(logn) other nodes. The memory usage for maintaining the links at each node is O(lognloglogn) on average and O(log 2 n) in the worst case. Load balance is also guaranteed to be within a constant factor
References in zbMATH (referenced in 2 articles , 1 standard article )
Showing results 1 to 2 of 2.
- Alaei, Saeed; Ghodsi, Mohammad; Toossi, Mohammad: Skiptree: A new scalable distributed data structure on multidimensional data supporting range-queries (2010) ioport
- Alaei, Saeed; Toossi, Mohammad; Ghodsi, Mohammad: SkipTree: A scalable range-queryable distributed data structure for multidimensional data (2005)