Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Efficient Sequencing Tape-Resident Jobs

Sachin More, S. Muthukrishnan, and Elizabeth A. M. Shriver

  View Paper (PDF)  

Return to Query Optimization

Abstract
Data repositories are terabytes or petabytes in size, and are expected to continue to grow. Consequently, many applications comprise of tape-resident jobs, namely, ones that process data resident on tape. Not all orders of execution amongst tape-resident jobs make optimum use of the resources, and better sequencing strategies for job execution can significantly reduce the total time for a batch of tape-resident jobs. Our contribution is the general algorithmic approach we develop for solving such scheduling problems by reducing them to a flow-shop problem. Our extensive experimental study shows that our techniques for sequencing job executions decrease the overall time for tape-resident jobs by as much as 15% on EOSDIS data (and even more on synthetic data), which is a significant gain due to the total time these jobs take.


References

Note: References link to DBLP on the Web.

[1]
...
[2]
Soumen Chakrabarti , S. Muthukrishnan : Resource Scheduling for Parallel Database and Scientific Applications. SPAA 1996 : 329-335
[3]
...
[4]
...
[5]
...
[6]
M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[7]
Minos N. Garofalakis , Yannis E. Ioannidis : Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources. VLDB 1997 : 296-305
[8]
...
[9]
...
[10]
...
[11]
...
[12]
Ben Kobler , John Berbert , Parris Caulk , P. C. Hariharan : Architecture and Design of Storage and Data Management for the NASA Earth Observing System Data and Information System (EOSDIS). IEEE Symposium on Mass Storage Systems 1995 : 65-76
[13]
...
[14]
...
[15]
Stefano Leonardi , Danny Raz : Approximating Total Flow Time on Parallel Machines. STOC 1997 : 110-119
[16]
...
[17]
...
[18]
...
[19]
...
[20]
...
[21]
...
[22]
Sunil Prabhakar , Divyakant Agrawal , Amr El Abbadi , Ambuj K. Singh : Scheduling Tertiary I/O in Database Applications. DEXA Workshop 1997 : 722-727
[23]
Sunita Sarawagi : Query Processing in Tertiary Memory Databases. VLDB 1995 : 585-596
[24]
...
[25]
...
[26]
Jie-Bing Yu , David J. DeWitt : Query Pre-Execution and Batching in Paradise: A Two-Thronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images. SSDBM 1997 : 0-

BIBTEX

@inproceedings{DBLP:conf/pods/MoreMS99,
  author    = {Sachin More and
                S. Muthukrishnan and
                Elizabeth A. M. Shriver},
   title     = {Efficient Sequencing Tape-Resident Jobs},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {33-43},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM