(12) United States Patent
`Hunt et al.
`
`I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII IIIIII IIII 11111111
`US006442658Bl
`US 6,442,658 Bl
`*Aug. 27, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR
`IMPROVING PLAYBACK OF INTERACTIVE
`MULTIMEDIA WORKS
`
`(75)
`
`Inventors: V. Bruce Hunt, Menlo Park; Ken Day,
`Aptos; Harry R. Chesley, San
`Francisco, all of CA (US)
`
`11/1995 Blades et al.
`5,465,358 A
`1/1996 Vitter et al.
`5,485,609 A
`1/1996 Cossock
`5,487,166 A
`1/1996 Turtle et al.
`5,488,725 A
`5,732,267 A * 3/1998 Smith ............................ 713/1
`6,128,712 A * 10/2000 Hunt et al.
`................. 711/158
`* cited by examiner
`
`(73)
`
`Assignee: Macromedia, Inc., San Francisco, CA
`(US)
`
`Primary Examiner----Hiep T. Nguyen
`(74) Attorney, Agent, or Firm-The Hecker Law Group
`
`( *)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21)
`
`Appl. No.: 09/563,598
`
`(22)
`
`Filed:
`
`May 1, 2000
`
`(63)
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`Related U.S. Application Data
`
`Continuation of application No. 08/792,484, filed on Jan. 31,
`1997, now Pat. No. 6,128,712.
`
`Int. Cl.7 . ... ... .. ... ... ... ... .. ... ... ... ... ... .. ... ... .. G06F 12/02
`U.S. Cl. ....................... 711/158; 711/137; 711/204;
`710/40; 369/14; 369/15; 369/30; 369/34
`Field of Search ................................. 711/158, 137,
`711/204; 710/40; 369/14, 15, 30, 34
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,710,763 A
`5,241,671 A
`5,265,065 A
`5,418,948 A
`5,442,771 A
`5,444,617 A
`5,446,891 A
`5,463,777 A
`
`12/1987 Franke et al.
`8/1993 Reed et al.
`11/1993 Turtle
`5/1995 Turtle
`8/1995 Filepp et al.
`8/1995 Merialdo
`8/1995 Kaplan et al.
`10/1995 Bialkowski et al.
`
`(57)
`
`ABSTRACT
`
`The present invention comprises a system for delivering an
`interactive multimedia work from a storage device, for
`example a hard disk drive, a CD-ROM drive, a network
`server, etc. to a playback device, for example a personal
`computer, in a manner that provides improved performance
`regardless of the playback sequence selected by a user. In
`one embodiment of the present invention, for each segment
`of an interactive multimedia work, a probability factor is
`assigned to each possible alternative succeeding segment. In
`addition a retrieval and delivery time cost factor is also
`assigned to each possible succeeding segment. In one
`embodiment of the invention, the time cost factor for each
`resource is assigned a fixed value. In another embodiment,
`the time cost factor is recalculated periodically to reflect
`changes in location and status of resources. The probability
`and time cost factor for each possible succeeding segment
`are combined to produce a relative priority ranking.
`Resources for the possible succeeding segments are pre(cid:173)
`loaded according to the relative priority ranking. As a result,
`the latency time between the time a segment is selected as
`a result of user input and the time at which execution of the
`segment begins is reduced and the performance of a multi(cid:173)
`media work improved. In one embodiment of the invention,
`in addition to delivering resources in the order of a relative
`priority ranking, the resources are also stored according to
`the relative priority ranking, thereby reducing the average
`seek time needed to find and retrieve resources and further
`improving playback performance.
`
`23 Claims, 17 Drawing Sheets
`
`400
`
`405
`
`415
`
`420
`
`425
`
`430
`
`435
`
`LOAD RESOURCES FOR
`CURRENT SEGMENT
`
`BEGIN EXECUTION OF
`CURRENT SEGMENT
`
`OBTAIN PROBABILITY
`FACTORS FOR POSSIBLE
`SUCCEEDING SEGMENTS
`
`CALCULATE PRIORITY
`FACTORS FOR POSSIBL~
`SUCCEEDING SEGMENTS
`
`PRE·LOAD RESOURCES
`FOR SEGMENT WITH
`LARGEST PRIORITY FACTOR
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 1 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 1 0f 17
`
`US 6,442,658 B1
`
`120
`120
`
`S2
`
` S2
`
`110
`
`130
`
`P13
`0.3
`
`115
`
`115
`
`S1
`
`P11
`0.1
`
`S3
`
`135
`' o
`140
`
`i
`-
`
`S4
`
`FIG. 1
`FIG. 1
`
`TTI-1030, Page 2
`
`

`

