The input data dependency is particularly important for advanced multimedia applications, where video content is partitioned into independent video objects instead of rectangular frames of samples. As objects can change over time, in size, shape and texture contents, the processing requirements are more variable then with conventional video. For this reason we have adopted the MPEG-4 standard as an example of object oriented video processing. In this paper we consider a class of QoS systems that relies on predicting the execution times of the application at run-time taking the data dependency into account. We propose a control mechanism based on a linear prediction model that interacts with a higher level QoS management unit to adopt qualit...