SMART: Storage Management Algorithms Research Team

Funded by NSF ITR Award CCR-0113192: Algorithms for Data Storage and Movement

Abstract: In this research we focus on efficient methods for the storage and movement of data over local as well as wide-area networks. Specifically, this project develops algorithmic techniques that impact the performance of large multimedia data storage systems. Furthermore, what makes the issues considered even more significant is the fact that data storage and movement issues also arise within publicly shared networks such as the Internet where the bandwidth can be dynamic and highly variable, and can result in a poor choice of paths chosen to transfer data in the network. In algorithmic terms, some of the principal challenges that arise in the context of multimedia data storage are: (a) deciding how many copies of each data item need to be stored, (b) determining the exact layout of data on a set of servers, (c) dealing with changing workloads and dynamic data access patterns. These related challenges require the development of efficient methods for optimizing data layout to maximize client satisfaction, monitoring the performance of data storage systems

Principal Investigators: Samir Khuller and Leana Golubchik

See the Bistro page as well

Publications related to this grant:

Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramki Thurimella and An Zhu.
Approximation Algorithms for Data Placement on Parallel Disks.
11th Symposium on Discrete Algorithms (SODA), San Francisco, Jan 2000.

Cheng-Fu Chou, Yung-Chun (Justin) Wan, William C. Cheng, Leana Golubchik, and Samir Khuller.
A Performance Study of a Large-scale Data Collection Problem.
7th International Workshop on Web Content Caching and Distribution, Boulder, Colorado, Aug 2002.

Yoo Ah Kim.
Data Migration to Minimize the Average Completion Time.
14th Symposium on Discrete Algorithms (SODA), Baltimore, Jan 2003.

William Cheng, Cheng-Fu Chou, Leana Golubchik, Samir Khuller, and Yung-Chun Wan.
Large-scale Data Collection: a Coordinated Approach.
IEEE Infocom 2003, San Francisco, Apr 2003.

Samir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan.
Algorithms for Data Migration with Cloning.
22nd ACM Symposium on Principles of Database Systems (PODS), San Diego, Jun 2003.

Samir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan.
On Generalized Gossiping and Broadcasting.
11th Annual European Symposium on Algorithms (ESA), Budapest, Hungry, Sept 2003.
An updated version with a (3+o(1))-approximation algorithm for the Multi-source Multicast problem.

Leana Golubchik, Samir Khuller, Yoo-Ah Kim, Svetlana Shargorodskaya, and Yung-Chun (Justin) Wan.
Data Migration on Parallel Disks.
To appear in 12th Annual European Symposium on Algorithms (ESA), Bergen, Norway, Sept 2004.


Implementation of algorithms for data migration with cloning