`U.S. Patent
`
`Aug. 2 7, 2002
`
`Sheet 2 of 17
`
`US 6,442,658 Bl
`
`210
`
`212
`
`214
`
`TEXT
`QUICKTIME MOVIE
`JPEG
`S1 ,___ __ __._ _ __ ---T'" ___ . ._ __ _
`
`110
`
`WAVAUDIO
`
`MIDI AUDIO
`
`216
`
`220
`
`\
`
`218
`
`222
`
`GIF
`
`MIDI
`
`120
`
`s2-------....-----
`
`MPEG VIDEO
`
`WAV
`
`WAV
`
`224
`
`226
`
`228
`
`'\
`TEXT
`
`230
`
`S3
`
`130 -
`
`232
`
`(
`
`234
`
`(
`
`VFW VIDEO
`
`PDF DOCUMENT
`
`WAVAUDIO
`
`S4
`140---
`
`PPT SLIDE SHOW
`
`MIDI AUDIO
`
`\_
`236
`
`240\
`
`~
`
`242
`
`0
`
`I
`5
`
`TIME (SECS.)
`I
`15
`
`I
`10
`
`20
`
`I
`25
`
`I
`30
`
`FIG. 2
`
`250
`(~
`
`

`

`Aug. 2 7, 2002
`
`Sheet 3 of 17
`
`US 6,442,658 Bl
`
`M
`
`7
`
`69SU
`
`1B85
`
`U.S. Patent
`US. Patent
`
`0
`C\J
`C"")
`
`
`
`mo_>mn_:3me
`
`w
`(.)
`> w
`0
`>-:s a..
`
`U)
`0
`
`
`
`mo_>woHonchoOED<
`
`w
`(.)
`> w
`0 .....
`::)
`a..
`.....
`::)
`0
`0
`0
`::)
`<(
`
`0
`T""
`C"")
`
`o5
`
`m5
`
`LO
`T""
`C"")
`
`2
`
`w
`(!)
`<( a:
`~
`
`CJ')
`CJ')
`<(
`:E
`
`m0<¢OHmmw<2E
`
`:E
`<( a:
`
`::)
`a..
`(.)
`
`
`
`wo<umm._.2_vEO>>._.mz
`
`w
`(.)
`<(
`
`LL a: w .....
`z
`::::.c:: a:
`
`~ w z
`
`2.mg08man
`
`9%
`
`0 ,q-
`
`C"")
`
`1.
`
`mmmm
`
`m8m
`
`~
`0
`a:
`6
`(.)
`
`
`
`Bm0_>mo.252.
`
`w
`(.)
`> w
`0 .....
`::) a.. z
`
`
`
`6.!ImmGE
`
`('I) .
`CJ
`LL
`
`mm._.2_mn_
`a:
`w ..... z
`a: a..
`
`omm
`
`0
`LO
`C"")
`
`TTI-1030, Page 4
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 2 7, 2002
`
`Sheet 4 of 17
`
`US 6,442,658 Bl
`
`400
`
`405
`
`410
`
`415
`
`420
`
`425
`
`430
`
`435
`
`LOAD RESOURCES FOR
`CURRENT SEGMENT
`
`BEGIN EXECUTION OF
`CURRENT SEGMENT
`
`IDENTIFY POSSIBLE
`SUCCEEDING SEGMENTS
`
`IDENTIFY RESOURCES
`REQUIRED FOR POSSIBLE
`SUCCEEDING SEGMENTS
`
`N
`
`N
`
`YES
`
`YES
`
`YES
`
`CALCULATE COST FACTORS
`FOR POSSIBLE
`SUCCEEDING SEGMENTS
`
`LOAD RESOURCES FOR
`SEGMENT WITH NEXT
`HIGHEST PRIORITY FACTOR
`
`OBTAIN PROBABILITY
`FACTORS FOR POSSIBLE
`SUCCEEDING SEGMENTS
`
`CALCULATE PRIORITY
`FACTORS FOR POSSIBLE
`SUCCEEDING SEGMENTS
`
`PRE-LOAD RESOURCES
`FOR SEGMENT WITH
`LARGEST PRIORITY FACTOR
`
`460
`
`END PRE-LOADING
`
`FIG. 4
`
`

`

`U.S. Patent
`
`Aug. 2 7, 2002
`
`Sheet 5 of 17
`
`US 6,442,658 Bl
`
`FIG. 5A
`
`S1
`7.861 MB
`
`S3
`7.510 MB
`
`S4
`2.629 MB
`
`510
`
`520
`
`530
`
`FIG. 58
`(PRIOR ART)
`
`S4
`5.355 MB
`
`_)
`
`540
`
`S1
`7.861 MB
`
`510 _)
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 6 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 6 0f 17
`
`US 6,442,658 B1
`
`,....
`r--(cid:173)
`co
`
`671
`
`.....
`0
`
`0.1
`
`,..._
`en
`
`S7
`
`R co
`
`,....
`lO co
`
`0
`lO co
`
`$5
`LO en
`
`0 co
`co
`
`660
`
`-
`
`622
`
`631
`
`co
`0
`
`g
`co
`
`M en
`
`,....
`C") co
`
`O1—
`CD
`
`31
`
`0 ,....
`co
`
`.....
`en
`
`672
`
`C)
`0
`0.9
`
`FIG.6
`CD .
`(9
`LL
`
`0.8
`
`co
`0
`
`652
`
`C\I
`lO co
`
`TTI-1030, Page 7
`
`

`

`,~:
`
`708
`
`S7
`
`709
`
`S4
`
`711
`
`S3
`
`I
`I
`I
`I
`I
`0.06
`,.
`I
`I
`0.14
`705 I
`I
`I
`
`I
`
`0.16
`1712
`
`I
`0.05
`I
`I
`:
`I
`I
`0.112
`I
`I
`1716
`I
`0.096
`
`704
`
`I
`I
`I
`I
`0.2
`I
`I
`0.2
`I
`I
`I
`I
`0.36
`
`I
`
`S6
`
`S4
`
`S5
`
`S1
`
`702
`
`S2
`
`703
`
`S3
`
`701
`
`S1
`
`I
`I
`I
`I
`0.4
`I I
`I
`I
`0.6
`
`J
`
`I
`
`700
`
`I
`
`,
`'<
`707
`
`710
`
`I
`
`'
`
`720
`
`706 ool[J
`024~o~q
`
`715
`
`S3
`
`S5
`
`717
`
`I
`
`I I
`I
`I
`I
`I
`I
`I
`
`I I
`
`S1
`
`I
`
`I
`
`I
`
`S7
`
`740
`
`750
`
`I
`I
`I
`I
`
`FIG. 7A
`
`713
`
`730
`
`714 0
`~13(
`
`I
`I 719
`::::i
`I
`I
`
`o.0:.1j
`
`721
`I
`0.045
`
`718
`718
`
`S1
`
`I
`I
`I
`I
`0.054
`
`S5
`
`I
`I
`
`S1
`
`S1
`
`I
`I 722
`I
`0.077
`
`725
`
`_ _ /
`
`$52qcm3 am$53“5
`
`723
`
`S1
`
`724
`J
`
`S7
`
`760
`
`)
`
`gm.5:2:
`
`3m.3“23
`
`d
`•
`r:JJ.
`•
`~
`......
`~
`=
`~
`......
`
`>
`=
`~
`N
`~-..J
`N
`0
`0
`N
`
`~
`~
`
`'JJ.
`
`=-
`....
`-..J
`....,
`0
`'"""'
`-..J
`
`e
`rJ'J.
`_,.a-...
`,I;;..
`,I;;..
`_,.N
`a-...
`(It
`~
`~
`i,-
`
`TTI-1030, Page 8
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 8 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 8 0f 17
`
`US 6,442,658 B1
`
`C\I en
`
`~
`
`r
`
`'-
`
`r
`
`\...
`
`r
`
`r
`
`\..
`
`C")
`
`en
`
`33
`
`~
`
`'LO
`~
`ci
`
`0.043
`
`0.065
`
`r
`
`,....
`en
`
`31
`
`Dj
`
`''
`LO
`,q-
`0
`ci
`
`,....
`en
`
`82
`.,
`
`0045
`
`S1.
`
`~
`
`'-
`
`~
`
`\...
`
`r
`
`'-
`
`C\I
`en
`
`r
`
`'-
`
`r
`
`""
`
`C")
`
`;g
`ci
`
`'
`:g
`
`C)
`
`
`
`0.1340.054
`
`,....
`en
`
`'
`~
`,....
`ci
`
`r
`
`.,
`
`r-
`en
`S7
`
`~
`
`\...
`
`~
`
`~
`0.034
`0
`ci
`
`r
`
`r
`
`C\I en
`
`r-,.
`en
`
`~
`
`~
`
`LO
`en
`
`.,
`
`36$301333531
`
`~
`
`co
`C\I
`C)
`
`,q-
`en
`
`.,
`
`LO
`(")
`C)
`
`' co
`,....
`0
`ci
`
`LO
`en
`
`r
`
`0.108
`
`85
`
`'--
`
`~
`
`co
`co
`,....
`C)
`
`C\I
`,....
`,....
`ci
`
`0.112
`.,
`
`(")
`
`en
`
`LO
`,....
`(")
`C)
`
`0.135
`
`r
`
`\..
`
`37
`
`r-
`en
`
`,....
`LO
`ci
`
`\..
`
`r
`
`'-
`0.15
`
`r
`
`\...
`
`'--
`
`$
`
`0
`C)
`
`,....
`en
`
`co
`,....
`ci
`
`(")
`
`en
`
`''
`-.::r-
`ci
`
`-.::r-
`CJ)
`
`\..
`
`r
`
`'--
`
`r
`
`a0.048a
`
`~
`
`C)
`
`LO
`en
`
`'-
`
`r
`
`~
`
`.,
`
`~
`
`'-
`0.24
`-.::r-
`C\I
`C)
`
`~
`
`.,
`
`FIG.7B
`en
`......... .
`-
`(!)
`LL
`
`TTI-1030, Page 9
`
`co en
`
`0.5
`
`~
`
`~ \...
`l
`
`32
`
`0
`
`C\I
`en
`
`'-
`
`~
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 9 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 9 0f 17
`
`US 6,442,658 B1
`
`r
`
`'-
`
`C")
`
`en
`
`V
`8
`0
`
`~
`
`005433
`
`"
`
`,-....
`en
`
`V
`en
`
`S4
`
`S7
`
`,)
`
`\.
`
`'
`,-....
`~
`0.029
`ci
`
`0067
`
`O>
`C\I
`q
`0
`
`r
`
`r
`
`r
`
`\.
`
`"
`
`,J
`
`0.077
`
`C")
`
`en
`
`~
`
`,-....
`,-....
`0
`0
`
`\.
`
`'-
`
`r
`
`<O
`en
`
`SS
`
`.._,.
`en
`
`S4
`
`"
`
`,-....
`en
`
`~
`
`0.008S7
`
`~
`
`co
`8
`0
`
`r
`
`r
`
`lO
`en
`85
`
`~ '-
`
`co
`C")
`0038
`C!
`0
`
`S3'
`
`C")
`
`en
`
`...
`
`r
`
`lO
`en
`
`j
`
`C\I
`C\I
`0
`ci
`
`,-....
`en
`
`C")
`
`en
`
`,J
`
`'-
`
`~
`
`.._,.
`lO
`0
`ci
`
`r
`
`...
`
`.._,.
`en
`
`,J
`
`'-
`
`~
`
`'-
`
`c.o'
`O>
`C!
`0.096
`0
`
`r
`
`<O
`O>
`0
`ci
`
`~
`
`0096
`
`r
`
`r
`
`r
`
`\.
`
`,J
`
`'-
`
`0.064
`~
`0
`0
`
`V
`CJ')
`
`C\I
`en
`
`C")
`
`en
`
`~
`0
`ci
`
`<O
`CJ')
`
`,J
`
`'-
`
`0.056
`<O
`lO
`0
`ci
`
`,,,
`
`a a 84
`~ /4
`
`~ ~ '-
`,-
`0
`
`.,-
`
`\.
`
`~ \.._
`
`008
`
`~
`
`0.288
`
`"
`co
`co
`C\I
`ci
`
`r
`
`'-
`
`\.._
`
`r
`
`C")
`CJ')
`
`,J
`
`a a 0.4- a
`
`,-....
`CJ')
`
`,)
`
`'-
`
`r
`
`,....
`N
`ci
`
`,-
`en
`
`,J
`
`~
`p
`
`a.n
`CJ')
`
`N
`en
`
`,J
`
`~
`
`<O
`, -
`0
`
`'-
`
`r
`
`I
`0.2'
`
`N
`ci
`
`,-
`en
`
`0.6
`
`'-
`
`~
`
`,J
`
`~ .._,.
`
`$3
`
`ci
`
`r
`
`C") en
`
`\.
`
`,J
`
`FIG.7C
`(.)
`......... .
`(!) -
`LL
`
`TTI-1030, Page 10
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 10 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 10 0f 17
`
`US 6,442,658 B1
`
`,...._
`cn
`
`C")
`C\J
`0
`ci
`
`<O cn
`
` LO
`
`I.O cn
`(I)
`
`,...._
`,....
`l\'—
`0
`ci
`0.O
`
`,...._
`|\
`en
`U)
`
`-.::r-en
`
`,-...
`,-...
`R
`0
`{20.
`ci
`0.9
`o
`
`N
`(D
`
`C\J
`
`cn
`
`V
`0')
`
`-.::r-
`cn
`
`,_
`,....
`n
`0
`on
`ci
`03
`o'
`
`(D
`(D
`<O cn
`
`.
`
`_
`
`0
`I'-.
`(!) -LL
`
`TTI-1030, Page 11
`
`Q
`go
`o,O
`
`%
`
`C\J en
`
`00
`C\J
`T""
`ci
`
`co
`~“—‘.
`0
`
`1—
`(D
`
`T"" cn
`
`N(
`
`'0
`O.O
`
`v
`CO
`
`....,.
`en
`
`0'
`
`CO
`V.O
`
`CO
`(D
`
`C") cn
`
`on
`O
`
`V(
`
`I)
`
`00
`ci
`
`....,.
`cn
`
`N
`w
`
`,...._
`cn
`
`;'};
`,....
`ci
`
`E
`1—
`o
`
`.—
`w
`
`,....
`cn
`
`g
`8
`9°
`0
`
`U7
`U)
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 11 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 11 0f 17
`
`US 6,442,658 B1
`
`LO en
`
`LO en
`
`C") en
`
`S5
`
`0.054
`
`-33
`
`0090
`
`0.102
`
`LO en
`
`3
`
`,.._
`,.._
`0
`ci
`
`0.077
`
`C") en
`
`0.128
`
`,.._
`en
`
`(0 en
`
`~ ..-
`ci
`
`a
`
`'V en
`
`0.16
`(0
`..-
`ci
`
`(\,I en
`
`016
`
`52-S4
`
`LO en
`
`a:,
`a:,
`(\J
`ci
`
`0.288
`
`53$5
`
`C") en
`
`0.48
`
`31
`
`0.3
`
`$50.18-
`
`LO en
`
`a:,
`..-
`ci
`S7
`,.._
`en
`
`08
`
`0.2
`
`85
`
`LO en
`
`FIG.7E
`.
`(!) -LL
`
`TTI-1030, Page 12
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 12 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 12 0f 17
`
`US 6,442,658 B1
`
`r
`
`(0
`
`en
`
`'"
`;-1;
`0
`C)
`
`C\I
`en
`
`~
`a
`
`~
`
`.....
`en
`
`'-
`
`r
`
`'"
`
`~
`
`~
`
`,J
`
`(0
`
`en
`
`~
`
`'-
`I.O
`~
`a
`
`C\I
`Cf)
`
`r
`
`'-
`
`,J
`
`,J
`
`'-
`
`C')
`(J)
`
`0
`.....
`C")
`0
`
`r
`
`......
`(J)
`
`~
`
`'"
`
`.......
`~
`0
`
`C")
`
`en
`
`'-
`
`,J
`
`~
`0
`C)
`
`-.::r-
`en
`
`C\I
`(J)
`
`,J
`
`8 r
`0343.82SS
`
`C")
`
`.._,.
`0
`d
`
`C")
`
`QWB
`~
`C)
`
`0269 aOlw7.
`
`I.O
`en
`
`r
`
`m
`(0
`C\I
`0
`
`r
`
`\..
`
`.....
`
`(J)
`
`0am
`
`'-
`
`1/
`
`~
`C")
`C)
`
`r
`
`0.56
`
`,J
`
`C")
`(J)
`
`'
`
`(0
`Lt)
`0
`
`.._,.
`(J)
`
`'-
`
`r
`
`'-
`
`o'
`m
`0
`0
`
`
`
`0.70.0900.0451
`
`'-
`
`r
`
`'-
`
`r
`
`......
`0
`
`C")
`C)
`
`86
`
`(0
`Cl)
`
`'-
`
`,J
`
`0mm
`(0
`co
`0
`0
`
`-..,
`
`~
`
`,J
`
`027..
`
`,-
`(J)
`
`(0
`~
`
`C\I
`0
`
`I.O
`en
`
`'
`......
`C\I
`0
`
`......
`(J)
`
`03
`
`,J
`
`FIG.7F
`LL
`I'--
`.
`C, -LL
`
`TTI-1030, Page 13
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 2 7, 2002
`
`Sheet 13 of 17
`
`US 6,442,658 Bl
`
`Aug. 27, 2002
`
`Sheet 13 0f 17
`
`US 6,442,658 B1
`
`S3
`
`,_
`co
`0.0
`
`C")
`Cl)
`
`,....
`00
`0
`ci
`
`-.::r-
`Cl)
`
`r-
`Cl)
`
`C") en
`
`(0
`Cl)
`
`-.::r(cid:173)
`C/)
`
`(\,I en
`
`C")
`Cl)
`
`~
`'V
`ci
`
`T""
`Cl)
`
`r-
`en
`
`FIG.7G
`
`0,
`ci
`
`r-
`Cl)
`
`CJ
`........ .
`-LL
`CJ
`
`TTI-1030, Page 14
`
`

`

`U.S. Patent
`
`Aug. 2 7, 2002
`
`Sheet 14 of 17
`
`US 6,442,658 Bl
`
`805
`
`810
`
`BEGIN EXECUTION OF
`MULTIMEDIA WORK
`
`LOAD RESOURCES
`FOR
`INITIAL SEGMENT
`
`BEGIN EXECUTION
`OF
`CURRENT SEGMENT
`
`815
`
`825
`
`IDENTIFY NEXT HIGHEST
`PRIORITY SEGMENT
`ON LIST
`
`YE
`
`NO
`
`840
`
`LOAD RESOURCES
`FOR SEGMENT
`
`FIG. BA
`
`

`

`U.S. Patent
`
`Aug. 2 7, 2002
`
`Sheet 15 of 17
`
`US 6,442,658 Bl
`
`YES
`
`NO
`
`YES
`
`NO
`
`855
`
`LOAD RESOURCES
`FOR SEGMENT
`
`NO
`
`875
`
`PURGE LOWER
`PRIORITY
`RESOURCES
`
`@-YES
`
`NO
`
`865--..__
`
`AWAIT SELECTION
`OF NEXT SEGMENT
`
`@--YES
`
`FIG. 88
`
`

`

`FIG. 9
`
`(
`
`S1
`
`)
`
`•( S2
`
`)
`
`•( S6
`
`)
`
`{
`
`S7
`
`)
`
`FIG. 10A
`
`FIG. 108
`
`FIG. 10C
`
`FIG. 10D
`
`101Cf
`
`l:\..~~~~~""l
`
`1oso--i
`
`RES.
`FOR
`S6
`
`RES.
`FOR
`S3
`
`1050
`
`1060
`
`10207
`
`1020
`
`l
`
`1030
`
`l
`
`RES.
`FOR
`S3
`
`RES.
`FOR
`S2
`
`1070
`
`1060
`
`1030~
`
`RES.
`FOR
`S7
`
`RES.
`FOR
`S2
`
`RES.
`FOR
`SS
`
`RES.
`FOR
`S2
`
`RES.
`FOR
`S4
`
`I
`
`~RES.~
`1030
`FgR~
`
`1030-i
`
`1040
`
`l
`
`RES. I 10407
`
`FOR
`S4
`
`RES. I 1040~
`
`FOR
`S4
`
`1000
`
`1000
`
`1000
`
`~1000
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`> = ~
`
`N
`~-..J
`N
`0
`0
`N
`
`~
`
`'J'J.
`
`=-
`~ ....
`'"""' O'I
`0 ....,
`'"""'
`-..J
`
`e
`rJ"J.
`O'I
`~
`,I;;..
`N
`O'I
`(It
`~
`~
`i,-
`
`

