Intelligent Prefetching and Buffering for Interactive
`Streaming of MPEG Videos
`
`Susanne Boll, Christian Heinlein, Wolfgang Klas, Jochen Wandel
`Databases and Information Systems (DBIS)
`Computer Science Department, University of Ulm, Germany
`fb heieikawadeg@if  aik. i .de
`
`ABSTRACT
`C i  deivey f edia ea  ike vide ve  e
`w k  fa i aiy haded by c ecia a ache
`ha deive he ea f wad ieed i hei w 
`ieay f  a. Th gh  e exiig ea ig ech
`gie ae abe  ada  vayig badwidh hey d  
` vide  h eaci   e ieaci  wih he c 
`i  ea .
`
`We have deve ed he EG /R aegy a ada
`ive efechig ag ih f  he EG 1 vide f  a i
`c biai  wih a ieige b (cid:11)eig echi e ha a
` w f   h ad  ick eaci   e ieaci  wih
`he ea . Wih /R [12] a a ach aeady ha
`bee eeed  deive ad b (cid:11)e h gee  c i
`  daa ea  ike  i  EG wih ecia f c  
`fa eaci   e ieaci .  c a he EG 1
`ec dig wih i di(cid:11)ee fa e ye ad he deedecie
`bewee fa e e he d   a e (cid:12)e gaied ada
`ai  f he c i  ea . weve he c exiy
` f EG 1 ca f  c eheive adaai  ad ecia
`a ed e f he /R ag ih  ake i a eÆcie
`e adig ad b (cid:11)eig echi e f  EG 1 vide .
`
`Wih he eaizai  f EG /R i he c ex f
`a i edia eeai  egie    f a i edia
`e i y we have a eÆcie ea  deive c i
`  ea  f ieacive i edia eeai  ve ex
`iig  ifa c e yig  ii ize ieaci  e
` e i e ad i ize adig/e adig  i  f a
`vide ea .
`
`INTRODUCTION
`1.
`  f  e e f i edia aicai  wi  ge be
`ai(cid:12)ed wih e acked eeai   ad a e y
`e    ieay c  ii  e bedded i Web age
`ad edeed by b we  g i. Rahe e aized i
`eacive i edia eeai  ae eeded deiveed 
`de ad f a i edia eve ve a  ew k  a
` e  (cid:13)exibe eeai  evi  e.  hi c ex he
`deivey f c i  i edia daa a we a i ee
`ai   be ai ed  he eci(cid:12)c e ie e f hi
`evi  e i. e. he vayig badwidh e e i e f
`he eve ad he ike.
`
`The ivai  f  w k i he aea f c i  de
`ivey f ieacive i edia eeai  ve a e
`w k e  f  eeach  jec \Gaey f Cadiac
`
`S gey" Cadi 1 [8] which ai  a deve ig a 
`ee baed ad daabae dive i edia if  ai 
`ye i he d ai f cadiac  gey. The e f he
`ye e e i edia c e f di(cid:11)ee af  
` ve di(cid:11)ee ew k c eci . Vide ea  ae f
`high i  ace i hi ed cai a evi  e. D ig
`he eaig  ce i i idieabe f  he e  ie
`ac  he ea  a  wach a cee agai  j  
`a he ieeig a f he vide . Theef e he ye
`     ieaci  ad  be e fiedy h d
`eac i a vey e ive way. ece he eeai  e
`vi  e de ad f  ea ig    f  c i 
` edia wih  iabe hadig f e ieaci .
`
`  he  jec c ex we deve ed a i edia ee
`ai  egie which ic de    f  c i  EG
`vide ea . F  hi we deve ed he EG /R
`ag ih  c i y deive EG 1 vide ea 
` ve a  ew k which we ee i hi ae.
`
`C aed wih e. g.  i  EG he ec dig f c 
`i  vide ea  wih EG 1 (cid:11)e a igi(cid:12)cay
`highe c ei  ae which i vey i  a f  a de
`ivey ve a ew k wih  eiay w badwidh. We
`ai a c i y deiveig he EG 1 ea i  a
` i ad a b (cid:11)eig hee i i a ieige way a
`he cie  ch ha he e i  vided wih a  h ad
`c i  eeai  h gh he e ca  iby cay
`  VCR ike ieaci   he ea ike fa f wad
`evee  j ig  a b k ak i he vide . The b (cid:11)e
`ig echi e h d hide he e e ad b (cid:11)eig f i
`ad ahe deive a c i  EG ea f he be
` aiy ha ca be c ey  vided  he aicai .
`
`Wih /R [12] we (cid:12)d a e adig ad b (cid:11)eig a
`egy f  c i  ea    ig ieaci  ha ha
` ve  ef  bee ha \adii a" aegie ike
`e. g. RU F F FU ec.Thi a ach h weve ai 
`a deiveig ad b (cid:11)eig h gee  c i  daa
`ea  ike  i  EG wih ecia f c   fa e
`aci   e ieaci . The c exiy f EG 1
`
`

