首页 | 本学科首页   官方微博 | 高级检索  
     


Optimal clip ordering for multi-clip queries
Authors:Raymond T. Ng  Paul Shum
Affiliation:(1) Department of Computer Science, University of British Columbia, Vancouver, B.C., V6T 1Z4, Canada , CA
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. Received: June 9, 1998 / Accepted October 13, 1998
Keywords::Performance of multimedia systems –   Admission control –   Bipartite graph matching
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号