| Available via | http://dbpubs.stanford.edu/pub/2004-35 |
| Previous version | 2003-71 |
|
Submitted on |
13th of July 2004 |
|
Author |
Ganesan, Prasanna; Bawa, Mayank; Garcia-Molina, Hector |
|
Title |
Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems |
|
Date of publication |
2004 |
|
Published in |
Proceedings VLDB, 2004 |
|
Citation |
Ganesan, Prasanna; Bawa, Mayank; Garcia-Molina, Hector. Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems, Proceedings VLDB, 2004 |
|
Number of pages |
12 |
|
Language |
English |
|
Project |
Peers |
|
Type |
Conference or Journal Paper |
|
Subject group |
Distributed Systems; Query processing; Miscellaneous |
|
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. |
|
Notes |
Extended Technical Report available at:
http://dbpubs.stanford.edu/pub/2004-18 |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |