Optimal display sequence for multi-clip queries

With the increased significance of multimedia applications, the performance of multimedia systems used in these applications becomes more important. This thesis investigates the possibility to improve the throughput of a system serving multi-clip queries. A multi-clip query requests multiple video clips be returned as the answer of the query. In many multimedia applications, the order in which the video clips are to be delivered does not matter that much to the user. This thesis discovers that the throughput of a system can be improved significantly for queries if the display sequence can be rearranged using the "piggybacking" technique. It describes two optimization criteria: maximizing the number of piggybacked clips and maximizing the impact on buffer space, to find an optimal display sequence. This thesis shows that the display sequences can be found using the bipartite matching. Two corresponding admission control algorithms, MaxPVC and MaxIBS, are presented. It further extends the technique to video clips of variable buffer size. Finally, it presents the MaxPP algorithm, which is used to generate display sequences for queries of variable length video clips. Experimental results show that the piggybacking technique can improve the system throughput significantly. Depending on the total number of available video clips, the throughput of the MaxPVC and MaxIBS algorithms can increase over 300%. The MaxPP algorithm can increase the throughput of the system to 30%.Science, Faculty ofComputer Science, Department ofGraduat