CONTINUOUS MEDIA SUPPORT FOR MULTIMEDIA
`DATABASES
`
`-4 thesis subrnitted to the
`
`Department of Computing and Information Science
`
`in conformity with the requirements for
`
`the degree of Master of Science
`
`Queen's University
`
`Kingston, Ontario, Canada
`
`September 1998
`
`Copyright @ Jun Su, 1998
`
`Page 1 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`DATABASES
`
`-4 thesis subrnitted to the
`
`Department of Computing and Information Science
`
`in conformity with the requirements for
`
`the degree of Master of Science
`
`Queen's University
`
`Kingston, Ontario, Canada
`
`September 1998
`
`Copyright @ Jun Su, 1998
`
`Page 1 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`1+1 o f m a d a
`
`National Library
`
`Bibiinthèque nationale
`du Canada
`
`Acquisitions and
`Bibliographie SeMces
`
`Acquisitions et
`seMces bibliographiques
`
`The author has granted a non-
`exclusive licence allowing the
`National Liirary of Canada to
`reproduce, loan, distribute or sel1
`copies of this thesis in microform,
`paper or electronic formats.
`
`L'auteur a accordé me licence non
`exclusive permettant à la
`Bibliothèque nationale du Canada de
`reproduire, prêter, distriber ou
`vendre des copies de cette thèse sous
`la forme de rnicrofiche/nlm, de
`reproduction sur papier ou sur format
`électronique.
`
`The author retains ownership of the
`copyright in this thesis. Neither the
`thesis nor substantid extracts fiom it
`may be printed or otherwise
`reproduced without the author's
`permission.
`
`L'auteur conserve la propriété du
`droit d'auteur qui protège cette thèse.
`Ni la thése ni des extraits substantiels
`de celle-ci ne doivent être imprimés
`ou autrement reproduits sans son
`autorisation.
`
`Page 2 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`Abstract
`
`Multimedia presentations demand specific support from database management sys-
`
`terns. The delivery of continuous media data from a database semer to multiple des-
`
`tinations over a network presents new challenges for buffer management in a DBMS.
`
`It has to consider specific requirements like providing for continuity of presentation or
`
`for immediate continuation of presentation after frequent user interactions. Different
`
`media also have specific features that must be considered.
`
`In this thesis we present a buffer management strategy for MPEG video presenta-
`
`tions. It supports smooth presentation of MPEG video stored in the relational DBMS
`
`DB2/UDB, and quick response to user interactions. Experiments show that Our buffer
`
`management strategy provides support superior to other strategies presented in the
`
`literature. -4 framework to support cornplex multimedia presentation that is based
`
`on DBP/UDB and its multimedia extenders is also presented.
`
`Page 3 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`ii
`
`Page 4 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`Page 4 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`Acknowledgment s
`
`1 would like to thank my supervisor, Dr. Pat Martin, for his support, advice, feedback.
`
`and above all, his patience. Without his guidance, this thesis could not have been
`
`finished. 1 would also like to thank Gary Powley and Wendy Powley, for helping me
`
`with my research and implementation; Rong Qiu and Hoiying Li, my good friends. for
`
`giving me help whenever 1 needed. Finally, I would like to thank the Department of
`
`Computing and Information Science at Queen's University for tlieir generous financial
`
`support provided during my graduate studies.
`
`iii
`
`Page 5 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`iv
`
`Page 6 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`Page 6 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`Contents
`
`1 Introduction
`
`1.1 Motivation for the Research . . . . . . . . . . . . . . . . . . . . . . .
`
`1.2 Goals of Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`1.3 Outline of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`2 Background
`
`7
`
`2.1 Multimedia DBMS and Buffer Management Strategy . . . . . . . . .
`
`8
`
`2.2 AMOS hlultimedia DBhlS at GMD-IPSI . . . . . . . . . . . . . . . .
`
`I l
`
`2.3 LeastIMost Relevant for Presentation
`
`. . . . . . . . . . . . . . . . . .
`
`15
`
`2.3.1 A General Mode1
`
`. . . . . . . . . . . . . . . . . . . . . . . . .
`
`17
`
`2.3.2 Replacement and Preloading S trategy
`
`. . . . . . . . . . . . . .
`
`20
`
`2.4 MPEG Video and -4udio Player a t OGI
`
`. . . . . . . . . . . . . . . . .
`
`21
`
`2-41 MPEG video standard
`
`. . . . . . . . . . . . . . . . . . . . . .
`
`21
`
`2.4.2 System Architecture
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`23
`
`Page 7 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`vi
`
`CONTENTS
`
`2.4.3 Software Feedback for Client/Server Spchronization
`
`. . . . .
`
`25
`
`2.4.4 Software Feedback for QoS control
`
`. . . . . . . . . . . . . . .
`
`27
`
`3 System Architecture
`
`3.1 System Architecture
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3.1.1 Session Manager and Client
`
`. . . . . . . . . . . . . . . . . . .
`
`3.1.2 SessionCoordinator
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`29
`
`29
`
`30
`
`32
`
`3.1.3 DB2/UDB and Its Multimedia Extenders
`
`. . . . . . . . . . .
`
`33
`
`3.2 Media Provider and Media Presenter
`
`. . . . . . . . . . . . . . . . . .
`
`35
`
`3.2.1 Media Provider and Media Presenter for MPEG video . . . . . 34
`
`4 B d e r Management Strategy
`
`4.1 MPEG Video Presentation
`
`. . . . . . . . . . . . . . . . . . . . . . . .
`
`4.1.1
`
`Initialization
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`1.1.2 Buffer Manager
`
`. . . . . . . . . . . . . . . . . . . . . . . . . .
`
`4.1.3 Decoder and Presenter
`
`. . . . . . . . . . . . . . . . . . . . . .
`
`4.2 Buffer Management Strategy
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`4.2.1 Preloading Strategy
`
`. . . . . . . . . . . . . . . . . . . . . . . .
`
`43
`
`43
`
`44
`
`46
`
`49
`
`51
`
`55
`
`4.2.2 Replacement S trategy
`
`. . . . . . . . . . . . . . . . . . . . . .
`
`57
`
`5 Performance Study
`
`5.1 Measurements
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`59
`
`59
`
`Page 8 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`CONTENTS
`
`5.2 Comparing Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5.3 Test Environment . . . . . . . . . . . . . . . . . . . . . . . . . - . - .
`
`5.4 Results and Observations . . . . . . . . . . . . . . . . . - . . - . . . .
`
`vii
`
`62
`
`64
`
`65
`
`5.4.1 Smoothness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
`
`5.4.2 Interactive Response Time . . . . . . . . . . . . . . . . . . . .
`
`il
`
`5.4.3 Smoothness vs. Buffer Size . . . . . . . . . . . . . . . . . . . .
`
`W C
`
`i a
`
`6 Conclusions
`
`77
`
`6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . .
`
`. . . , . .
`
`78
`
`6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . - . . . . . . 79
`
`Bibliography
`
`Glossary
`
`Vit a
`
`Page 9 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`viii
`viii
`
`CONTENTS
`CONTENTS
`
`Page 10 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`Page 10 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`List of Tables
`
`2.1 Functionality of the synchronization feedback mechanism . . . . . . . 26
`
`2.2 Functionality of the QoS control feedback mechanism . . . . . . . . . 25
`
`5.1 MPEG Video Frames Mode1
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`62
`
`5.2 SmoothnessofAMOSandOurStrategy . . . . . . . . . . . . . . . . 68
`
`5-3 Smoothness of OGI and Our Strategy
`
`. . . . . . . . . . . . . . . . . 69
`
`5.4 . Interaction Response Time (ms) . . . . . . . . . . . . . . . . . . . . . 72
`
`Page 11 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`x
`x
`
`LIST OF TABLES
`LIST OF TABLES
`
`Page 12 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`Page 12 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`List of Figures
`
`General architecture of a hlhl-DBM S
`
`. . . . . . . . . . . . . . . . . .
`
`9
`
`Architecture of the AMOS MM-DBMS
`
`. . . . . . . . . . . . . . . . .
`
`14
`
`Example state of a data flow
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`16
`
`An example of interaction sets viith relevance values
`
`. . . . . . . . . .
`
`17
`
`L/MRP Algorithm
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`20
`
`Architecture of the OGI player
`
`. . . . . . . . . . . . . . . . . . . . . .
`
`23
`
`Structure of the synchronization feedback mechanism . . . . . . . . . 26
`
`Structure of the QoS control feedback mechanism
`
`. . . . . . . . . . .
`
`27
`
`3.1 System Architecture
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3.2 Session Manager and Client
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`3.3 Object-Relational Database System
`
`. . . . . . . . . . . . . . . . . .
`
`30
`
`31
`
`34
`
`3.4 Classification of Adaptation Mechanism
`
`. . . . . . . . . . . . . . . .
`
`37
`
`3.5 Media Provider and Media Presenter for MPEG video
`
`. . . . . . . .
`
`39
`
`xi
`
`Page 13 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`xii
`
`LIST OF FIGURES
`
`4.1 MPEG Video Presentation Process
`
`. . . . . . . . . . . . . . . . . . .
`
`4.2 Data Flow at Client Side
`
`. . . . . . . . . . . . . . . . . . . . . . . .
`
`45
`
`46
`
`4.3
`
`.-ln example of MPEG video stream
`
`. . . . . . . . . . . . . . . . . . .
`
`53
`
`4.4 Buffer Management Algorithm
`
`. . . . . . . . . . . . . . . . . . . . .
`
`54
`
`5.1 Smoothness Measurement
`
`. . . . . . . . . . . . . . . . . . . . . . . .
`
`5.2 Smoothness vs . Buffer Size
`
`. . . . . . . . . . . . . . . . . . . . . . .
`
`67
`
`C I -
`
`r a
`
`Page 14 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`Chapter 1
`
`Introduction
`
`1.1 Motivation for the Research
`
`Multimedia presentations present a wide range of media including audio, video, test,
`
`images, and animation in a single presentation, and allow users to control the rate
`
`and selection of media being played. It is one of the most important multimedia
`
`applications. The fusion of different media into multimedia presentations provides an
`
`opportunity to create more effective and efficient communications of ideas.
`
`A multimedia database management system (MM-DBMS) provides the necessary
`
`support for multimedia presentation. A MM-DBMS has the capability of storing,
`
`managing and retrieving information on individual media, managing interrelation-
`
`ships between the information represented by different media, and exploiting t hese
`
`1
`
`Page 15 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2
`
`1 ntroduction
`
`media for presentation purposes [RNL95].
`
`Multimedia presentation demands specific support from a EVM-DBMS. They re-
`
`quire the delivery of continuous media data from a database server to multiple des-
`
`tinations over a network. To facilitate a hiccup-free presentation, the MM-DBbIS
`
`must ensure that an object is present in memory before it is displayed. If the loading
`
`rate of a media stream from disk to mernory is less than the delivery rate of the
`
`media stream, then preloading of the stream prior to delivery is necessary to ensure
`
`continuous presentation. Furthermore, an appropriate allocation and replacement
`
`strategy must be provided to anticipate the dernands of delays and user interactions.
`
`Such a strategy must rninirnize the response time of multimedia presentations while
`
`guaranteeing that dl continuity requirements are satisfied.
`
`Replacement strategies for conventional database applications, like LRü (Leas t
`
`Recently Used), FIFO (First In First Out), LFU (Least Frequently Used), etc.,
`
`([DTgO], (EH841) are not suitable for a multimedia database system. They do oot ex-
`
`plicitly address the reference behaviour of interactive continuous data. Furthermore,
`
`presentation scenarios can be constructed where these strategies have destructive be-
`
`haviour. We can show this by a n example. Suppose Our buffer uses the LRU strategy.
`
`If we begin with an empty buffer with constant buffer size 15, then playing frames
`
`1 to 20 of a video leads to a buffer state in which frames 6 to 20 are in the buffer
`
`after the presentation h a . finished. If we next wish to play forward from frame 5 to
`
`Page 16 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`1.1 Motivation for the Research
`
`3
`
`15, then kame 5 is not present in buffer, which causes a buffer fault. LRU would
`
`replace 6 to load 5. Now we request frame 6, and LRU would replace 7, and so on.
`
`In this case LRU always replaces the frame that will be needed next. T h e reason for
`
`this behaviour is that LRU does not consider any presentation specific informat ion.
`
`For al1 the other general strategies similar examples of "destructive behaviour" can
`
`be found. This behaviour is not only for some "constructed~' examples, Moser et al
`
`[kIKK95] show the average misbehaviour of LRU in their performance investigations.
`
`Currently many multimedia systems employ the "UseSrToss" replacement st rat-
`
`egy [CAFSl]. Each data page is free for replacement immediately after it is presented.
`
`The drawback of this simple strategy is that data that rnay be referenced after an in-
`
`teraction are not kept in the buffer. For example. if the user initiates a play backmard
`
`interaction from the play fonvard state, then al1 previously tossed d a t a may have to
`
`be reloaded into buffer, which leads to increase response times.
`
`Most buffer management strategies developed For multimedia database si-çtems
`
`only support generic models for continuous media, but we claim that media specific
`
`properties should be considered. A generic buffer manager treats video frames as
`
`independent, atomic units and the preloading and replacement strategies are based
`
`on this assumption. In MPEG (Motion Picture Experts Group) video presentation.
`
`frame dropping is used because the data volume involved is very large, and the systeni
`
`may not be able to present al1 the frarnes in time. Dropping of one frame rnay affect
`
`Page 17 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`4
`
`Introduction
`
`the following frames. Thus for MPEG video the dependencies between the single
`
`frames have to be considered.
`
`MPEG is a widely accepted international standard. Specially, MPEG-1 plays a n
`
`important role in multimedia applications. Some researchers [CPS95] have studied
`
`the specific features on MPEG-1, but did not consider the impact of these features on
`
`multimedia presentation. Other researchers [HL971 have considered the effect of the
`
`features of MPEG-I on multimedia presentation, but could not mode1 MPEG-I data
`
`very well. We investigate a specific buffer management strategy for MPEG-I video
`
`presentation in this thesis.
`
`A relational database uses tables to represent entities and uses keys to represent
`
`relationships. An instance of an entity is represented as a row of the table. The
`
`standard applications of a relational database range from high volume online trans-
`
`action systems to query intensive data aarehouse applications. Multimedia data like
`
`audio and video are stored as binary large objects (BLOBs) in a relational database.
`
`User-defined data types and functions are used to support multimedia applications.
`
`1.2 Goals of Research
`
`The main goals of the research are:
`
`To study efficient buffer management strategies for delivering MPEG video data
`
`from a relational database. The strategies must also support user interaction.
`
`Page 18 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`1.3 Outline of Thesis
`
`5
`
`To implement a buf'fer management strategy and study its performance in
`
`a client-semer environment where IBM DB2/UDB [IBAI97b] is used to store
`
`MPEG video a t the server side.
`
`To propose a framework to support complex multimedia presentations.
`
`The particular problems and issues addressed in this thesis are:
`
`How to preload video data to maintain a smooth presentation.
`
`How to replace video data in order to quickly respond to user interactions.
`
`1.3 Outline of Thesis
`
`The remainder of this thesis is organized as follows:
`
`Chapter 2 discusses the background rnaterial required for our work.
`
`Chapter 3 describes the architecture of a system to support multimedia presen-
`
`tation. The subsystem for MPEG video presentation is also presented.
`
`Chapter 4 presents the buffer management strategy for MPEG video presenta-
`
`tion.
`
`Chapter 5 discusses the implementation of the buffer management strategy and
`
`presents a performance study of the strategy.
`
`Page 19 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`6
`
`Introduction
`
`Chapter 6 concludes the thesis with a review of the contributions of the work
`
`and a discussion of future research directions.
`
`Page 20 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`Chapter 2
`
`Background
`
`In this chapter, we first introduce multimedia database management system (DBMS)
`
`and its buffer management strategy. Then we give an overview of the "AMOS Multi-
`
`media DBMS at GMD-IPSI". We present their "teast/most relevant for presentation"
`
`(L/MRP) buffer management strategy from which we derived our strategy for MPEG
`
`video presentation. Finaily we present an MPEG video player developed at OGI that
`
`provides the b a i s for Our implementation.
`
`7
`
`Page 21 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`8
`
`Background
`
`2.1 Multimedia DBMS and Buffer Management
`
`Strategy
`
`A multimedia database management system (MM-DBMS) has the capability of stor-
`
`ing, managing and retrieving information on individual media, managing interre-
`
`lationships between the information represented by different media, and exploiting
`
`these media for presentation purposes. The basic constituents of a MM-DBMS are
`
`the following:
`
`Multimedia Data Modeling. Standard datatypes are not adequate to reflect the
`
`structure of multimedia data. New built-in datatypes like image and audio and
`
`a notion of stream for presentation and capture purpose are needed. In addi-
`
`tion to the datatypes, type constructors that allow one to deal with temporal
`
`relationships are also helpful.
`
`Content-Based Retrieval. Retrieval in rnuitimedia databases must include the
`
`type of queries known from the field of traditional databases as well as retrieval
`
`functionality (such as full text search) knowo from the field of information
`
`retrieval. In the case of videos, content-based search means the ability to search
`
`for a specific fragment of a video that starts with a given scene, or includes given
`
`objects.
`
`Page 22 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.1 Muhimecria DBMS and B a e r Management Strategy
`
`9
`
`- - - - - - -
`
`data - conuol
`
`MM-DBMS Server
`
`p p -- -
`
`MM-DBMS Client
`
`manipulation object
`
`manipulation objecu
`1
`7
`
`
`
`1 Pragnrn
`
`Application
`
`1
`
`Figure 2.1: General architecture of a MM-DBMS
`
`Continuous Storage Management. To provide timely delivery, continuous data
`
`strearns may be directed from the storage components to the consuming com-
`
`ponent (viewer, application) bypassing other layers of the multimedia database
`
`system. This avoids additional overhead but does not allow any further pro-
`
`cessing (selection of portion, scafing, etc.) of the data by the database system.
`
`Architecture. Figure 2.1 [NT921 shows a multimedia application that uses the
`
`service of the DBMS to retrieve multimedia objects from the database, to ma-
`
`nipulate them, to transport them over the network and finally to present them
`
`at the user's workstation. A transport protocol that implements the continuous
`
`flow of data along with a mechanism for continuous control is of central im-
`
`portance for an efficient management of presentation and capture functionality
`
`throughout the whole system.
`
`Buffer management wit hin the multimedia database system is essential to ensure
`
`the maintenance of the intra- and inter-strearn synchronization requirements of mul-
`
`timedia data presentations. To facilitate a hiccup-free presentation, we must ensure
`
`Page 23 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`10
`
`Background
`
`that an object is present in memory before it is displayed. If the loading rate of a me-
`
`dia stream from disk t o memory were less than the delivery rate of the media stream,
`
`preloading of the stream pnor to delivery would be necessary to ensure continuous
`
`presentation. Furthemore, an appropriate allocation and replacement strategy must
`
`be provided to anticipate the dernands of delays and user interactions. Such a strat-
`
`egy must minimize the response time of multimedia presentations while guaranteeing
`
`that al1 continuity and synchronization requirements are satisfied.
`
`Research involving buffer management in multimedia database systems is still in
`
`its infancy [TK95]. Moser et al [MKK95] have proposed a buffer strategy termed
`
`"least /most relevant for presentation" . This buffer strategy invest igates the effects
`
`of such user interactions as "rewind" and "fast fonvard" on buffer design. A mech-
`
`anism is proposed which reduces the delay after user interactions. Chaudhuri et al
`
`[CGS95] have investigated the problem of continuously displaying composite objects
`
`that are dynamically specified at the server level. Techniques based on simple slid-
`
`ing and buffered sliding are proposed which support continuous display by partial
`
`prefetching of overlapping media objects. Such an approach is preferable to the naive
`
`strategy of prefetching the entirety of overlapped media objects. Gollapudi [GZ96]
`
`has investigated the minimum buffering requirements that are necessary to guarantee
`
`the continuity and synchrony of the presentation of multimedia data. A prefetching
`
`technique that satisfies the minimum requirements has also been worked out.
`
`Page 24 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.2 AMOS Multimedia DBMS at GMD-IPSI
`
`11
`
`2.2 AMOS Multimedia DBMS at GMD-IPSI
`
`The Integrated Publication and Information Systems Institute (IPSI) is one of the
`
`eight institutes of GMD - German National Research Center for Information Tech-
`
`nology. Research on MM-DBMS a t IPSI started at the end of the 1980's. In 1992,
`
`the department Active Media Object Stores (AMOS) was founded to foster devel-
`
`opments in this research area [NT92]. Currently, concepts are implemented in the
`
`AMOS MM-DBMS prototype and are elaborated by means of international research
`
`projects as well a s industrial projects. The accomplishments to date of the AMOS
`
`prototype include the following: the design of multimedia data types, the modeling
`
`of meta information, support for multimedia presentations, and the development of
`
`an object manager for continuous objects.
`
`AMOS allows the free composition of different media into a new multimedia prod-
`
`uct - a multimedia presentation. Any combination of both continuous media, such
`
`as audio, video, and text, as well as non-continuous media, such as a picture, can be
`
`arranged in one multimedia presentation. This calls for a mode1 of a presentation that
`
`includes defined temporal dependencies between the media, defined time intervals in
`
`which media are presented to the user as well as media specific characteristics such
`
`as initial playback volume of an audio.
`
`The essential concepts of the modeling and solutions can be summarized as follows:
`
`Spatial and Temporal Composition: The description of a presentation
`
`Page 25 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`reflects al1 possible temporal relationships between the media and a possibIe
`
`spatial position and overlapping of two-dimensional media on the screen.
`
`Time Line: The selected representation mirrors the entire temporal course of
`
`the multimedia presentation. The solution to keeping track of a presentation is
`
`to store information only about changes during a presentation.
`
`Interaction Capabilities: One of the main features of a presentation on the
`
`client's site is the user interaction in the course of a presentation. Interactions
`
`are treated and modeled as normal media.
`
`Coarse and Fine Synchronization: Timing requirements are subdivided into
`
`fine and coarse synchronization. The coarse synchronization ensures that the
`
`time line representation of the presentation is put into action. Coarse synchro-
`
`nization relies on the mere schedule of the presentation stored in the description.
`
`The fine synchronization, however, obeys the maximum permissible deviation
`
`from reference media.
`
`Presentation Parameters: Initial settings such as playback volume for an
`
`audio, the playback speed of a video, and the like, are modeled.
`
`A presentation is composed on a high definition level using a definition tool such
`
`as HyTime [IS092]. The script-like description of the presentation is transferred
`
`from the MM-DBMS semer to the client, is interpreted there, and the presentation
`
`Page 26 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.2 AMOS Multimedia DBMS at GMD-PSI
`
`13
`
`is shown to the user as desired. The interpreting component at the client manages
`
`the preparation, startup and termination of the individual media presentations that
`
`belong to the integrated multimedia presentation.
`
`The architecture of the AMOS MM-DBMS is shown in Figure 2.2 [RKN96]. The
`
`VODAK DBMS [AUG95], which was also developed at GMD-IPSI, is used for the
`
`modeling and storage of discrete data. Thus, data types of the VODAK Modeling
`
`language (VML) are exchanged between client and server. The main tasks a t the
`
`server are data storage, scheduling, and cont inuous ob ject management (CO hil) , which
`
`uses extemal media servers for storage. This architecture enables easy integration of
`
`specific hardware such as real-time servers, tape or magneto-optical jukeboxes, and
`
`CD-ROM devices. The Continuous Transport Manager (CTM) enables access to
`
`Internet protocols as well as Asynchronous Transfer Mode (ATM).
`
`The "Spatial, Temporal and Interaction Script" Interpreter (STI) interprets the
`
`time line-based scripts (as generated from a VML schema) and triggers the Multi-
`
`media Playout Manager (MPM). This module is responsible for the handling of the
`
`client's environment, the synchronized playback, and the scheduling of concurrent
`
`requests. The MPM controls single media presenters (SPMs) which are implemented
`
`by utilizing libraries available for the client's platform, for example, a virtual audio
`
`device, a motion JPEG player, and an animation tool. -4 SPM get its data from
`,
`the COM. When the application asks for time-dependent data, this request is sent to
`
`Page 27 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`14
`
`Background
`
`Continuws Transp. Mgr. 1
`1 VODAK remote API
`; 1 Continuous Data
`1 l
`Controt Data
`
`VML SchemdApplication
`
`Figure 2.2: Architecture of the AMOS MM-DBMS
`
`ontinuous
`Database
`
`the VODAK DBMS via the VODAK remote API. Time-dependent data are sent via
`
`COM to the application. The COM initiates asychronous replacement and loading
`
`of distributed continuous data and adaptation in case of semer and network delays.
`
`In contrast to traditional object managers, the delivery of data like audio and
`
`video is "just in time". Object management enables an application to access data by
`
`loading these objects from disk into a main memory buffer and by replacing objects
`
`no longer needed. Updated objects are written back to disk. In a client/server based
`
`Page 28 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.3 Least/Most Relevant for Presentation
`
`15
`
`environment, objects must be transported in addition to the main memory of the
`
`requesting client. Because of their large volume, time-dependent data cannot be
`
`entirely loaded into the buffer. These objects are therefore decomposed into small
`
`blocks (for example audio sequences, frames) which are loaded and replaced in the
`
`buffer. Loading and replacement of objects is done by a strategy, called Least/Most
`
`Relevant for Presentation (L/MRP) [MKK95] which is explained in more detail in
`
`next section.
`
`2.3 Least /Most Relevant for Presentation
`
`Least/Most Relevant for Presentation (L/MRP) is a buffer management strategy that
`
`considers specific requirements such as continuity of presentations and immediate
`
`continuation of presentations after frequent user interactions. It is especially sui table
`
`for supporting highly interactive multimedia presentation.
`
`To explain the general idea of L/MRP, we use the presentation snapshot illus-
`
`trated in Figure 2.3. Since the continuous objects are too large to be stored in the
`
`client buffer as a whole, they are segmented into a sequence of manipulation units,
`
`called Continuous O bject Presentation Units (COPU). Single COPUs are requested
`
`continuously by the buffer manager. Al1 COPUs of a continuous object are indexed
`
`from O to ri-1, where n denotes the total number of COPUs. We denote the direction
`
`and skip parameter of a presentation by a single signed skip value. A positive value
`
`Page 29 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`16
`
`Background
`
`indicates the fonvard direction and a negative value indicates the backward direction.
`
`The absolute value of the skip value denotes the number of COPUs to be skipped. In
`
`Figure 2.3, the skip value is +2 which means the presentation rnoves forward and one
`
`of every two frames are skipped. We can also identih three different COPU types
`
`in Figure 2.3: COPUs located in the reverse direction (History), COPUs to be refer-
`
`enced in future (Referenced) and COPUs to be skipped because the absolute value of
`
`the skip value is great than one (Skip). LIEVIRP introduces the notion of a relevance
`
`function that assigns a value to every element of a set denoting its significance for
`
`replacement and preloading. L/MRP makes use of the relevance values in the way
`
`that least relevant COPUs are replaced and most relevant COPUs will be preloaded.
`
`The relevance value of a COPU also depends on specific presentation parameters like
`
`the number of the currently presented COPUs.
`
`current presentation
`point p
`
`presentation direction -
`
`COPU in reverse
`
`COPU to be
`referenced
`
`COPUtobe
`skipped
`
`Figure 2.3: Example state of a data flow
`
`Figure 2.4 shows the sets of History, Referenced and Skip COPUs for the given
`
`presentation point (508) and a skip value of +2. Each COPU, identified by the
`
`index on the x-axis, is associated with a relevance value refiecting the importance of
`
`Page 30 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.3 Least/Most Relevant for Presentation
`
`17
`
`the COPU with respect to the specific interaction set. Let us assume that due to
`
`some previous ongoing presentations, the COPUs with underlined numbers are in the
`
`buffer. The least relevant COPUs, that is the COPUs with the lowest relevance value,
`
`a t this moment are 527, 525, 523, 528, 521,500, 526, etc.. Thus, the next replacement
`
`candidates are 527, 523, 500, etc.. The most relevant COPUs for presentation are
`
`508, 510, 512, 514, etc.. Thus, the next preloaded COPUs will be 510, 514, etc..
`
`relevance
`
`1
`0.9
`
`4 a a a
`
`0 : .
`u I
`TS
`O
`
`1
`
`Y
`
`a
`
`0
`
`a
`
`w
`
`a
`
`m -
`
`O
`
`0 History
`
`Referenced
`
`O Skip
`
`Figure 2.4: .4n example of interaction sets with relevance values
`
`2.3.1 A General Mode1
`
`Let CO (continuous object) denote the sequence of al1 COPUs that constitute a
`
`continuous object. An element ci, i = O,. . . , ICOI - 1, denotes the COPU with index
`
`i within the continuous object CO. The state of a presentation is characterized by a
`
`Page 31 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`18
`
`Background
`
`tuple s =< p, skip >, with p E {O,. . . , ICOI - 1) denoting the index of the COPü
`
`at the current presentation point and skip E 2, skip # O, denoting the skip value.
`
`COPUs are related to one or more interaction sets A,. Each set A, has an associated
`
`criteria that is used to decide whether or not a COPU belongs to the set at a specific
`
`point of a presentation, and to specify the relevance value of the COPU with respect
`
`to S. Hence, an interaction set A, is defined as a binary relation relating a COPU to a
`
`relevance value. For example the interaction set Re f erenced, with s =< 508, +2 >.
`
`as visualized in Figure 2.4, is:
`
`To denote the relevance of a COPU within a given interaction set A,, a distance
`
`relevance junction d.,
`
`is defined. The domain of a distance relevance function is
`
`relative distance of individual COP Us to the current presentation point. Function
`
`d,, map distances to values in [O, 11:
`
`d,,
`
`(2) is the relevance value of a COPU with distance i to any possible presectation
`
`point p. The distance relevance values describe the degree of importance to keep
`
`COPUs in buffer. For example, the distance function &R,,,R,,,,,
`
`for al1 future
`
`referenced COPUs describes the degree of importance to keep specific COPUs in the
`
`buffer because of the high probability to be accessed in the current presentation. X
`
`Page 32 of 107
`
`PETITIONERS' EXHIBIT 1003
`
`
`
`2.3 LeadMost Relevant for Preseztation
`
`19
`
`distance relevaace function value of 1 means that the COPU is most relevant for
`
`presentation, and, hence, is not to be considered as a candidate for replacement, but
`
`has to be preloaded by L/MRP, if necessa-
`
`The formal definition of the interaction set As for a presentation state s is:
`
`A, = {((cj, dr, (i)) lcj E CO, j = g ( i , '11
`
`2 E NO)
`
`The index j of a COPU to be considered in A, is determined by a function g which
`
`depends on the dis
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
