Non-deterministic method and system for the optimization of a targeted content delivery

• US 20030130887A1
• Filed: 10/03/2001
• Published: 07/10/2003
• Est. Priority Date: 10/03/2001
• Status: Abandoned Application

• Current Assignee: OpenTV, Inc. (Kudelski SA)
• Original Assignee: OpenTV, Inc. (Kudelski SA)
• Inventors: Nathaniel, Thurston
• Application Number:
  US09/969,911
• Publication Number:
  US 20030130887A1
• Time in Patent Office: Days
• US Class Current: 705/14
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 30/0277 Online advertisement
• CPC Class Codes: H04L 67/303 Terminal profiles
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04N 21/25808 Management of client data terminal profiles in network data switching protocols H04L67/303
• CPC Class Codes: H04N 21/25891 being end-user preferences retrieval of video data in a video database based on user preferences G06F16/739; arrangements for recognizing users' preferences H04H60/46; user profiles in network data switching protocols H04L67/306; processing of user preferences or user profiles in wireless networks H04W8/18
• CPC Class Codes: H04N 21/262 Content or additional data distribution scheduling, e.g. sending additional data at off-peak times, updating software modules, calculating the carousel transmission frequency, delaying a video stream transmission, generating play-lists scheduling strategies for dispatcher in multiprogramming arrangements G06F9/4881; arrangements for scheduling broadcast services or broadcast-related services H04H60/06; flow control in packet networks H04L47/10; establishing a time schedule or organising the servicing of application requests H04L67/62
• 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/812 involving advertisement data advertising per se G06Q30/02
• CPC Class Codes: H04N 7/165 Centralised control of user terminal subsequent to an upstream request signal H04N7/17345; Registering at central by two-way working H04N7/17309

Abstract

A method for scheduling delivery of items of content to a plurality of network devices. The method features generating an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content, and determining a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the priority and the weight for each of the items of content optimizes a delivery schedule for the items of content.

Claims

1. A method for scheduling delivery of items of content to a plurality of network devices, comprising:

generating an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content; and

determining a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the priority and the weight for each of the items of content optimizes a delivery schedule for the items of content.

2. The method of claim 1, wherein the network devices are iTV set-top boxes.

3. The method of claim 1, wherein the network devices are selected from the group consisting of iTV set-top boxes and computers with Internet access.

4. The method of claim 1, wherein, for a given network device, the item of content having the priority with the highest value is delivered before other items of content.

5. The method of claim 4, wherein two of more items of content with the same priority having the highest value are each delivered a certain percentage of available delivery slots, the certain percentage being defined by the weight for each item of content.

6. The method of claim 5, wherein the certain percentage being defined by the weight of each item of content is equal to the weight of that item of content divided by the summation of the weights of all items of content for the given network device.

7. The method of claim 1, further comprising using a number of deliveries requested for each item of content to optimize the delivery schedule.

8. The method of claim 7, further comprising using a number of deliveries expected for each item of content to optimize the delivery schedule.

9. The method of claim 8, further comprising using a number of impressions available for each item of content to optimize the delivery schedule.

10. The method of claim 9, wherein the number of deliveries expected for each item of content is expressed as a function of the weights for the items of content and the number of impressions available.

11. The method of claim 10, wherein the function for the deliveries expected for each of the items of content is:

DelEx(Ai)=Q×

DelRq(Ai);

where DelEx(A_i) is the deliveries expected for item of content A_i as a function of the weights for the items of content, DelRq(A_i) is a constant equaling the deliveries requested for item of content A_i, and where

12. The method of claim 11, wherein Q is a constant for the items of content evaluated.

13. The method of claim 12, wherein determining the weight for each item of content includes using Newton'"'"'s Method to iteratively solve the function for the deliveries expected for the weight, wherein new weights from an iteration of Newton'"'"'s Method are accepted as the weights if an energy function decreases with the new weights.

14. The method of claim 13, wherein the energy function is:

15. The method of claim 14, wherein determining the priority for each of the items of content includes:

evaluating subsets of each group of items of content with the same priority; and