`

`wih i hee gee  fa e ye f di(cid:11)ee i  ace
`vayig fa e ize ad ie fa e deedecie ca f 
`c eheive adaai  ad ecia a ed e f he
` igia /R ag ih  ake i a eÆcie e ad
`ig ad b (cid:11)eig echi e f  EG 1 vide . Thi ae
`ee  EG 1 eci(cid:12)c e adig ad b (cid:11)e a
`age e aegy EG /R f  EG 1 vide .
`
`The e aide f hi ae i gaized a f w: Sec
`i  2 dic e eaed w k. Seci  3 evii he igia
`/R ag ih ad give a h  veview f he a
` f EG 1 eeva   a ach.
`  Seci  4 
`ew EG /R a ach i eeed which c i
` f a f  a de ad a c e dig ag ih . Seci  5
`keche he i e eai  f he a ach ad Seci  6
`c c de he ae.
`
`2. RELATED WORK
`Reaed w k c ceed wih he deivey f i edia
`c e ve he ee c ve evea eeach a ache
`deaig wih he adaive ea ig f EG vide . A
`a a f he UASAR  jec a he eg  Gad ae
` i e [19] a EG aye f  adaive EG ea
`ig ve he ee ha bee deve ed which addee
`e ce cacee i he ed  ed deivey. The f c 
`ie  a  aiy f evice  S de ad a adaai 
` echai f he aye. T faciiae adaive ea ig
`he EG vide i  vided by he eve i di(cid:11)ee  a
`iie. The ea i adaed i he e  a di ei  by
`d ig B fa e (cid:12) he  fa e ad (cid:12)ay fa e.
`  addii  di(cid:11)ee aia e i  ae  vided a a
`ec d vaiabe  aiy di ei . B (cid:11)eig i aied 
`c eae ew k jie b  d e      fa eac
`i   e ieaci . A he a ach he edia
`Sea ig   c [4] deve ed a he Uiveiy f i
` i  vide adaive ea ig f EG vie  . 
`c gei  he   c c ide he di(cid:11)ee fa e ye
` f EG wih hei fa e iedeedecie ad i ia
`  a ach d  e i  a EG fa e (cid:12).
`The cie ide b (cid:11)e i e  yed y   h he jie
` f aivig daa b  d e   a w f  ii izig ie
`aci  e e i e ad e ad f daa afe  ibe e
`ieaci .
`
`  he c ecia aea ay a ache ca be f d ha
`dea vey we wih he ea ig f vide  e. g. icki e
`[1]  E baze [2]. Wih VDive [17] ad Rea [14] a
` ache exi ha ae f he e abe  ada he vide
`ea  (cid:13) c ai  f he avaiabe badwidh. F  i
`ace wih he i d ci  f he S eSea ech gy
`[15] Rea a w  ec de a vide ci ha eve f   
`ix di(cid:11)ee badwidh. Thi ea ca a  aicay be
`adj ed  c eae f  ew k c gei . weve
`a hi echi e ec de ie dij i ea  i e
`(cid:12)e i ead  a i(cid:13)ai  f he  age ize ad  ed 
`dacy. weve a he c ecia a ache ei ed
`have i c  ha hey eae   ieay vide f 
` a ad ae eihe deiged     ii izai  f
`he ieaci  e e i e    i ize he e(cid:11)  f 
`e adig  i  f a vide ea .
`
`Wih /R [3] a ieeig aicai  f /R ha
`ev ved. /R exed /R wih addii a ie
`
`aci  e i de     he eci(cid:12)c S e ie e
` f ceai e. weve he a ach d e   dea wih
`EG eci(cid:12)c e adig ad eace e aegie.
`
`3. L/MRP AND MPEG-1 REVISITED
`3.1 L/MRP
`/R ea/  Reeva f  eeai  [12] i a
`b (cid:11)e aage e aegy f  ieacive c i  daa
`(cid:13) w i a cie/eve evi  e. The cie e e
`ad eceive a c i  edi i  a i ad b (cid:11)e
`ha a f he ea ha i eeva f  he c e ad
`f  e eeai . The ai idea i  e e e ad
`ad b (cid:11)e h e i ha ae  eeva  be eeed
`i he ea f  e. The eciaiy f he /R aegy
`hee i ha he e adig ad b (cid:11)eig ake i acc 
`he ieaci  a e  iby caie   he ea 
`e. g. wich  fa f wad ayback  j   a b k ak.
`By ha ea he ieaci  e e i e c aed 
`c  b (cid:11)e aage e ad eace e aegie i
`ed ced cf. [12]. e adig ad eace e ae he w
`ak he b (cid:11)e aage e aegy ha  ae. D ig
`e adig he ex  eeva i f he c i 
`ea ae dee ied wheea he eace e aegy
`  decide which ae he ea eeva i a hee ae
`e ved f he b (cid:11)e  fee ace f  e eeva i.
`
`The /R b (cid:11)e aage e aegy ea he ea
`a a e ece f  caed C i  bjec eeai 
`Ui CU wih a acedig  beig f he i.
` kig a a e ece f CU f a eci(cid:12)c eeai 
` i  i i e he ige CU ae di(cid:11)eey eeva
`f  he c e eeai  which i exeed by aigig
`eevace va e  each CU. C ide Fig e 1 f  a
`i ai : The c e eeai   i i  = 43 ad
`he e i wachig he ea a d be eed i f wad
`dieci . The evey he CU i f wad dieci 
`c e  he c e eeai   i i ab ey eeva
`f  he c ig eeai . Thee CU f  he 
`caed efeeced e a hey ae ikey  be efeeced i
`he ea f  e. weve hee ae CU ha aeady
`have bee viewed. Thee be g  he hi y e f C
`U f he ea . A a e c d chage he dieci 
` f he ay  a ay i e hee CU ae i eeva
`f  he eeai . Fiay he fa e i f wad diec
`i  which ae kied d e  he d be eed ay  ae
`eeva   a he e c d wich    a eed ay
`back a ay i e. Thee c ideai  ca be c i ed f 
`f he ieaci  ye  ch a fa backwad j ig 
`b k ak ad he ike.
`
`The eevace f a CU wih eec  e f hee e i
`dee ied by a  caed diace eevace f ci  which
`exee a CU  eevace a a f ci  f he diace f
`he CU  he c e eeai   i . F  he ef
`eeced e he diace eevace f ci  i    y
`deceaig wih va e 1 f  he ex few CU  be e
`eed. A he fa e f he hi y ad kied e ae
`e ikey  be eeed hei diace eevace f ci 
`ae deceaig e aidy. Give e  e eevace
`f ci  f  each CU a vea eevace f ci  ca
`be cac aed e. g. by akig he axi eevace va e
`f  each CU. Thi g ba eevace f ci  i he ed
`by he e adig ad eace e f he b (cid:11)e. The e
`
`Page 2 of 10
`
`PETITIONERS' EXHIBIT 1017
`
`

`

`evace va e exee which CU ae ikey  be e
`eed whe akig i acc  he di(cid:11)ee ieaci 
`a e c d ef   he ea . /R ie  kee
`h e  eeva CU i he cie b (cid:11)e  achieve a
` ick ad  h eaci   he e ieaci . Deed
`ig  he b (cid:11)e ize h e CU ab ve a ceai eevace
`va e ae ke i he b (cid:11)e ad h e be w he heh d
`va e ae   aded/ae e ved f he b (cid:11)e  ake
` f  he e/  eeva CU. Wheeve he
`eeai   i   ceed he eevace va e ae e
`cac aed he CU  be e aded ae dee ied ad
`he CU wih he ea eevace va e i he b (cid:11)e ae
`eaced.
`
`Presentation Point
`
`p
`
`Relevance
`
`1
`
`0.5
`
`36
`
`37
`
`38
`
`39
`
`40
`
`41
`
`42
`
`43
`
`44
`
`45 46 47
`
`48 49 50 51 52 53 54 55 56 57 58 59
`60
`COPU Indices
`
`Interaction Sets:
`
`History
`
`Referenced
`
`Skip
`
`Fig e 1: /R: ieaci  e ad eevace
`va e
`
`3.2 MPEG-1
`The EG 1 adad [6] i a c dig f  a f  a di ad
`vide ea .  hi ae we ae c ceed wih vide
`ea  y [7]. The ai fea e f EG 1 ha i ie
`eig i hi ae i ha fa e ae  ge ideede
` f each he a i he cae wih e. g.  i  EG which
`i a eie f ige EG [18] i age. Fig e 2 h w a e
` ece f EG fa e ad hei iedeedecie which
`ae eeva f  dec dig he ea . A EG 1 vide e
` ece i geea c i f hee di(cid:11)ee fa e ye  B
`ad . U ay he fa e f e fa e   he fa e
`bef e he ex fa e f  a  caed G  f ic e
`G . Sice fa e ia c ded ic e ae ec ded
`i iaiy  EG i age hei dec dig i ideede f
` he fa e. The dec dig f  fa e edicive c ded
`ic e deed  he ecedig   fa e f he a e
`G . F  B fa e bidieci ay c ded ic e dec d
`ig deed  b h he ecedig ad he  cceedig 
` fa e.  ad B fa e a w a ch highe c ei 
`ae ha fa e by ex iig e  a edici  ig
` i  vec .
`  i i  a   e ha he diay
` de i which he fa e ae eeed i di(cid:11)ee f
`he biea de i which he fa e ae dec ded d e
` ie fa e deedecie. Fig e 2 i ae b h he
`diay de ad he biea de f a ea . The 
`de f  dec dig i vey i  a a a e adig aegy
`  f c e c ide he de f dec dig ad   y
` f diayig he fa e.
`
`A e adig ad b (cid:11)e aage e aegy f  EG 1
`vide  ay aei   he di(cid:11)ee fa e ye ad
`
`Display order:
`
`0
`I
`
`1
`2
`B B
`
`3
`P
`
`4
`5
`B B
`
`6
`P
`
`7
`8
`B B
`
`9
`I
`
`Bitstream order by frame number:
`0
`2
`6
`4
`5
`1
`3
`
`9
`
`7
`
`8
`
`...
`
`Fig e 2: EG fa e ye ad hei iedee
`decie
`
`hei ie fa e deedecie he biea de f  de
`c dig he ea  ad he fac ha he biae/daa ae
` f he vide ad he ize f he fa e ca heaviy vay.
`
`4. MPEG-L/MRP MODEL
`4.1 Overview of MPEG-L/MRP
`Basic idea
`S fa he /R a ach ha  ve [12]  be  ei 
` adii a e adig ad b (cid:11)eig aegie eeciay
`whe i c e  fa eaci   e ieaci . The ba
`ic idea f EG /R i   vide he a e ieaci 
`e ivee a achieved wih /R b  i aic a 
`ake i acc  he eci(cid:12)c fea e f he EG vide
`ea . The di(cid:11)ee fa e ye wih hei ie fa e
`deedecie ad hei di(cid:11)ee i  ace f  he ee
`ai  ae he ai i e whe adaig /R  EG.
`The EG /R aegy ex i he k wedge ab 
`he i  ace ad deedecie f he fa e  ch ha
`he vide ca be i ay eeed de he avaiabe
`ew k badwidh. Theef e he ieaci  e ad he
`a ciaed eevace f ci  f he /R aegy ae
`adaed  ch ha hey e(cid:13)ec hi eci(cid:12)c i  ace f
`fa e f  he eeai . Whe fa e d   aive i
`i e a he cie e  a adaai  i ed i de 
` aiai a c i  eeai .
`
`Choosing the appropriate COPU size
`The (cid:12) i e f adaig /R  EG ea  i he
`kid ad ize f he daa ha f   a CU. The CU
`ae he baic i f  a ai  f he ea .  k
`ig a EG 1 hee ae di(cid:11)ee  ibiiie  de(cid:12)e a
`CU:
`A CU c e d  a G . The ahe big ize
` f he CU igh be a  be . f  ch a CU ca 
`be deiveed  he cie i aveage haf a ec d f he
`vide i iig. Thi ize i a  iabe f  e. g. a fa
`f wad eeai  f he vide  ice a fa e had  be
` aded  he cie h gh y a  be f he w d be
`eeded.
`A CU c e d  a a f a G . [5]   ed
` e BB  BB g . weve he g  ad hee
`f e he CU ae he deede  each he. Ad hi
`eic he   ed c dig che e f he EG ea
` BBBB...BB ae.
`ee i he
`A CU c e d  a fa e.
`CU ae deede  each he ike he fa e f he
`EG ea ae. weve hi ga aiy a w f  fa
`
`Page 3 of 10
`
`PETITIONERS' EXHIBIT 1017
`
`

`

`ad ageed eaci   vayig ew k badwidh ad
` e ieaci .
`
`We decided  e he hid aeaive a i (cid:11)e he 
`a iae  ibiiy  c eae (cid:13) c ai  i he
`avaiabe ew k badwidh ad a he a e i e (cid:11)e
`   f  fa ad  h eaci   e ieaci  
`he ea . Thi decii  eve a he bai f  he f  a
` de  f w.
`
`4.2 The MPEG-L/MRP Model
`Overview
`  hi  beci  he EG /R de wi be deve
` ed e by e. F wig  e ei iay de(cid:12)ii 
`we i d ce eeai  e a a ea  c ec h e
`fa e which have  be diayed f  a aic a kid f
`eeai  f a vide   ch a   a ayback d be
`eed eeai  ad  . Sice  ad B fa e ca 
`be dec ded ideedey addii a   fa e igh
`be eceay  ac ay dec de ad diay he fa e f
`a eci(cid:12)c eeai  e. Thee ie fa e deedecie
`ae ca ed by deedecy e eadig  he  i  f
`c ed eeai  e.
`
`Afewad aic ad dya ic eevace f ci  ae de
`(cid:12)ed a a ea   aify he eevace f fa e c 
`aied i a aic a eeai  e. Whie aic ee
`vace f ci  ae ed  aig eevace va e  fa e
`  dig a aic efeece fa e eeeig e. g. a
`b k ak dya ic eevace f ci  ae eeded  c
` e he eevace va e f fa e   dig he c e
`eeai   i which i c ay vig i i e d ig
`a   a eeai  f he vide . B h aic ad dya ic
`eevace f ci  ae baed  geeic eevace f ci 
`which de(cid:12)e eevace va e ideede f a aic a
`efeece fa e  he c e eeai   i.
`
`Fiay a g ba eevace f ci  i i d ced which c
`bie he eevace va e f aic ad dya ic eevace
`f ci  i a ige vea eevace va e f  each fa e
` f he vide which wi be ed by he EG /R ag
`ih  dee ie e adig cadidae ad eace e
`vici .
`
`Re ak: F  eade fa iia wih he deai f he igi
`a /R de [12] i h d be  ed ha he f  a
` de ev ved i evea aec i de  ada i  he
`ecia e ie e f he EG vide f  a.  aic
`a he  i  f ieaci  e c aiig ai f fa e
`  CU ad eevace va e dee ied by  caed
`diace eevace f ci  ha bee i i w h g
` a c ce: eeai  e c aiig fa e y 
`he e had ad eevace f ci  aigig eevace
`va e  fa e  he he had. By ha ea ie
`fa e deedecie ca be ca ed  ie eaiy by i
`d cig deedecy e which ae c eey ideede
` f he c ce f eevace va e. F he e geeic e
`evace f ci  which ae aaed  a aic a fa e
`ad eiced  a aic a eeai  e i de  b
`ai aic ad dya ic eevace f ci  ae  ewha
`eaie  e ha he c e dig diace eevace f c
`i  f he igia de eeciay whe fa e ae  
`e idiay diib ed wihi a eeai  e.
`
`Preliminary Definitions
`e a  a  = f1; 2; 3; : : : g be he e f a a 
`be ad //Z = f: : : ; 2; 1; 0; 1; 2; : : : g he e f iege
` be. F  k 2 //Z e //Zk de e he e f iege f
`0  k i. e.
`
`//Zk = (cid:26) f0; 1; : : : ; k 1; kg
`
`fk; k  1; : : : ; 1; 0g
`
`f  k (cid:21) 0;
`f  k < 0:
`
`F  a  be  (cid:18) //Z f iege e (cid:31) : //Z ! f0; 1g be
`he chaaceiic f ci  f  aigig a va e f 1  a
` e be f  ad 0  a he  be:
`
`(cid:31) x = (cid:26) 1
`Presentation Sets
`F  a aic a vide c iig  2  fa e e
`
`f  x 2 ;
` hewie:
`
`0
`
`F = f0; 1; : : : ;  1g
`
`be he e f i fa e  be i diay de. F he
` e e    ad B be aiwie dij i  be f F
`eeeig he e f a   ad B fa e f he vide 
`eecivey. A ig ha a vide d e   c ai he
`fa e ye i aic a D fa e i h d:
`
`F = [  [ B:
`
`A eeai  e i a  be S (cid:18) F f fa e which have
` be diayed f  a aic a kid f eeai  f he
`vide . F  iace he eeai  e
`
`F = ff 2 F j f = i ; i 2 0g = f0; ; 2; : : : g
`
`eci(cid:12)e he e f a fa e f which have  be diayed
`f  a f wad  backwad eeai  f he vide wih a
`eaive eed   ki fac   f  2 .
`
`Dependency Sets
`D e  ie fa e deedecie i de  be abe  de
`c de ad diay he fa e f a aic a eeai 
`e S i igh be eceay h weve  dec de addii a
`fa e. Thee ie fa e deedecie ae ca ed by he
`deedecy e Df  (cid:18) F c aiig a fa e g 2 F which
`ae diecy  aiivey eeded  dec de ad diay
`fa e f 2 F . Uig he a xiiay de(cid:12)ii 
`
` f  = axfg 2 j g (cid:20) f g
`
`ad
`
` f  = ifg 2 [  j g (cid:21) f g
`
`ecifyig he c e ecedig fa e f fa e f ad he
`c e  cceedig   fa e f fa e f  eecivey Df 
`ca be de(cid:12)ed a f w:
`
`Df  = ff g [ fg 2 [  j f  (cid:20) g (cid:20)  f g:
`
`Sice f  = f =  f  f  a fa e f 2  i h d
`Df  = f i ha cae which ea ha  addii a
`fa e i eeded  dec de a fa e. F  a  fa e f 2 
`i h d f  < f =  f  ad h  Df  c ai f ad a
`ecedig  fa e   ad ic dig he c e eced
`ig fa e. The a e h d f  a B fa e f 2 B b  ice
` f  < f <  f  i ha cae Df  c ai he c e
` cceedig   fa e f f   .
`
`Page 4 of 10
`
`PETITIONERS' EXHIBIT 1017
`
`

`

`Re ak: F  f  ad  f   be we de(cid:12)ed f  a fa e
`f 2 F  he (cid:12) fa e f a vide  be a fa e ad i
`a fa e  be a   fa e. Wih  hee eic
`i  he vide w d   be adad c f  ig h weve.
`
`Closed Presentation Sets
`The c  e (cid:22)S f a eeai  e S (cid:18) F ca be de(cid:12)ed a
`he e
`
`(cid:22)S = [f 2S
`
`Df 
`
`c aiig a fa e which ae ac ay eeded f  a aic
` a kid f eeai  eihe diecy beca e hey have
` be diayed  idiecy d e  ie fa e deede
`cie. A eeai  e S i caed c ed if S = (cid:22)S h d.
`
`Give he de(cid:12)ii  f F ab ve he c  e (cid:22)F c ie
`f  exa e a fa e which ae ac ay eeded f  a e
`eai  f he vide wih a eaive eed f . eecig
`(cid:22)F wih e f he e     B yied he aiwie di
`j i e  = (cid:22)F \   = (cid:22)F \   ad B = (cid:22)F \ B
`c aiig a    B fa e eecivey eceay f 
` ch a eeai .
`
` f he c dig che e f a vide i a c a eeii  f
`he ae i aed i Fig e 3 i f wed by a (cid:12)a
`fa e he eeai  e F2 c ai a fa e deiced
`a haded b xe. Sice hi e c ie a ad  fa e
` f he vide  i i aeady c ed i. e. i h d (cid:22)F2 = F2
`i ha cae. The eeai  e F3  he he had
`i aed i Fig e 3 ii i   c ed ice addii a
` fa e idei(cid:12)ed by back a w ae eeded  dec de he
`B fa e ha ae  be eeed a a ki fac  f 3. Tha
` ea ha he c  e (cid:22)F3 c ai 6 iead f 4 fa e 
` f each 12 fa e ae BBBBBBBBB e ig i a
` vehead f  ghy 50 .2
`
`(i)
`
`(ii)
`
`2F :
`I
`
`F :3
`I
`
`BBB
`
`P
`
`BB
`
`B
`
`P
`
`B
`
`B
`
`B
`
`B B B
`
`P
`
`B B B
`
`P
`
`B B B
`
`frames to be
`presented
`additional
`frames needed
`for decoding
`
`Fig e 3: eeai  e a di(cid:11)ee ki ae
`
`Relevance Functions
`A geeic eevace f ci  i a f ci  (cid:26) : //Z ! [0; 1] a
`igig a eevace va e (cid:26)x 2 [0; 1]  each iege 
`be x 2 //Z. Tyicay a geeic eevace f ci  i eihe
`    y iceaig f  x (cid:20) 0 ad ze va ed f  x > 0
`  ze va ed f  x < 0 ad    y deceaig f 
`x (cid:21) 0. F  iace he iea f ci 
`
`ax = (cid:26) axb 1 x=a; 0
`(cid:21)b
`
`0
`
`f  x 2 //Za;
` hewie;
`
`wih a eak va e f b 2 [0; 1] f  x = 0 ad  iive va e
`f  x 2 //Za  fag a 2 //Z ae yica exa e f geeic
`
`

`

`Examples
`Example 1 – Forward Presentations
`F  a ki fac   2  e !(cid:26)  !(cid:26)  ad !(cid:26)B be geeic
`
`
`
`eevace f ci 3 which ae ze va ed f  x < 0 ad
`    y deceaig f  x (cid:21) 0. Sice fa e ae ge
`eay e i  a ha  fa e which ae i   e
`
`
`i  a ha B fa e he eai hi !(cid:26) x (cid:21) !(cid:26) x (cid:21)
`!(cid:26)B
` x ha h d f  a x 2 //Z cf. Fig e 5 f  a yica
`exa e ig a ki fac   = 1.
`
`Reevace
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`!(cid:26)
`1
`
`!(cid:26)
`1
`
`!(cid:26)B
`1
`//Z
`
`3
`
`6
`
`9
`
`12
`
`15
`
`18
`
`Fig e 5: Geeic eevace f ci  !(cid:26)
`1 !(cid:26)
`1  !(cid:26)B
`1
`
`Baed  hee geeic eevace f ci  dya ic ee
`vace f ci 
`
` ad
`ca be de(cid:12)ed ig he
`eeai  e   ad B eecivey de(cid:12)ed ea
`ie cf. Fig e 6 agai ig  = 1:
`
`
`!Æ
`
` 
`!Æ
`
`B
`!Æ
`
`f;  = !(cid:26)
`f  (cid:31)  f ;
`f;  = !(cid:26)
` f  (cid:31) f ;
`f;  = !(cid:26)B
` f  (cid:31)B f :
`
` 
`!Æ
`
`
`!Æ
`
`B
`!Æ
`
` 1 !Æ
`!Æ
`
`B1
`1 !Æ
`
`F
`
`
`
`3
`
`6
`
`9 12 15 18
`
`Reevace
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`B1
`!Æ
`
`
`
`1
`!Æ
`
`
`
` 1
`!Æ
`
`Fig e 6: Dya ic eevace f ci 
`
`Deedig  he c e eeai   i  hee f c
`i  exe he eevace va e f h e   ad B fa e
`eecivey which wi be eeded i he ea f  e f  a f 
`wad eeai  f he vide wih a ki fac  f . Sice
`he eeai  e   ad B ae aiwie dij i a
`  e f he va e
`f; 
`f;  ad
`f;  wi
`be  iive f  each fa e f 2 F  whie he he ae ze .
`
`B
`!Æ
`
`
`!Æ
`
` 
`!Æ
`
`B1
`!Æ
`
`1
`!Æ
`
` 1
`!Æ
`
`C biig he f ci 
`
` ad
`i a g ba e
`evace f ci  ig weigh fac  !(cid:25)
`1 = !(cid:25)
`1 = !(cid:25)B
`1 = 1
`yied he f ci  !(cid:13)1 h w i Fig e 7:
`
`f; (cid:17)
`
`B1
`!Æ
`
`f; ;
`
`1
`!Æ
`
`!(cid:13)1f;  = ax(cid:16)!
`Æ
`1 f; ;
`
`

`

` igh be eibe i de  give b k ak he a e ve
`a eevace a he c e eeai   i.
` f  he
` he had he  be f b k ak i vey age  ae
`weighig fac  have  be ch e i de  av id ha
`b k ak fa e c eey  h  fa e which ae e
`eva f  he c e eeai .
`
`4.3 MPEG-L/MRP Algorithm
`Preloading and Replacement of Frames
`The EG /R ag ih  which i baed  he b (cid:11)e
` aage e ag ih eeed i [12] iegae e ad
`ig ad eace e f fa e. Uig he g ba eevace
`f ci  (cid:13) h e fa e f a EG vide ae dee ied
`ha ae  be aded ex a hey ae  eeva f 
`he eeai . f he b (cid:11)e i f  he g ba eevace
`f ci  i a ed  dee ie h e fa e ha ae 
`be e ved  ake  f  e eeva e. i
`ig 4.1 h w he eeia a f he ag ih which ae
`exaied i he f wig.
`
`The b (cid:11)e c aiig he c ey aded fa e i e
`eeed by a bjec b f ye B ffe  yig eh d
`f  ad   ad d  exaied be w. T
`i ify  ai  b i a ed a a e c iig a c 
`ey aded fa e.
`
`The f ci   ad ReevaFa e which i caed
`wheeve he c e eeai   i  chage ai
`ai w fa e ad  wih c e dig eevace va
` e  ad T cf. Fig e 11. The ad heh d  e
`ee he axi eevace va e ax
`(cid:13)f;  f a
`f 2F b
`fa e f 2 F  b f he vie which ae c ey  
` aded whie he   heh d T eee he ii
`(cid:13)f;  f a fa e f 2 b which ae
`eevace va e i
`f 2b
`c ey aded. Th  i i k w ha a fa e wih
`a g ba eevace va e geae ha  ae aeady aded
`whie h e havig a g ba eevace va e we ha T ae
`  aded. The ad cadidae 2 F  b ad he   vici
` 2 b ae fa e wih g ba eevace va e (cid:13);  = 
`ad (cid:13);  = T  eecivey.
`  he ah  h w i
`Fig e 11 i h d f  exa e =   9 ad  =  5.
`
`Reevace
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`9
`
`6
`
`3
`
`
`
`3
`
`6
`
`9
`
`# 
`
`" T
`
`F
`
`Fig e 11:  ad ad   heh d  ad T
`
`The f ci  eeaedy eec a ad cadidae ie 5
`ad ad i i he b (cid:11)e ie 11 ca ig he ad heh
` d  = ax
`(cid:13)f;   gad ay deceae. A g a hee
`f 2F b
`i   e gh b (cid:11)e ace f  he ad cadidae  h weve
`ie 6 a   vici  i eeced ie 7 ad  ed  f
`
`
`
`Æ
`
`1
`1 Æ
`
`
`
`ÆB
`1
`
`F
`
`Reevace
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`"
`
`"
`
`18
`
`15
`
`12
`
`9
`
`6
`
`3
`
`
`
`Fig e 9: Dya ic eevace f ci 
`Æ
`wih
`1 di(cid:12)ed
`
`
`
`
`
`Æ
`1 
`
`
`
`Æ
`1 
`
`
`
`ÆB
`1
`
`B1
`!Æ
`
`1
`!Æ
`
` 1
`!Æ
`
`
`
`
`
`
`
`C biig he f wad f ci 
`
` ad
`ad he
`Æ
`Æ
`ÆB
`backwad f ci 
`1 
`1  ad
`1 i a g bae eevace
`
`
`
`
`f ci  ig weigh fac  !(cid:25) 1 = !(cid:25)1 = !(cid:25)B1 = 1 ad (cid:25) 1 =
`
`
` (cid:25)1 = (cid:25)B1 = 0:75 exeig ha he vea eevace f
`backwad ayig h d be weighed 0.75 c aed wih
`he vea eevace f f wad ayig yied he f ci 
`(cid:13)1 h w i Fig e 10:
`
`(cid:13)1f;  = ax!(cid:13)1f; ;
`Æ
`0:75
`1 f; ; 0:75
`
`
`
`
`
`Æ
`1 f; ; 0:75
`
`
`
`ÆB
`1 f; 
`
`Reevace
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`9
`
`6
`
`3
`
`
`
`3
`
`6
`
`9
`
`F
`
`Fig e 10: G ba eevace f ci  (cid:13)1
`
`Example 3 – Bookmarks
`Seig a b k ak a a eci(cid:12)c fa e b 2 F h d a
` w a e  j   ha fa e a ay i e ad c 
`i e he eeai  f he vide a ha  i. Thee
`f e fa e   dig a b k ak fa e b h d have
`he a e eevace va e a h e   dig he c e
`eeai   i . Th  deedig  he eeai 
`dieci  f wad/backwad ad he ki fac   2 
`which h d be a wed afe j ig  a b k ak aic
`
`
`eevace f ci  !(cid:27)T ad  iby (cid:27)T h d be de(cid:12)ed
`f  each b k ak fa e b baed  he geeic eevace
`f ci  !(cid:26)T
` ad (cid:26)T
`  eecivey i d ced ab ve:
`
` f  = !(cid:26)T f b (cid:31)T f 
`
`!(cid:27)T
`
` (cid:27)T f  = (cid:26)T
` f b (cid:31)T f 
`
`f  T = ; ; B;
`f  T = ; ; B:
`
`  de  ic de hee f ci  i a g ba eevace
`f ci  ike e. g. (cid:13)1 hei weighig fac  !!T
` ad !T
`
`h d deed  fac  ike he fe ecy b k ak ae
`j ed   he  be f b k ak which have bee e
`ad he avaiabe b (cid:11)e ize. f f  iace he  be
` f b k ak i  a wih eec  he b (cid:11)e ize ad
`
`
`b k ak ae efeeced fe ey fac  !!T = !T = 1
`
`Page 7 of 10
`
`PETITIONERS' EXHIBIT 1017
`
`

`

`he b (cid:11)e ie 9 ca ig he   heh d T = i
`f 2b
` gad ay iceae. Sice fa e ize igh vay he