ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Optimal Clip Ordering for Multi-Clip Queries.

Raymond T. Ng, Paul Shum: Optimal Clip Ordering for Multi-Clip Queries. VLDB J. 7(4): 239-252(1998)
@article{DBLP:journals/vldb/NgS98,
  author    = {Raymond T. Ng and
               Paul Shum},
  title     = {Optimal Clip Ordering for Multi-Clip Queries},
  journal   = {VLDB J.},
  volume    = {7},
  number    = {4},
  year      = {1998},
  pages     = {239-252},
  ee        = {db/journals/vldb/NgS98.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A multi-clip query requests multiple video clips be returned as the answer of the query. In many applications and situations, the order in which these clips are to be delivered does not matter that much to the user. This allows the system ample opportunities to optimize system throughput by using schedules that maximize the effect of piggybacking. In this paper, we study how to find such optimal schedules. In particular, we consider two optimization criteria: (i) one based on maximizing the number of piggybacked clips, and (ii) the other based on maximizing the impact on buffer space. We show that the optimal schedule under the first criterion is equivalent to a maximum matching in a suitably defined bipartite graph, and that under the second criterion, the optimal schedule is equivalent to a maximum matching in a suitably defined weighted bipartite graph. Our experimental results, which are based on realistic distributions, indicate that both kinds of optimal schedules can lead to a gain in throughput of over 300%. And yet the time taken to compute such an optimal schedule is negligible. Finally, we show how to deal with clips that are variable in length.

Key Words

Performance of multimedia systems - Admission control - Bipartite graph matching

Copyright © 1998 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
David P. Anderson, Yoshitomo Osawa, Ramesh Govindan: A File System for Continuous Media. ACM Trans. Comput. Syst. 10(4): 311-337(1992) BibTeX
[2]
...
[3]
Steven Berson, Shahram Ghandeharizadeh, Richard R. Muntz, Xiangyu Ju: Staggered Striping in Multimedia Information Systems. SIGMOD Conference 1994: 79-90 BibTeX
[4]
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
[5]
Asit Dan, Martin G. Kienzle, Dinkar Sitaram: A Dynamic Policy of Segment Replication for Load-Balancing in Video-On-Demand Servers. Multimedia Syst. 3(3): 93-103(1995) BibTeX
[6]
Asit Dan, Dinkar Sitaram: An Online Video Placement Policy based on Bandwith to Space Ratio (BSR). SIGMOD Conference 1995: 376-385 BibTeX
[7]
Michael L. Fredman, Robert Endre Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3): 596-615(1987) BibTeX
[8]
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
BibTeX
[9]
Jim Gemmell: Multimedia Network File Servers: Multi-Channel Delay Sensitive Data Retrieval. ACM Multimedia 1993: 243-250 BibTeX
[10]
Jim Gemmell, Stavros Christodoulakis: Principles of Delay-Sensitive Multimedia Data Storage and Retrieval. ACM Trans. Inf. Syst. 10(1): 51-90(1992) BibTeX
[11]
Jim Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, Lawrence A. Rowe: Multimedia Storage Servers: A Tutorial. IEEE Computer 28(5): 40-49(1995) BibTeX
[12]
Shahram Ghandeharizadeh, Luis Ramos: Continuous Retrieval of Multimedia Data Using Parallelism. IEEE Trans. Knowl. Data Eng. 5(4): 658-669(1993) BibTeX
[13]
Leana Golubchik, John C. S. Lui, Richard R. Muntz: Reducing I/O Demand in Video-On-Demand Storage Servers. SIGMETRICS 1995: 25-36 BibTeX
[14]
Siu-Wah Lau, John C. S. Lui, P. C. Wong: A Cost-effective Near-line Storage Server for Multimedia System. ICDE 1995: 449-456 BibTeX
[15]
Gene Miller, Greg Baber, Mark Gilliland: News On-Demand for Multimedia Networks. ACM Multimedia 1993: 383-392 BibTeX
[16]
Dwight J. Makaroff, Raymond T. Ng: Schemes for Implementing Buffer Sharing in Continuous-Media Systems. Inf. Syst. 20(6): 445-464(1995) BibTeX
[17]
...
[18]
Frank Moser, Achim Kraiss, Wolfgang Klas: L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS. VLDB 1995: 275-286 BibTeX
[19]
...
[20]
Raymond T. Ng, Jinhai Yang: An Analysis of Buffer Sharing and Prefetching Techniques for Multimedia Systems. Multimedia Syst. 4(2): 55-69(1996) BibTeX
[21]
P. Venkat Rangan, Harrick M. Vin: Designing File Systems for Digital Video and Audio. SOSP 1991: 81-94 BibTeX
[22]
Lawrence A. Rowe, Brian C. Smith: A Continuous Media Player. NOSSDAV 1992: 376-386 BibTeX
[23]
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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:34 2009