Optimal clip ordering for multi-clip queries

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 allo ws the system ample opportunities to optimize system throughput by using sc hedules that maximize the effect of piggybacking. In this paper, we study h ow to find such optimal schedules. In particular, we consider two optimizat ion 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 maxi mum matching in a suitably defined bipartite graph, and that under the seco nd 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 t aken to compute such an optimal schedule is negligible. Finally, we show ho w to deal with clips that are variable in length.