Method and apparatus for improving playback of interactive multimedia works

• US 6,128,712 A
• Filed: 01/31/1997
• Issued: 10/03/2000
• Est. Priority Date: 01/31/1997
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Macromedia, Inc. (Adobe Inc.)
• Inventors: Chesley, Harry R., Day, Ken, Hunt, V. Bruce
• Primary Examiner(s): Nguyen, Hiep T
• Application Number:
  US08/792,484
• Time in Patent Office: 1,341 Days
• Field of Search: 711/137, 711/151, 711/158, 711/4, 711/114, 711/117, 711/111, 711/159, 711/204, 710/6, 710/29, 710/40, 710/41, 369/14, 369/15, 369/30, 369/34
• US Class Current: 711/158
• CPC Class Codes: G11B 2220/213 Read-only discs
• CPC Class Codes: G11B 2220/2545 CDs
• CPC Class Codes: G11B 2220/2562 DVDs [digital versatile discs]; Digital video discs; MMCDs; HDCDs
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: H04N 21/26216 involving the channel capacity, e.g. network bandwidth admission control, resource allocation in open networks H04L12/5692; flow control in packet networks H04L47/10; establishing a schedule or organising the servicing of application requests taking into account QoS H04L67/61
• CPC Class Codes: H04N 21/26233 involving content or additional data duration or size, e.g. length of a movie, size of an executable file
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 21/8541 involving branching, e.g. to different story endings
• CPC Class Codes: H04N 7/163 by receiver means only

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-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 multimedia 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.

Claims

1. A method for presenting a multimedia work on a playback device comprising the steps of:

loading resources required for presenting a first segment of said multimedia work on said playback device into memory accessible by said playback device;

presenting said first segment of said multimedia work on said playback device;

identifying possible alternative succeeding segments that may be selected for presentation subsequent to said first segment;

assigning a priority ranking to said possible alternative succeeding segments of said first segment wherein said step of assigning a priority ranking to possible succeeding segments of said first segment comprises the steps of;

assigning a probability factor that represents an estimate of the likelihood each of said possible succeeding segments will be selected;

assigning a cost factor that represents an estimate of the time used to present each of said possible succeeding segments to said playback device;

deriving said priority ranking from said probability factors and said cost factors;

loading resources required by said possible succeeding alternative segments into memory accessible by said playback device according to said priority ranking.

2. The method of claim 1 wherein said step of loading resources required by said possible succeeding segments into memory accessible by said playback device according to said priority ranking comprises the steps of:

identifying a possible succeeding segment having a first highest priority ranking;

identifying any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking on said playback device that have not been previously loaded into said memory accessible by said playback device;

loading said any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking into said memory accessible by said playback device.

3. The method of claim 1 wherein said resources for said possible succeeding segments are stored on a storage device connected to said playback device by a communications means.

4. The method of claim 3 wherein said storage device comprises a rotating storage medium.

5. The method of claim 4 wherein said rotating storage medium comprises a rewritable rotating storage medium.

6. The method of claim 4 wherein said rotating storage medium comprises a read-only storage medium.

7. The method of claim 4 wherein said rotating storage medium comprises a CD-ROM.

8. The method of claim 4 wherein said rotating storage medium comprises a DVD disk.

9. The method of claim 3 wherein said storage device comprises a fixed storage medium.

10. The method of claim 9 wherein said fixed storage medium comprises random access memory.

11. The method of claim 3 wherein said storage device comprises a magnetic tape storage device.

12. The method of claim 3 wherein said communications means comprises a data communications network.

13. The method of claim 3 wherein said communications means comprises a computer bus.

14. The method of claim 2 wherein said step of loading said any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking into said memory accessible by said playback device comprises the step of:

determining whether said memory accessible by said playback device has sufficient memory space available for loading said remaining resources;

if said playback device does not have said sufficient memory space available, determining whether any resources for any segments of said multimedia work having a lower priority ranking than said possible succeeding segment having said first highest priority ranking are loaded into said memory;

if a resource for a segment of said multimedia work having a lower priority ranking than said possible succeeding segment having said first highest priority ranking is loaded into said memory, purging said resource to make room for a portion of said remaining resources.

15. The method of claim 1 wherein said probability factor comprises an estimate of a probability that said possible succeeding segment will be presented subsequent to said first segment.

16. The method of claim 15 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented immediately subsequent to said first segment.

17. The method of claim 15 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented within a plurality of segments subsequent to said first segment.

18. The method of claim 1 wherein said cost factor comprises an estimate of a relative time cost required to obtain resources required by said each possible succeeding segment.

19. The method of claim 1 wherein said cost factor comprises an estimate of a relative storage cost required to obtain resources required by said each possible succeeding segment.

20. The method of claim 1 wherein said cost factor comprises an estimate of a relative bandwidth cost required to obtain resources required by said each possible succeeding segment.

21. The method of claim 1 wherein said probability factors are derived from observations of presentation sequences of segments of said multimedia work.

22. The method of claim 1 wherein said probability factors are derived dynamically and updated during execution of said multimedia work.

23. The method of claim 1 wherein said probability factors depend on a characteristic of a user.

24. The method of claim 1 wherein said probability factors depend on an external parameter.

25. The method of claim 1 wherein said step of assigning a priority ranking to said possible succeeding segments of said first segment comprises the steps of:

identifying a parameter of a user of said playback device;

assigning said priority ranking based upon said parameter of said user.

26. The method of claim 3 wherein said step of loading resources required by said possible succeeding segments into memory accessible by said playback device according to said priority ranking is controlled by said storage device.

27. The method of claim 1 wherein said resources comprise application program data.

28. The method of claim 1 wherein said resources comprise media data.

29. A method for storing resources of a multimedia work on a storage device comprising the steps of:

identifying possible alternative succeeding segments that may be selected for presentation during playback of said multimedia work subsequent to presenting a first segment of said multimedia work;

assigning a first priority ranking to said possible alternative succeeding segments of said first segment wherein said step of assigning a first priority ranking to possible succeeding segments of said first segment comprises the steps of;

assigning to each of said possible succeeding segments a probability factor that represents an estimate of the likelihood each of said possible succeeding segments will be selected;

assigning a cost factor that represents an estimate of the time used to present each of said possible succeeding segments for playback;

deriving said first priority ranking from said probability factors and said cost factors;

storing resources required by said possible alternative succeeding segments on said storage device according to said first priority ranking.

30. The method of claim 29 wherein said storage device comprises rotating storage medium.

31. The method of claim 30 wherein said rotating storage medium comprises a rewritable rotating storage medium.

32. The method of claim 30 wherein said rotating storage medium comprises a read-only storage medium.

33. The method of claim 30 wherein said rotating storage medium comprises a CD-ROM.

34. The method of claim 30 wherein said rotating storage medium comprises a DVD disk.

35. The method of claim 30 wherein said storage device comprises a fixed storage medium.

36. The method of claim 35 wherein said fixed storage medium comprises random access memory.

37. The method of claim 30 wherein said storage device comprises a magnetic tape storage device.

38. The method of claim 30 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented subsequent to said first segment.

39. The method of claim 30 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented immediately subsequent to said first segment.

40. The method of claim 30 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented within a plurality of segments subsequent to said first segment.

41. The method of claim 30 wherein said time cost factor comprises an estimate of a relative time cost required to obtain resources required by said each possible succeeding segment.

42. The method of claim 30 wherein said cost factor comprises an estimate of a relative storage cost required to obtain resources required by said each possible succeeding segment.

43. The method of claim 30 wherein said cost factor comprises an estimate of a relative bandwidth cost required to obtain resources required by said each possible succeeding segment.

44. The method of claim 29 wherein said resources comprise application program data.

45. The method of claim 29 wherein said resources comprise media data.

46. The method of claim 29 further comprising the steps of:

identifying possible succeeding segments that may be selected for presenting during playback of said multimedia work subsequent to presenting a second segment of said multimedia work;

assigning a second priority ranking to said possible succeeding segments of said second segment;

storing resources required by said possible succeeding segments of said second segment on said storage device according to said second priority ranking.

47. A method for storing resources of a multimedia work on a storage device comprising the steps of:

identifying possible alternative succeeding segments that may be selected for presentation during playback of said multimedia work subsequent to presenting a first segment of said multimedia work;

assigning a first priority ranking to said possible alternative succeeding segments of said first segment wherein said step of assigning a priority ranking to possible succeeding segments of said first segment comprises the steps of;

assigning to each of said possible succeeding segments a probability factor that represents an estimate of the likelihood each of said possible segments will be selected;

assigning a cost factor that represents an estimate of the time used to present each of said possible succeeding segments for playback;

deriving said first priority ranking from said probability factors and said cost factors.

48. The method of claim 47 wherein said storage media comprises a CD-ROM.

49. The method of claim 47 wherein said storage media comprises a DVD disk.

50. The method of claim 47 wherein said storage device comprises a magnetic tape storage device.

51. The method of claim 47 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented subsequent to said first segment.

52. The method of claim 47 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented immediately subsequent to said first segment.

53. The method of claim 47 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented within a plurality of segments subsequent to said first segment.

54. The method of claim 47 wherein said cost factor comprises an estimate of a relative time cost required to obtain resources required by said each possible succeeding segment.

55. The method of claim 47 wherein said cost factor comprises an estimate of a relative storage cost required to obtain resources required by said each possible succeeding segment.

56. The method of claim 47 wherein said cost factor comprises an estimate of a relative bandwidth cost required to obtain resources required by said each possible succeeding segment.

57. The method of claim 47 wherein said resources comprise application program data.

58. The method of claim 47 wherein said resources comprise media data.

59. The method of claim 47 further comprising second copies of said resources stored according to a second priority ranking obtained by using the method steps of:

identifying possible succeeding segments that may be selected for presenting during playback of said multimedia work subsequent to presenting a second segment of said multimedia work;

assigning a second priority ranking to said possible succeeding segments of said second segment.

60. A program storage device readable by a machine tangibly embodying a program of instructions executable by the machine to perform method steps for presenting a multimedia work on a playback device, said method comprising the steps of:

loading resources required for presenting a first segment of said multimedia work on said playback device into memory accessible by said playback device;

presenting said segment of said multimedia work on said playback device;

identifying possible alternative succeeding segments that may be selected for presentation subsequent to said first segment;

assigning a priority ranking to said possible alternative succeeding segments of said first segment wherein said step of assigning a priority ranking to possible succeeding segments of said first segment comprises the steps of;

assigning to each of said possible succeeding segments a probability factor that represents an estimate of the likelihood each of said possible succeeding segments will be selected;

assigning a cost factor that represents an estimate of the time used to present each of said possible succeeding segments to said playback device;

deriving said priority ranking from said probability factors and said cost factors;

loading resources required by said possible alternative succeeding segments into memory accessible by said playback device according to said priority ranking.

61. The program storage device of claim 60 wherein said step of loading resources required by said possible succeeding segments into memory accessible by said playback device according to said priority ranking comprises the steps of:

identifying a possible succeeding segment having a first highest priority ranking;

identifying any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking on said playback device that have not been previously loaded into said memory accessible by said playback device;

loading said any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking into said memory accessible by said playback device.

62. The program storage device claim 60 wherein said resources for said possible succeeding segments are stored on a resource storage device connected to said playback device by a communications means.

63. The program storage device of claim 62 wherein said resource storage device comprises a rotating storage medium.

64. The program storage device of claim 63 wherein said rotating storage medium comprises a rewritable rotating storage medium.

65. The program storage device of claim 63 wherein said rotating storage medium comprises a read-only storage medium.

66. The program storage device of claim 63 wherein said rotating storage medium comprises a CD-ROM.

67. The program storage device of claim 63 wherein said rotating storage medium comprises a DVD disk.

68. The program storage device of claim 62 wherein said resource storage device comprises a fixed storage medium.

69. The program storage device of claim 68 wherein said fixed storage medium comprises random access memory .

70. The program storage device of claim 62 wherein said resource storage device comprises a magnetic tape storage device.

71. The program storage device of claim 62 wherein said communications means comprises a data communications network.

72. The program storage device of claim 62 wherein said communications means comprises a computer bus.

73. The program storage device of claim 61 wherein said step of loading said any remaining resources required for presenting said possible succeeding segment having said first highest priority ranking into said memory accessible by said playback device comprises the step of:

determining whether said memory accessible by said playback device has sufficient memory space available for loading said remaining resources;

if said playback device does not have said sufficient memory space available, determining whether any resources for any segments of said multimedia work having a lower priority ranking than said possible succeeding segment having said first highest priority ranking are loaded into said memory;

if a resource for a segment of said multimedia work having a lower priority ranking than said possible succeeding segment having said first highest priority ranking is loaded into said memory, purging said resource to make room for a portion of said remaining resources.

74. The program storage device of claim 60 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented subsequent to said first segment.

75. The program storage device of claim 74 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented immediately subsequent to said first segment.

76. The program storage device of claim 74 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented within a plurality of segments subsequent to said first segment.

77. The program storage device of claim 60 wherein said cost factor comprises an estimate of a relative time cost required to obtain resources required by said each possible succeeding segment.

78. The program storage device of claim 60 wherein said cost factor comprises an estimate of a relative storage cost required to obtain resources required by said each possible succeeding segment.

79. The program storage device of claim 60 wherein said cost factor comprises an estimate of a relative bandwidth cost required to obtain resources required by said each possible succeeding segment.

80. The program storage device of claim 60 wherein said probability factors are derived from observations of presentation sequences of segments of said multimedia work.

81. The program storage device of claim 60 wherein said probability factors are derived dynamically and updated during execution of said multimedia work.

82. The program storage device of claim 60 wherein said probability factors depend on a characteristic of a user.

83. The program storage device of claim 60 wherein said probability factors depend on an external parameter.

84. The program storage device of claim 60 wherein said step of assigning a priority ranking to said possible succeeding segments of said first segment comprises the steps of:

identifying a parameter of a user of said playback device;

assigning said priority ranking based upon said parameter of said user.

85. The program storage device of claim 62 wherein said step of loading resources required by said possible succeeding segments into memory accessible by said playback device according to said priority ranking is controlled by said storage device.

86. The program storage device of claim 60 wherein said resources comprise application program data.

87. The program storage device of claim 60 wherein said resources comprise media data.

88. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for storing resources of a multimedia work on a resource storage device, said method comprising the steps of:

identifying possible alternative succeeding segments that may be selected for presentation during playback of said multimedia work subsequent to presenting a first segment of said multimedia work;

assigning a first priority ranking to said possible alternative succeeding segments of said first segment wherein said step of assigning a first priority ranking to possible succeeding segments of said first segment comprises the steps of;

assigning to each of said possible succeeding segments a probability factor that represents an estimate of the likelihood each of said possible succeeding segments will be selected;

assigning a cost factor that represents an estimate of the time used to present each of said possible succeeding segments for playback;

deriving said first priority ranking from said probability factor and said cost factor;

storing resources required by said possible alternative succeeding segments on said storage device according to said first priority ranking.

89. The program storage device of claim 88 wherein said resource storage device comprises rotating storage medium.

90. The program storage device of claim 89 wherein said rotating storage medium comprises a rewritable rotating storage medium.

91. The program storage device of claim 89 wherein said rotating storage medium comprises a read-only storage medium.

92. The program storage device of claim 89 wherein said rotating storage medium comprises a CD-ROM.

93. The program storage device of claim 89 wherein said rotating storage medium comprises a DVD disk.

94. The program storage device of claim 88 wherein said resource storage device comprises a fixed storage medium.

95. The program storage device of claim 94 wherein said fixed storage medium comprises random access memory.

96. The program storage device of claim 88 wherein said resource storage device comprises a magnetic tape storage device.

97. The program storage device of claim 88 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented subsequent to said first segment.

98. The program storage device of claim 88 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented immediately subsequent to said first segment.

99. The program storage device of claim 88 wherein said probability factor comprises an estimate of a probability that said each possible succeeding segment will be presented within a plurality of segments subsequent to said first segment.

100. The program storage device of claim 88 wherein said time cost factor comprises an estimate of a relative time cost required to obtain resources required by said each possible succeeding segment.

101. The program storage device of claim 88 wherein said cost factor comprises an estimate of a relative storage cost required to obtain resources required by said each possible succeeding segment.

102. The program storage device of claim 88 wherein said cost factor comprises an estimate of a relative bandwidth cost required to obtain resources required by said each possible succeeding segment.

103. The program storage device of claim 88 wherein said resources comprise application program data.

104. The program storage device of claim 88 wherein said resources comprise media data.

105. The program storage device of claim 88 wherein said method further comprises the steps of:

identifying possible succeeding segments that may be selected for presenting during playback of said multimedia work subsequent to presenting a second segment of said multimedia work;

assigning a second priority ranking to said possible succeeding segments of said second segment;

storing resources required by said possible succeeding segments of said second segment on said resource storage device according to said second priority ranking.