Abstract:
Ads play an important role in enhancing the market reach of the products. Televisions are one of the major targets for advertising to reach mass market. With the advent of the Internet, video on demand mode of delivering content, to a variety of devices such as personal computers and mobile phones, has become a possibility. New ad targeting opportunities arise when the multitude of technologies are combined. One of the aspects of ad targeting, to keep the viewers&#39; attention focused on ads, is to “beat the expectations.” A system and method to help in keeping viewers&#39; attention focused on ads involves randomly selecting an ad to be displayed using a randomly selected ad display model at a randomly selected time interval during the course of watching of content. Further, a viewer&#39;s attention on ads gets enhanced when the randomly selected ads are appropriate from the point of view of the content being watched.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to ad targeting in general, and more particularly, ad targeting when content is being watched. Still more particularly, the present invention is related to a system and method for real-time ad selection and scheduling for targeting purposes so as to enhance viewers&#39; attention on the displayed ads. 
       BACKGROUND OF THE INVENTION 
       [0002]    Ad targeting in general and TV ad targeting in particular involves delivering specific ads to specific audience. Ad customization deals with diverse consumer segments and hundreds of variations of an ad are generated, say based on context-based business rules, to help in targeting. This further helps in making the ads more effective at the same time reducing the ad wear-out. It has been observed that many TV viewers cite having already seen a commercial, possibly several times, as one of the major reasons for their intent to skip the TV commercials. In order to help retain the interests of the users on the ads, it is required to “beat the expectations” of the viewers. This needs to be achieved while a user is viewing content on a television, personal computer, or mobile phone. Note that “user,” “viewer,” and “subscriber” are used interchangeably. Specifically, the ads compete with content in being able to draw the attention of the viewers. Further, the viewers are mentally tuned to watch the content and hence, the ads are treated an unwanted interruptions. On the other hand, the return of investment on ads is related to the attention factor: the fraction of time the user&#39;s attention is on the ads being shown. As a consequence, any solution that addresses the issues related to ad monotonicity, that is, the bombarding of the viewers with the same and most importantly predictable ads, would go a long way in improving the return on investment for the ad sponsors. 
       DESCRIPTION OF RELATED ART 
       [0003]    U.S. Pat. No. 7,228,555 to Schlack; John A. (Southampton, Pa.) for “System and method for delivering targeted advertisements using multiple presentation streams” (issued on Jun. 5, 2007 and assigned to Prime Research Alliance E., Inc. (Tortola, VG)) describes a system and method for delivering channels of presentation streams carrying targeted advertisements in a television service network environment that includes a generator for generating a set of presentation streams for each of programming channels, each of the presentation streams in each set having same programming data but different ads directed to advertiser-specific market segments of different advertisers. 
         [0004]    U.S. Pat. No. 7,203,684 to Carobus; Alexander Paul (Mountain View, Calif.), Roetter; Alex (Palo Alto, Calif.), Davenport; Ben (Mountainview, Calif.) for “Serving content-targeted ADS in e-mail, such as e-mail newsletters” (issued on Apr. 10, 2007 and assigned to Google, Inc (Mountainview, Calif.)) describes an approach for serving content-targeted ads with emails such as email newsletters by including a unique content identifier in the content and using of the same to fetch content-relevant ads from an ad server. 
         [0005]    U.S. Pat. No. 7,185,353 to Schlack; John A. (Southampton, Pa.) for “System and method for delivering statistically scheduled advertisements” (issued on Feb. 27, 2007 and assigned to Prime Research Alliance E., Inc. (Tortolla, VG)) describes a system and method for scheduling advertisements in a television network based on such information as channel change statistical information and avail information. 
         [0006]    U.S. Pat. No. 6,463,585 to Hendricks; John S. (Potomac, Md.), Bonner; Alfred E. (Bethesda, Md.), McCoskey; John S. (Derwood, Md.), Asmussen; Michael L. (Herndon, Va.) for “Targeted advertisement using television delivery systems” (issued on Oct. 8, 2002 and assigned to Discovery Communications, Inc. (Bethesda, Md.)) describes a novel multiple channel architecture that is designed to allow targeted advertising directed to television terminals connected to an operations center or a cable headend by providing additional feeder channels to early alternate advertising that may be better suited for certain viewing audiences. 
         [0007]    U.S. Pat. No. 6,144,944 to Kurtzman, II; Stephen J. (San Jose, Calif.), Nawathe; Sandeep A. (Sunnyvale, Calif.) for “Computer system for efficiently selecting and providing information” (issued on Nov. 7, 2000 and assigned to Imgis, Inc. (Cupertino, Calif.)) describes a system for selecting advertisements in response to a request from a web page server based on such information as demographic information, page sponsor information, and keyword sponsor information. 
         [0008]    “Auctioning Ad Space in Video on Demand (VoD) Assets” by Hood; Bill, Sinha; Nishith, and Barker; Reed (document available in the URL; http://www.experts-iptv.com/database/forums2007/advertizing_methods_vodassets.pdf) describes a competitive selection of advertising for Video on Demand based on real-time and near real-time “ad auctioning” that provides a mechanism for dynamically selecting advertisements that need to be placed in conjunction with a specific viewing of a movie. 
         [0009]    “Event Driven Semantics Based Ad Selection” by Thawani; Amit, Gopalan; Srividya, and Varadarajan; Sridhar (appeared in the Proceedings of the 2004 IEEE International Conference on Multimedia and Expo (ICME &#39;2004), The Grand Hotel, Taipei, Taiwan, Jun. 27-30, 2004) describes a system for the selection, filtering, and presentation of advertisements based on detected program events and profiles contained in the Home Information System. 
         [0010]    “Viewing Characteristics based Personalized Ad Streaming in an Interactive TV Environment” by Thawani; Amit, Gopalan; Srividya, and Varadarajan; Sridhar (appeared in the Proceedings of the 2004 IEEE Consumer Communications and Networking Conference, Caesar&#39;s Palace, Las Vegas, Nev., USA, Jan. 5-8, 2004 (CCNC 2004)) describes a channel surfing analysis algorithm for predicting the “user(s) in front” of a television to enable deciding about the nature of ads that are likely to have an impact. 
         [0011]    The known systems are largely related to the selection and scheduling of ads based on sponsors&#39; needs and in some cases accounting of relevance. And, hence, do not explicitly address the various issues related to ad monotonicity and ad wear-out. The present invention provides a system and method for the randomized selection and scheduling of ads so as to “beat the expectations” of the users thereby reducing ad monotonicity and ad wear-out. 
       SUMMARY OF THE INVENTION 
       [0012]    The primary objective of the invention is to reduce ad monotonicity and ad wear-out in the context of ads shown during the watching of a content on a television, personal computer, or mobile phone. 
         [0013]    One aspect of the invention is to exploit multiple ad models for effective display of ads. 
         [0014]    Another aspect of the invention is to exploit multiple ads related to the multiple ad models. 
         [0015]    Yet another aspect of the invention is to randomly select ads. 
         [0016]    Another aspect of the invention is to randomly distribute the randomly selected ad models throughout the content timeline. 
         [0017]    Yet another aspect of the invention is to ensure that the randomly selected ads are relevant to the content being watched. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]      FIG. 1  depicts an overview of the System for Ad Scheduling (SAS). 
           [0019]      FIG. 2  provides an overview of the illustrative ad models. 
           [0020]      FIG. 3  provides an overview of Time Allocation for Ads. 
           [0021]      FIG. 3   a  provides an approach for Time Allocation for Ads. 
           [0022]      FIG. 4  provides an overview for Scheduling of Ads. 
           [0023]      FIG. 4   a  provides an approach for Randomized Ad Scheduling (LbAC). 
           [0024]      FIG. 4   b  provides an approach for Randomized Ad Scheduling (SbAC). 
           [0025]      FIG. 4   c  provides an approach for Randomized Ad Scheduling (SAC). 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0026]    Ads are an important component of any content delivery system. For example, consider a broadcasting scenario: in this case, the content is typically delivered onto a television sets at homes. Most of the programs aired in this manner have one or more sponsors and in return, each of the sponsors gets spots during the airing of the corresponding programs to display their ads. The major expectation on the part of sponsors is that ads, especially during prime time, lead to increased sales revenue. However, the constant bombardment of the same ads can turn out to be counterproductive: viewers may turn off television sets or may skip to another channel. It has been observed in the literature that such a behavior is partially due to the boredom of seeing the same ad again and again leading to ad wear-out. The main challenge is to make ad viewing a pleasure thereby, reducing the boredom and ad wear-out. A solution for this challenge is to identify ads, to be inserted at various time points during the delivering and displaying of a content (say, a movie), so that it is not monotonous and it “beats the expectations.” 
         [0027]      FIG. 1  depicts an overview of the System for Ad Scheduling (SAS). Given a content (say, a movie), the system ( 100 ) identifies multiple ads that are relevant to the content and a subset of these identified ads gets inserted into the content for to be shown on an end user device (say, a television). The basic idea is to use as many ad models as possible for the displaying of the ads so that there is a variety; further, the ads are randomly selected and displayed at randomly selected time points leading to a surprising package of content and ads. It is anticipated that such a surprising package overcomes the fatigue due to the watching of traditional display of ads and hence, the ads can have a positive impact on the viewers. Initially, the input content is analyzed so as to retrieve a set of content-specific ads ( 110 ) from a database containing multiple versions of multiple ads related to multiple ad models ( 120 ). In order to avoid monotonicity, the ad models are randomly selected distributed randomly throughout the viewing timeline associated with the content ( 130 ). The set of content-specific ads contains more ads than what can get inserted into the content and hence, a subset is randomly selected ( 140 ) keeping in mind the ad model distribution. Finally, the randomly selected ads are bound with the content based on the randomly distributed ad models ( 150 ) to create a surprising package of content and ads. 
         [0028]      FIG. 2  provides an overview of the illustrative ad models. Ad models describe the varied ways in which ads can be displayed on an end user device. A brief overview of Ad Models is as follows:
       1. Ad models play an important role in overcoming ad monotonicity and wear-out;   2. Ad models provide additional ad spots;   3. Ad models combined with right ads at right time enhance return on investment for ad sponsors;   4. Ad models exploit multimedia richness and multi-modal cognitive capabilities of humans;   5. Ad models vary in their temporal durations providing greater display flexibility;   6. Ad models efficiently and effectively exploit display area;       
 
         [0035]    For illustrative purposes, three classes of ad models are identified.
       1. Simultaneous Ad models Class (SAC): The main characteristics of the ads part of this class are: (a) Short duration ads; (b) Typically, have a theme; (c) Displayed ads are relevant to and are simultaneous with the content being shown; and (d) Typically, displayed in a non-intrusive manner without audio.   2. Short-break Ad models Class (SbAC): The main characteristics of the ads part of this class are: (a) Short duration ads; (b) Typically, tend to combine multiple partial themes; and (c) Typically, shown separately in full screen with audio enabled.   3. Long-break Ad models Class (LbAC): These are like typical TV commercial ads.       
 
         [0039]    Some Illustrative Ad Models are as follows: 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                 Class 
                 Model 
                 Description 
               
               
                   
               
             
             
               
                 SAC 
                 M1: L-Ads 
                 An L-shaped, typically, animated ads 
               
               
                 SAC 
                 M2: F-Ads 
                 Floating ads - An image block floats on the 
               
               
                   
                   
                 content; 
               
               
                 SAC 
                 M3: S-Ads 
                 Scrolling ads - A predominantly text oriented ad 
               
               
                   
                   
                 scrolls at the bottom bordering the content; 
               
               
                 SAC 
                 M4: P-Ads 
                 Picture ads - Typically, ads are shown as picture 
               
               
                   
                   
                 in picture; 
               
               
                 SbAC 
                 M5: Sv-Ads 
                 Short video ads - Typically, short in duration; 
               
               
                 LbAC 
                 M6: Lv-Ads 
                 Long video ads - Typically, traditional ads; 
               
               
                   
               
             
          
         
       
     
         [0040]      FIG. 3  provides an overview of Time Allocation for Ads. There are a variety of ad models and each of these ad models forms part of a class. Keeping in mind the ad monotonicity and ad wear-out, it is required to allocate time of display for the various ads ( 300 ). In order to have more flexibility in ad randomization, the time allotment is undertaken at class level. That is, total ad durations are allotted for the various of the classes such as SAC, SbAC, and LbAC. For a given content, the appropriate system parameters ( 310 ) are obtained. Also, obtained are the content-specific ads related to the various classes ( 320 ). Based on these inputs, ad time is allotted for each of the classes and each block of each of these classes. Here, a block is a group of ads of a class, say, based on the duration of the ads. 
         [0041]      FIG. 3   a  provides an approach for Time Allocation for Ads. 
       An Approach for Time Allocation: 
       [0042]    Input: T—Duration of Content (say, a movie);
 
AMR—The expected ad movie ratio; typically, set by the providers;
 
W 1 —The weight associated with the class SAC;
 
W 2 —The weight associated with the class SbAC;
 
W 3 —The weight associated with the class LbAC;
 
Cads—Content specific ads related to the various classes;
 
         [0043]    Here, AMR stands for Ad to Movie Ratio. This is one of the operator/provider controlled parameters and indicates the amount of possible ad time while delivering a particular content, say a movie. Typically, it is a value between 0 and 1. Operator/provider also specifies how the ads related to the various of the classes need to be prioritized. One way to specify this information is to define a weight for each class such that the sum of the weights is unity. For example, for each of the three classes, a weight is associated as follows: W 1  with SAC, W 2  with SbAC, and W 3  with LbAC with W 1 +W 2 +W 3 =1; 
       Output: Class-Block-Wise Ad Time Allocations 
       [0000]    
       
         Step 1: Based on AMR and T, determine Ta (total ad duration) as T*AMR; 
         Step 2: Distribute Ta across three different classes:
       Ta 1  associated with SAC as Ta*W 1 ;   Ta 2  associated with SbAC as Ta*W 2 ;   Ta 3  associated with LbAC as Ta*W 3 ;   
     
         Step 3: Analyze the ads of class SAC based on Cads with respect to their durations; Note that due to the nature of SAC ads, the durations vary over a small range; Let N 1  be the total count of SAC ads; Let N 11 , N 12 , . . . , N 1   j , . . . be the counts associated with the various durations;
       For each N 1   j , compute the ad duration Ta 1   j  as Ta 1 *N 1   j /N 1 ;   
     
         Step 4: Similarly, for each N 2   j , compute Ta 2   j  as Ta 2 *N 2   j /N 2  with N 2  being the total count of SbAC ads in Cads;
       For each N 3   j , compute Ta 3   j  as Ta 3 *N 3   j /N 3  with N 3  being the total count of LbAC ads in Cads;   
     
         Step 5: The class-block-wise ad times are as follows:
       SAC-N 11 -Ta 11 , SAC-N 12 -Ta 12 , . . . , SAC-N 1   j -Ta 1   j, . . . ;      SbAC-N 21 -Ta 21 , SbAC-N 22 -Ta 22 , . . . , SbAC-N 2   j -Ta 2   j, . . . ;      LbAC-N 31 -Ta 31 , LbAC-N 32 -Ta 32 , . . . , LbAC-N 3   j -Ta 3   j, . . . ;      
     
       
     
         [0057]      FIG. 4  provides an overview for Scheduling of Ads. The randomized scheduling of ads ( 400 ) takes content for which ads are being scheduled as input along with class-block-wise ad time durations ( 410 ) and the content-specific ads of the various classes ( 420 ) to generate randomized ad schedules.  430  depicts a portion of content with scheduled ads. Note that in one of the embodiments, SAC class ads are simultaneous while SbAC and LbAC class ads are shown during a break. As a consequence, in the case of scheduling of ads related to SAC class, initially, a model is selected randomly and a randomly selected ad based on the selected ad model is bound with the content. On the other hand, in the case of SbAC or LbAC class, an ad is selected randomly and queued up to be displayed during the break. For the purposes of ad binding, the content is viewed as a structure comprising of multiple segments, with each segment comprising multiple scenes, and finally, with each scene comprising multiple key frames.  440  depicts a scheduling of an ad of SAC class. Note that “scheduling of ads” and “binding of ads” are used interchangeably. Note that SAC class ads are bound with respect to an anchor key frame. That is, the ad gets displayed either starting at key frame or the key frame appears at about half way during the simultaneous displaying of the ad. SbAC class ads are scheduled during a break following a randomly selected scene ( 450 ). And, finally, LbAC class ads are scheduled at the end of a segment ( 460 ). 
         [0058]      FIG. 4   a  provides an approach for Randomized Ad Scheduling (LbAC). Ads of the various classes are scheduled based on the allotted durations: Ta 1  for SAC class, Tat for SbAC class, and Ta 3  for LbAC class. 
         [0059]    An Approach for Ad Scheduling for ads of LbAC class is as follows: 
       Input: 
       [0000]    
       
         
           
             C—Content (say, a movie); Content is structured as follows: 
             Key Frames and their annotations; 
             Scenes and their annotations; 
             Segments; 
             Note that C has multiple segments with each segment having multiple scenes and each scene having multiple key frames;
 
Output: Scheduled ads;
 
Step 1: Work top-down; Process and schedule LbAC ads;
 
             Let S 1  be the number of segments in C; 
             Distribute Ta 3  equally among S 1  segments; 
             Obtain ads of class LbAC as CLbAds; 
           
         
       
     
       Step 1a: 
       [0000]    
       
         
           
             For each segment, perform the following:
           Let Ta 3   j  be the ad break duration;   
         
           
         
       
     
       Step 1a1: 
       [0000]    
       
         
           
             Randomly select an ad A from CLbAds such that ShowFlag of A is OFF; 
             If no such ad can be selected, reset ShowFlag of the ads and randomly reselect; 
             Based on the duration D of A and Ta 3   j , Check if A can be inserted into the queue; 
             If so, Set ShowFlag of A as ON, and Update Ta 3   j;  
           Repeat Step 1a1 until sufficient ads are queued up;   
         
             Else, if Ta 3   j  exceeds half of D, then Set ShowFlag of A as ON; 
             If this is the last segment, update Tat and Recompute SbAC-class-block-wise durations; 
             Else Update the duration of the next segment break (Ta 3 ( j+ 1)); 
           
         
       
     
         [0078]    Note that the ads are randomly selected so as to create a surprise in viewer&#39;s mind. Further, all the ads in the class are given an opportunity to be selected before reconsidering an ad again for scheduling. 
         [0079]      FIG. 4   b  provides an approach for Randomized Ad Scheduling (SbAC). Having scheduled LbAC ads, the next step is to schedule SbAC ads. In this embodiment description, while no block-wise randomized selection is described in the case of LbAC class ads, the selection of SbAC ads illustrates block-wise randomized selection. 
         [0080]    An Approach for Ad Scheduling (Contd.): 
         [0000]    Step 2: Process and schedule SbAC ads;
       Let K be the possible number of scene breaks;   Obtain the number of ads in various blocks—N 21 , N 22 , . . . , N 2   j , with N 2  being the total number of ads in SbAC class;   Identify the weights R 2   j  based on N 2   j /N 2 ;       
 
       Step 2a; 
       [0000]    
       
         
           
             Generate a random number j based on R 21 , R 22 , . . . , R 2   j, . . . ;    
             Select the block SbAC-N 2   j;    
           
         
       
     
       Step 2b: 
       [0000]    
       
         
           
             Generate a random number I based on K; 
             Obtain ShowCount of Scene I and if ShowCount exceeds a pre-defined threshold, remove Scene I from further considerations; Go to Step 2b; 
             Compute SAR based on the scene duration and the number of ads scheduling during the scene break; 
             If SAR exceeds AMR, remove Scene I from further considerations;
           Go to Step 2b;   
         
             Based on Scene I annotations obtain a set of filtered ads based on SbAC-N 2   j  ads; 
             Select an ad A randomly based on the set of filtered ads; 
             If no ad can be selected, go to Step 2b; 
             If ShowCount of A exceeds a pre-defined threshold, Go to Step 2b; 
             Based on the duration D of A and Ta 2   j , Check if A can be inserted into the queue; 
             If so, Increment ShowCount of A and Update Ta 2   j;    
             Else, if Ta 2   j  exceeds half of D, then Increment ShowCount of A;
           Update a randomly selected Ta 2   m  based on Ta 2   j;      Remove the block SbAC-N 2   j  from further considerations;   If no such Ta 2   m  can be selected, update Ta 1  based on Ta 2   j  and Recompute SAC-class-block-wise durations; Go to Step 3;   
         
             Repeat from Step 2a until sufficient ads are queued up; 
           
         
       
     
         [0102]    Note that SAR stands for Scene Ad Ratio which is used in conjunction with AMR, the Ad Movie Ration. SAR of a scene describes the ratio of the amount of ads that has been inserted for to be displayed during the scene break, and the scene duration. 
         [0103]      FIG. 4   c  provides an approach for Randomized Ad Scheduling (SAC). 
         [0104]    The final step is to schedule SAC ads. 
         [0105]    An Approach for Ad Scheduling (Contd.): 
         [0000]    Step 3: Process and schedule SAC ads;
       Obtain a set SK of key frames of content C;       
 
       Step 3a: 
       [0000]    
       
         
           
             Generate a random number to select a key frame KF from SK; 
             Determine the Scene I associated with KF; 
             Compute SAR of Scene I; 
             If SAR exceeds AMR, remove KF from further considerations;
           Remove also the other key frames of Scene I from further considerations;   Go To Step 3a;   
         
             Find the number of frames NF that separates KF from the nearest ad break; 
             If NF is within a pre-defined threshold, remove KF from further considerations; Go to Step 3a; 
           
         
       
     
       Step 3b: 
       [0000]    
       
         
           
             Generate a random number to select a block SAC-N 1   j  of SAC class; 
             Find the number of frames NFB that separates KF from the nearest ad break associated with the block SAC-N 1   j;    
             If NFB is within a pre-defined threshold, Go to Step 3b; 
           
         
       
     
       Step 3e: 
       [0000]    
       
         
           
             Based on key frame KF annotations, obtain a set of filtered ads based on SAC-N 1   j  ads; 
             Select an ad A randomly based on the set of filtered ads; 
             If ShowCount of A exceeds a pre-defined threshold, remove A from further considerations; Go to Step 3c; 
             If no such ad can be selected, Go to Step 3b; 
             Based on the duration D of A and Ta 1   j , Check WA can be bounded; 
             If so, Bind A with KF; Update ShowCount of A; Update Talk 
             Else, if Ta 1   j  exceeds half of D, then Increment ShowCount of A;
           Update a randomly selected Ta 1   m  based on Ta 1   j;      Remove the block SAC-N 1   j  from further considerations;   
         
             Repeat from Step 3a until sufficient ads are bounded; 
           
         
       
     
         [0128]    Thus, a system and method for randomized ad selection and scheduling is disclosed. 
         [0129]    Although the present invention has been described particularly with reference to the figures, it will be apparent to one of the ordinary skill in the art that the present invention may appear in any number of systems that need to overcome monotonicity and package a deliverable that “beats the expectations.” It is further contemplated that many changes and modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the present invention.