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 .
| BibTeX | DublinCore | EndNote | HTML |
This is the latest version of this item.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 535Kb |
Abstract
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.
| Item Type: | Conference or Workshop Item (Paper) | |
|---|---|---|
| Additional Information: | Extended Technical Report available at: http://dbpubs.stanford.edu/pub/2004-18 | |
| Subjects: | Computer Science > Distributed Systems Computer Science > Query Processing Miscellaneous | |
| Projects: | Peers | |
| Related URLs: | Project Homepage | http://infolab.stanford.edu/peers/ |
| ID Code: | 768 | |
| Deposited By: | Import Account | |
| Deposited On: | 12 Jul 2004 17:00 | |
| Last Modified: | 23 Dec 2008 08:49 |
Available Versions of this Item
- Distributed Balanced Tables: Not Making a Hash of it all. (deposited 25 Nov 2003 16:00)
- Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems. (deposited 11 Mar 2004 16:00)
- Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems. (deposited 12 Jul 2004 17:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