`

`1100 Ia8S9‘ZW‘9sn
`
`1110 I n
`1115
`
`\ 7\ 13\19 \25 \
`
`2(\
`
`G \
`
`54
`
`56 \
`
`56
`\
`
`FIG. 11
`
`1120
`
`39
`
`\
`
`01
`
`\ 55 \
`
`\
`
`1100
`
`
`
`mama'S'n
`
`
`
`zooz‘Lzfinv
`
`LIJ0LI199118
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`> = ~
`
`N
`~-..J
`N
`0
`0
`N
`
`'JJ. =-~
`~ ....
`'"""'
`-..J
`0 ....,
`'"""'
`-..J
`
`e
`rJ'J.
`O'I
`~
`,I;;..
`N
`O'I
`(It
`~
`~
`i,-
`
`TTI-1030, Page 18
`
`

`

`US 6,442,658 Bl
`
`1
`METHOD AND APPARATUS FOR
`IMPROVING PIAYBACK OF INTERACTIVE
`MULTIMEDIA WORKS
`
`This application is a continuation of Ser. No. 08/792,484,
`filed Jan. 31, 1997, now U.S. Pat. No. 6,128,712.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to the field of multimedia
`works, and more specifically to a method and apparatus for
`improving delivery and playback of interactive multimedia
`works.
`2. Background Art
`Multimedia works are works containing more than one
`"media" such as text, sound, video, still and animated
`graphics, etc. Multimedia works may be delivered to a
`viewer (user) in a variety of forms, including live
`presentations, television broadcasts, computer programs,
`and Internet web pages. The present invention involves
`multimedia works that are presented to a user by a delivery
`device such as a computer, a television, or a similar appli-
`ance.
`"Interactive" multimedia works are multimedia works in
`which the sequence in which the work is presented is
`determined by user actions. Examples of interactive multi(cid:173)
`media works include computer games, computer based
`information resource applications (for example a CD-ROM
`based travel guide or multimedia encyclopedia), websites on
`the Internet, computer learning programs (for example for(cid:173)
`eign language programs or college entrance examination
`study programs), annotated books (for example multimedia
`versions of classic literary, historical and religious works),
`interactive television programs, and other works that
`respond to user input.
`The content of an interactive multimedia work can be
`thought of as a series of individual segments, each having a
`beginning point and an end point. The individual segments
`are linked together sequentially in an order determined by
`the user. Once started, a segment normally executes from its
`beginning to its end. At the end of a segment a succeeding
`segment is selected, according to user input, from among a
`generally finite number of alternatives. The identity and
`number of segments available at each segment end point are
`set by the author of the multimedia work.
`Each segment includes one or more media elements. For
`example, a segment may include an introductory graphic
`animation sequence with an accompanying audio track,
`followed by a video clip, followed by a screen of text. To
`present ( or "play") a segment, the playback device being
`used must have available the appropriate resources in the
`form of the data to be presented and an appropriate playback
`system for that form of data. For example, if the playback
`device is a computer, to play a video clip contained in of a
`segment of a multimedia work, the computer must have
`available in its internal memory (for example RAM
`memory) the video data for the video clip as well as the
`appropriate application program needed to playback the
`video data. For example, a segment of a multimedia work
`may contain a video clip for which the video data is stored
`in MPEG file format on a CD-ROM disk. In order for the
`computer to display the video dip, the computer's processor
`must have access to an MPEG video player (software that
`allows the display of MPEG video data) as well as to the
`MPEG video data itself.
`If a playback device used for presenting a multimedia
`work has unlimited internal memory, all data and application
`
`5
`
`20
`
`2
`code needed to present a multimedia work can be loaded into
`the playback device's memory at one time. The playback
`device always has all resources available for every segment
`of the multimedia work. A transition from one segment to
`the next selected segment can therefore be made nearly
`instantaneously.
`In general, however, a playback device has only a limited
`amount of internal memory available. Because the size of
`multimedia works are commonly much larger than a play-
`10 back device's available internal memory, only a portion of
`the data and application code of a multimedia work can be
`stored in the playback device's internal memory at one time.
`The remainder of the data and application code needed to
`playback the multimedia work must be stored in external
`15 memory devices (stores) such a hard drive, a CD-ROM, or
`a network server. Often, a combination of such stores are
`used.
`In order to proceed without delay from one segment to the
`succeeding segment, the resources required for the succeed(cid:173)
`ing segment must be available to the playback device's
`processor, preferably in quickly accessible internal memory,
`at the end of the currently playing segment. If the resources
`required for the succeeding segment are not available at such
`time, execution of the succeeding segment is delayed while
`25 the resources are located and retrieved. If the resources are
`stored on a CD-ROM drive or a server accessed over a
`communications network, retrieval of the required resources
`can take a significant amount of time, causing an excessive
`and undesirable delay in the execution of the succeeding
`30 segment.
`If the identity of the succeeding segment were known
`ahead of time, the resources required for the succeeding
`segment could be pre-loaded into the playback device's
`internal memory while the preceding segment is being
`executed, assuring that they are available when needed.
`However, for an interactive multimedia title, for each
`segment, there are a number of possible succeeding seg(cid:173)
`ments. The identity of the actual succeeding segment is not
`known until the end of the currently executing segment is
`reached, which is the same time at which the resources
`required for the succeeding segment are needed.
`One possible solution is to pre-load resources for all
`possible succeeding segments while a segment is being
`45 executed. However, doing so is often not possible. First, the
`available internal memory of a playback device is often not
`sufficient to store the resources required for all possible
`succeeding segments. Second, even if the size of the avail(cid:173)
`able memory is sufficient, the time required to retrieve all
`50 required resources for all possible succeeding segments may
`exceed the execution time of the currently executing seg(cid:173)
`ment. Accordingly, it is often impractical to pre-load the
`resources for all possible succeeding segments.
`If it were possible to guess correctly which of the possible
`55 succeeding segments will be selected for execution after a
`currently executing segment 100% of the time, then the
`resources only for that succeeding segment would have to be
`pre-loaded. However, it is in general not possible to predict
`with 100% certainty which succeeding segment will be
`60 selected by user input.
`In the prior art, attempts have been made to improve the
`performance of interactive multimedia titles by attempting
`to identify, for each segment, the most likely succeeding
`segment of the possible succeeding segments. Such identi-
`65 fication may, for example, be done by the author of an
`interactive multimedia work at the time the multimedia work
`is being created based on the author's best guess of what the
`
`35
`
`40
`
`

`

`US 6,442,658 Bl
`
`3
`most likely user selection will be. The resources for the
`segment identified as the most likely succeeding segment are
`then pre-loaded while the preceding segment is being
`executed.
`If a user were to always select the segment that the author 5
`has designated as the segment to be pre-loaded, then a
`multimedia playback system utilizing the prior art method of
`pre-loading the designated most likely succeeding segment
`could provide an increase in performance over a system that
`provides no pre-loading. However, it is unlikely that a user 10
`will always choose the designated segment. In fact, if a user
`always did so, there would be no need for any alternative
`segments. In cases where the user selects a segment other
`than the pre-loaded segment, the prior art provides no benefit
`at all: at the end of the preceding segment, execution of the
`chosen succeeding segment is delayed while the resources 15
`needed for the segment are located and retrieved. The result
`is highly inconsistent performance: performance is good if a
`user selects the designated succeeding segment, perfor(cid:173)
`mance is poor if the user selects any of the other available
`segments.
`There remains a need for a multimedia playback system
`that provides improved performance regardless of which
`succeeding segment is selected by user action.
`
`4
`In one embodiment of the invention, in addition to deliv(cid:173)
`ering resources in the order of a relative priority ranking, the
`resources are also stored according to the relative priority
`ranking, thereby reducing the average seek time needed to
`find and retrieve resources and further improving playback
`performance.
`In one embodiment of the invention, for each segment of
`a multimedia work, a probability factor is determined for
`each other segment of the multimedia work. This probability
`factor represents an estimate of the probability that a par(cid:173)
`ticular one of the other segments will be executed, not
`necessarily immediately after the segment, but at some point
`after the segment. This embodiment accordingly looks
`ahead not only to the immediately succeeding segment, but
`to one or more subsequent segments as well. In one
`embodiment, a time cost factor is combined with the prob(cid:173)
`ability factor to produce a relative priority ranking, and
`resources are pre-loaded according to this priority ranking.
`In one embodiment of the invention, the time cost factor
`20 for each resource is assigned a fixed value. In another
`embodiment, the time cost factor is recalculated periodically
`to reflect changes in location and status of resources.
`
`25
`
`SUMMARY OF THE INVENTION
`The present invention comprises a system for delivering
`an interactive multimedia work from a storage device, for
`example a hard disk drive, a CD-ROM or DVD disk drive,
`a network server, etc. to a playback device, for example a
`personal computer, in a manner that provides improved
`performance regardless of the playback sequence selected
`by a user.
`In one embodiment of the present invention, for each
`segment of an interactive multimedia work, a probability
`factor is assigned to each possible alternative succeeding 35
`segment. The probability factor assigned to a possible suc(cid:173)
`ceeding segment represents an estimate of the probability
`that the segment will be selected for execution upon the
`completion of the currently executing segment In one
`embodiment, the probability factors are assigned by the 40
`author of the multimedia work. In another embodiment, the
`probability factors are dynamically updated based on obser(cid:173)
`vations of actual use.
`In one embodiment of the invention, in addition to assign(cid:173)
`ing a probability factor to each possible succeeding segment 45
`for a preceding segment, a retrieval and delivery time cost
`factor is also assigned to each possible succeeding segment.
`The retrieval and delivery time cost factor represents an
`estimate of the time required to retrieve and deliver to the
`playback device all of the resources required to execute the
`segment. The size of a retrieval and delivery time cost factor
`for a segment depends on a variety of factors, for example
`the size and storage location of the resources required, the
`speed of the communications channel between the storage
`device and the playback device, the amount of traffic at the 55
`storage device and along the communications channel, and
`other factors that determine the time required for a resource
`to be located, retrieved, and delivered to the playback
`device. In this embodiment, the probability and time cost
`factor for each possible succeeding segment are combined to
`produce a relative priority ranking. Resources for the pos(cid:173)
`sible succeeding segments are pre-loaded according to the
`relative priority ranking. As a result, the latency time
`between the time a segment is selected as a result of user
`input and the time at which execution of the segment begins 65
`is reduced and the performance of a multimedia work
`improved.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram illustrating an example of a
`branch point for an interactive multimedia work.
`FIG. 2 is a schematic diagram illustrating the media
`content of each of segments Sl-S4 of FIG. 1.
`FIG. 3 is a schematic diagram of a computer system that
`30 can be used as a playback device in one embodiment of the
`present invention.
`FIG. 4 is a block diagram illustrating a resource pre(cid:173)
`loading operation for one embodiment of the present inven(cid:173)
`tion.
`FIG. SA is a schematic diagram of the configuration of a
`playback device's internal memory for one embodiment of
`the present invention.
`FIG. SB is a schematic diagram of the configuration of a
`playback device's internal memory of the prior art.
`FIG. 6 is a block diagram illustrating an interactive
`multimedia work.
`FIG. 7Ais a block diagram illustrating a method used to
`derive probability factors for segment Sl of the multimedia
`work of FIG. 6.
`FIG. 7B is a block diagram illustrating a method used to
`derive probability factors for segment S2 of the multimedia
`work of FIG. 6.
`FIG. 7C is a block diagram illustrating a method used to
`derive probability factors for segment S3 of the multimedia
`50 work of FIG. 6.
`FIG. 7D is a block diagram illustrating a method used to
`derive probability factors for segment S4 of the multimedia
`work of FIG. 6.
`FIG. 7E is a block diagram illustrating a method used to
`derive probability factors for segment SS of the multimedia
`work of FIG. 6.
`FIG. 7F is a block diagram illustrating a method used to
`derive probability factors for segment S6 of the multimedia
`60 work of FIG. 6.
`FIG. 7G is a block diagram illustrating a method used to
`derive probability factors for segment S7 of the multimedia
`work of FIG. 6.
`FIG. 8 is a block diagram showing how the pre-loading
`order specified in Table 11 is used during execution of the
`multimedia work of FIG. 6 in one embodiment of the present
`invention.
`
`

`

`US 6,442,658 Bl
`
`5
`FIG. 9 is a schematic diagram illustrating the sequence of
`executing segments of a multimedia work using one
`embodiment of the present invention.
`FIG. l0A is a schematic diagram illustrating the contents
`of a playback device's memory for one embodiment of the 5
`present invention.
`FIG. l0B is a schematic diagram illustrating the contents
`of a playback device's memory for one embodiment of the
`present invention.
`FIG. l0C is a schematic diagram illustrating the contents
`of a playback device's memory for one embodiment of the
`present invention.
`FIG. l0D is a schematic diagram illustrating the contents
`of a playback device's memory for one embodiment of the
`present invention.
`FIG. 11 is a schematic diagram of a disk drive storage
`medium used to store resources of a multimedia work in one
`embodiment of the present invention.
`
`6
`will be repeated. Probability factor P12 represents an esti(cid:173)
`mate of the probability that execution of segment S2 will
`follow execution of segment Sl. Probability factor P13
`represents an estimate of the probability that execution of
`segment S3 will follow execution of segment Sl. Probability
`factor P14 represents an estimate of the probability that
`execution of segment S4 will follow execution of segment
`Sl. In the example of FIG. 1, Pll has a value of 0.1, P12 has
`10 a value of 0.2, P13 has a value of 0.3, and P14 has a value
`of 0.4. Assuming the values of the probability factors are
`accurate estimates of the actual probabilities, the most likely
`segment to follow execution of segment Sl is segment S4,
`which will occur 40% of the time. Segment S2 will follow
`15 segment Sl 20% of the time, segment S3 will follow
`segment Sl 30% of the time, and segment Sl will be
`repeated 10% of the time. Pll, P12, P13 and P14 in this
`example add up to 1.0. In general, if the probability factors
`20 for each transition are accurate estimates of the actual
`probabilities, the sum of the probability factors will equal
`unity. However, if one or more of the probability factors
`differs from the corresponding actual probability, the sum of
`the probability factors at a transition point may differ from
`25 unity to some extent.
`
`DETAILED DESCRIPTION OF IBE
`INVENTION
`
`A method and apparatus for delivery and playback of
`interactive multimedia works is described. In the following
`description, numerous specific details are set forth in order
`to provide a more thorough description of the present
`invention. It will be apparent, however, to one stilled in the
`art, that the present invention may be practiced without these
`specific details. In other instances, well-known features have
`not been described in detail so as not to obscure the 30
`invention.
`Execution, or playback, of interactive multimedia works
`occurs in segments or stages. As the end of each segment is
`reached, the next succeeding segment is selected from a 35
`generally finite number of alternative segments based on
`user input. The segment may be directly selected by a user,
`or user input ( or lack of user input) may indirectly select a
`segment based upon some predetermined, or random, crite(cid:173)
`ria. An interactive multimedia work can thus be viewed as 40
`a series of branch points at which execution of the work
`transitions from one segment to another, with the identity of
`the transitioned-to segment depending in some manner on
`user input. "User input" as used here includes actual input of
`a user, but also includes any other form of input including 45
`input or lack of input from sources internal and external to
`a multimedia playback device. For example, such external
`inputs may include external physical variables such as
`weather, pressure, sound, moisture, temperature, light, etc.
`FIG. 1 is a block diagram illustrating an example of a 50
`branch point for an interactive multimedia work. At branch
`point 100 of FIG. 1, a transition occurs from segment Sl 110
`to a succeeding segment along one of four possible branches
`115, 125, 135 or 145. The particular branch along which the
`transition occurs is dependent upon user or external input. 55
`Branch 115 represents a transition from the end of segment
`Sl back to the beginning of segment Sl, resulting in a repeat
`execution of segment Sl. Branch 125 represents a transition
`from the end of segment Sl to the beginning of segment S2.
`Branch 135 represents a transition from the end of segment 60
`Sl to the beginning of segment S3. Branch 145 represents a
`transition from the end of segment Sl to the beginning of
`segment S4.
`In the example