Indexing data-oriented overlay networks

We address the problem of how a data-oriented, structured overlay networks can be constructed efficiently from scratch in a self-organized way, a problem that has so far not been addressed in the literature. This problem occurs when using overlay networks to implement index structures for data-oriented applications such as peer-to-peer databases or peer-to-peer information retrieval. There changing application requirements frequently lead to re-indexing of the data and hence (re-)construction of overlay networks. Standard maintenance algorithms for overlay networks cannot efficiently deal with this task as they are inherently sequential. We propose a randomized algorithm which is completely decentralized and parallel that can construct a new overlay network with short latency. At the same time our approach ensures good load-balancing for skewed data key distributions which result from preserving key order relationships as necessitated by data-oriented applications. We provide both a theoretical analysis of the basic algorithms and a complete system implementation that has been tested on PlanetLab. We are using this system to support peer-to-peer information retrieval and database applications.


Presented at:
31st International Conference on Very Large Databases (VLDB), Trondheim, 30 Aug - 2 Sep, 2005
Year:
2005
Keywords:
Laboratories:




 Record created 2005-09-15, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)