resetting the priority for a particular subset of the group of items of content to a higher priority if the particular subset will be underdelivered at the same priority.

16. The method of claim 1, wherein the items of content comprise advertisements to be displayed on a display device operated by each network device.

17. The method of claim 1, wherein the specifications specify the number of times an item of content is to be delivered to the network devices.

18. The method of claim 1, wherein the specifications specify a time period during which a given number of deliveries of an item of content is to be delivered to the network devices.

19. An apparatus for scheduling delivery of items of content to a plurality of network devices, comprising:

means for generating an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content; and

means for determining a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the priority and the weight for each of the items of content optimizes a delivery schedule for the items of content.

20. A computer system for scheduling delivery of items of content to a plurality of network devices, comprising:

a memory for storing a program; and

a processor operative with the program to;

generate an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content; and

determine a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the priority and the weight for each of the items of content optimizes a delivery schedule for the items of content.

21. A method for scheduling delivery of items of content to a plurality of network devices, comprising:

generating an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content, wherein the specification for each item of content includes a number of deliveries requested over all of the network devices; and

controlling a number of deliveries made for each item of content using a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein the number of deliveries requested for each item of content and a number of deliveries available for a set of network devices is used to adjust the priority and weight for at least one subset of the items of content.

22. The method of claim 21, wherein the network devices are iTV set-top boxes.

23. The method of claim 21, wherein the network devices are selected from the group consisting of iTV set-top boxes and computers with Internet access.

24. The method of claim 21, wherein, for a given network device, the item of content having the priority with the highest value is delivered before other items of content.

25. The method of claim 24, wherein two of more items of content with the same priority having the highest value are each delivered a certain percentage of available delivery slots, the certain percentage being defined by the weight for each item of content.

26. The method of claim 25, wherein the certain percentage being defined by the weight of each item of content is defined to be the weight of one particular item of content divided by the summation of the weights of all items of content in the list for the given network device.

27. A method for scheduling delivery of items of content to a plurality of network devices, comprising:

generating an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content; and

determining a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the weight for each of the items of content includes;

(a) performing an iteration of Newton'"'"'s Method to compute a new weight for each item of content using an equation for the deliveries expected for each of the items of content, wherein the weight for each item of content is set to be the new weight if an energy function decreases with the new weights, and (b) resetting the weight for each item of content to be equal to the weight divided by a delivery ratio for the item of content.

28. The method of claim 27, wherein the equation for the deliveries expected for each of the items of content is:

DelEx(Ai)=Q×

DelRq(Ai);

where DelEx(A_i) is the deliveries expected for item of content A_i as a function of the weights for the items of content, DelRq(A_i) is a constant equaling the deliveries requested for item of content A_i, and where

29. The method of claim 28, wherein the energy function is:

30. The method of claim 29, wherein determining the priority for each of the items of content includes:

evaluating subsets of each group of items of content with the same priority; and

resetting the priority for a subset of the group of items of content to a higher priority if the subset will be underdelivered at the same priority.

31. The method of claim 30, wherein the subset is the items of content with weight(A_i)>

w, where w is every weight in the group of items of content.

32. The method of claim 30, wherein the subset is the items of content with DelRat(A_i)<

d, where d is every delivery ratio in the group of items of content.

33. The method of claim 30, wherein determining the priority for each of the items of content further includes adjusting priority relationships for other groups of items of content having different priorities.

34. A computer system for scheduling delivery of items of content to a plurality of network devices, comprising:

a memory for storing a program; and

a processor operative with the program to;

generate an individual list of one or more items of content to be delivered to each network device based on profiles of the network devices and specifications for the items of content; and

determine a priority and a weight for each of the items of content, the priority and weight for each item of content determining the probability of delivery at each network device in relation to other items of content, wherein determining the weight for each of the items of content includes;

(a) performing an iteration of Newton'"'"'s Method to compute a new weight for each item of content using an equation for the deliveries expected for each of the items of content, wherein the weight for each item of content is set to be the new weight if an energy function decreases with the new weights, and (b) resetting the weight for each item of content to be equal to the weight divided by a delivery ratio for the item of content.