Scalable Data Access in Peer-to-Peer Systems Using Unbalanced Search Trees

With the appearance of Peer-to-Peer information systems the interest in scalable and decentralized data access structures is attracting increasingly interest. We propose to that end P-Grid, a scalable data access structure resulting from the distribution of a binary prefix tree. When adapting the P-Grid structure to skewed data distributions one obtains unbalanced search trees. The key result of this paper shows that unbalanced trees do not harm as long as communication is considered as the critical cost and the access structures are constructed properly. Besides proving this result we propose the necessary distributed, randomized algorithms that allow to construct the P-Grid in a self-organized manner such that the tree structure dynamically adapts to the data distribution and the aforementioned result is applicable.