title: Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems
creator: Ganesan, Prasanna
creator: Bawa, Mayank
creator: Garcia-Molina, Hector
subject: Distributed Systems
subject: Query Processing
subject: Miscellaneous
description: We consider the problem of horizontally partitioning a dynamic relation across a large number of disks/nodes by the use of range partitioning. Such partitioning is often desirable in large-scale parallel databases, as well as in peer-to-peer (P2P) systems. As tuples are inserted and deleted, the partitions may need to be adjusted, and data moved, in order to achieve storage balance across the participant disks/nodes. We propose efficient, asymptotically optimal algorithms that ensure storage  balance at all times, even against an adversarial insertion and  deletion of tuples. We combine the above algorithms with distributed  routing structures to architect a P2P system that supports efficient range  queries, while simultaneously guaranteeing storage balance.
date: 2004
type: Conference or Workshop Item
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/768/1/2004-35.pdf
identifier: Ganesan, Prasanna and Bawa, Mayank and Garcia-Molina, Hector (2004) Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems. In: 30th International Conference on Very Large Data Bases (VLDB 2004) , August 29 - September 3, 2004 , Toronto, Canada .
relation: http://ilpubs.stanford.edu:8090/768/