Current demand for scalability in databases leads to an architecture of loosely-coupled computer nodes which can be expanded or contracted at will. Demand for 24/7 availability leads to requirements for online reorganization. To satisfy these demands, this project develops algorithms for migrating data from one node to another in a distributed system while still allowing users to access the data. First, several schemes for deciding which data to move are considered. While the goal is load balancing, performance of the migration algorithm itself is also a consideration. Algorithms must move only a small amount of the data, not reassign everything to a new node. Experiments are run to measure the "goodness" (coefficient of variance) of load balancing as well as the cost of migration. Second, index maintenance during migration is considered. When only a relatively small amount of data is moved, creating new indexes is more expensive than merging indexes or index entries of moved data into already existing indexes at destination nodes. This merging process must also be online so that users have access to all the data almost all of the time. Experiments measure both efficiency and concurrency for index merging algorithms. Broader impacts of this research include (1) educating the future educators of our technological workforce, (2) enabling efficient online reorganization of massive databases, such as occurs when government agencies are combined and (3) aiding the database industry in satisfying customer demand for scalability and 24/7 availability. More information about this project is available at www.ccs.neu.edu/research/dblab/

Agency
National Science Foundation (NSF)
Institute
Division of Information and Intelligent Systems (IIS)
Application #
0328393
Program Officer
Gia-Loi Le Gruenwald
Project Start
Project End
Budget Start
2004-09-01
Budget End
2007-08-31
Support Year
Fiscal Year
2003
Total Cost
$202,270
Indirect Cost
Name
Northeastern University
Department
Type
DUNS #
City
Boston
State
MA
Country
United States
Zip Code
02115