Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases.

Minos N. Garofalakis, Banu Özden, Abraham Silberschatz: Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases. VLDB 1997: 516-525
  author    = {Minos N. Garofalakis and
               Banu {\"O}zden and
               Abraham Silberschatz},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Resource Scheduling in Enhanced Pay-Per-View Continuous Media
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {516-525},
  ee        = {db/conf/vldb/GarofalakisOS97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP,}


The enhanced pay-per-view (EPPV) model for providing continuous-media-on-demand (CMOD) services associates with each continuous media clip a display frequency that depends on the clip's popularity. The aim is to increase the number of clients that can be serviced concurrently beyond the capacity limitations of available resources, while guaranteeing a constraint on the response time. This is achieved by sharing periodic continuous media streams among multiple clients. In this paper, we provide a comprehensive study of the resource scheduling problems associated with supporting EPPV for continuous media clips with (possibly) different display rates, frequencies, and lengths. Our main objective is to maximize the amount of disk bandwidth that is effectively scheduled under the given data layout and storage constraints. This formulation gives rise to NP-hard combinatorial optimization problems that fall within the realm of hard real-time scheduling theory. Given the intractability of the problems, we propose novel heuristic solutions with polynomial-time complexity. Preliminary results from an experimental evaluation of the proposed schemes are also presented.

Copyright © 1997 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents BibTeX

Electronic Edition

From CS Dept., University Trier (Germany)


Steven Berson, Shahram Ghandeharizadeh, Richard R. Muntz, Xiangyu Ju: Staggered Striping in Multimedia Information Systems. SIGMOD Conference 1994: 79-90 BibTeX
Mon-Song Chen, Dilip D. Kandlur, Philip S. Yu: Optimization of the Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Streams. ACM Multimedia 1993: 235-242 BibTeX
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley 1981, ISBN 0-201-03822-6
Eugene L. Lawler: Fast Approximation Algorithms for Knapsack Problems. Math. Oper. Res. 4(4): 339-356(1979) BibTeX
Thomas D. C. Little, Dinesh Venkatesh: Popularity-Based Assignment of Movies to Storage Devices in a Video-on-Demand System. Multimedia Syst. 2(6): 280-287(1995) BibTeX
C. L. Liu, James W. Layland: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM 20(1): 46-61(1973) BibTeX
Banu Özden, Alexandros Biliris, Rajeev Rastogi, Abraham Silberschatz: A Low-Cost Storage Server for Movie on Demand Databases. VLDB 1994: 594-605 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Disk Striping in Video Server Environments. IEEE Data Eng. Bull. 18(4): 4-16(1995) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: On the Design of a Low-Cost Video-on-Demand Storage System. Multimedia Syst. 4(1): 40-54(1996) BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: The Storage and Retrieval of Continuous Media Data. Multimedia Database System: Issues and Research Direction 1996: 237-261 BibTeX
Banu Özden, Rajeev Rastogi, Abraham Silberschatz: Periodic Retrieval of Videos from Disk Arrays. ICDE 1997: 333-343 BibTeX
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX
P. Venkat Rangan, Harrick M. Vin: Efficient Storage Techniques for Digital Continuous Multimedia. IEEE Trans. Knowl. Data Eng. 5(4): 564-573(1993) BibTeX
Sartaj Sahni: Approximate Algorithms for the 0/1 Knapsack Problem. J. ACM 22(1): 115-124(1975) BibTeX
Abraham Silberschatz, Peter Galvin: Operating System Concepts, 4th edition. Addison-Wesley 1994, ISBN 0-201-50480-4
John A. Stankovic, Krithi Ramamritham (Eds.): Advances in Real-Time Systems. IEEE Computer Society 1993
Fouad A. Tobagi, Joseph Pang, Randall Baird, Mark Gang: Streaming RAID: A Disk Array Management System for Video Files. ACM Multimedia 1993: 393-400 BibTeX
W.-D. Wei, C. L. Liu: On a Periodic Maintenance Problem. Oper. Res. Lett. 2(2): 90-93(1983) BibTeX
Clement T. Yu, Wei Sun, Dina Bitton, Qi Yang, Richard Bruno, John Tullis: Efficient Placement of Audio Data on Optical Disks for Real-Time Applications. Commun. ACM 32(7): 862-871(1989) BibTeX

Referenced by

  1. Minos N. Garofalakis, Banu Özden, Abraham Silberschatz: On Periodic Resource scheduling for Continuous-Media Databases. VLDB J. 7(4): 206-225(1998)
  2. Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden, Abraham Silberschatz: Throughput-Competitive Admission Control for Continuous Media Databases. PODS 1998: 79-88
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:18 2009