Management Of Resources To Support Coordinated Display Of Structured Presentations.
Martha L. Escobar-Molano · University of Southern California Digital Library · 2014
With the structured approach to represent video, a presentation consists of a collection of background objects and actors (3-D representations) constrained using spatial and temporal constructs along with rendering features such as shading and the audiences' view point. While the spatial constructs define the position of the objects on the screen, the temporal constructs describe when the objects are displayed. As compared with an alternative approach (termed stream-based) that conceptualizes a video clip as a sequence of frames, the structured approach provides for both re-usability of objects in other presentations and effective query processing techniques for retrieval of relevant data. The display of a structured presentation is termed coordinated when the rendering of its objects respects the pre-specified temporal and spatial constraints. Otherwise, the display might suffer from failures that translate into meaningless scenarios. For example, a chase scene between a dinosaur and a jeep becomes meaningless if the system fails to render the dinosaur when displaying the scene. This dissertation proposes the structured approach to conceptualize video in a database. Assuming a hardware platform configured with D disks and a fixed amount of memory, this dissertation studied the complexity of resource schedulers that support the display of structured presentations. The obtained results are as follows: (1) For a single-disk architecture (D = 1), an optimal resource scheduler exists with worst case time complexity of ${\cal O}$(n lg n). This scheduler minimizes both the incurred startup latency and the amount of memory required by a display. (2) For a multi-disk architecture ($D >$ 1), a resource scheduler that minimizes the startup latency is NP-Hard. This study provides a taxonomy of resource scheduling heuristics that guarantee a coordinated display of structured presentations for a multi-disk hardware platform ($D >$ 1). A subset of these techniques manipulate the placement of data across the available disks. We employ a simulation study to quantify the trade-off associated with the alternative heuristics. The results are compared with a theoretical minimum, demonstrating that one of the proposed techniques provides a performance almost identical to this minimum.