Paper Info
Title
Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems
Abstract
We consider the problem of horizontally partition- ing a dynamic relation across a large number of disks/nodes by the use of range partitioning. Such partitioning is often desirable in large-scale paral- lel databases, as well as in peer-to-peer (P2P) sys- tems. As tuples are inserted and deleted, the parti- tions may need to be adjusted, and data moved, in order to achieve storage balance across the partici- pant disks/nodes. We propose efficient, asymptot- ically optimal algorithms that ensure storage bal- ance at all times, even against an adversarial in- sertion and deletion of tuples. We combine the above algorithms with distributed routing struc- tures to architect a P2P system that supports ef- ficient range queries, while simultaneously guar- anteeing storage balance.
Year
Venue
Keywords
2004
VLDB
range partitioning,dynamic relation,participant disk,large-scale parallel databases,asymptotically optimal algorithm,online balancing,large number,efficient range query,p2p system,storage balance,range-partitioned data,adversarial insertion,p2p,distributed systems,range query
Field
DocType
ISBN
Peer-to-peer,Tuple,Computer science,Range query (data structures),Theoretical computer science,Asymptotically optimal algorithm,Database,Distributed computing
Conference
0-12-088469-0
Citations 
PageRank 
References 
157
6.43
20
Authors
3
Search Limit
100157
Name
Order
Citations
PageRank
Prasanna Ganesan1116785.68
Mayank Bawa2109557.78
Héctor García-Molina3243595652.13