Abstract:
A system and method for scheduling advertisements in a television service network environment. An ad scheduler prepares an ad insertion schedule based on channel change statistical information and avail time information. The scheduler evaluates the statistical information, time durations between adjacent avails in a presentation stream, and the relatedness of market segments assigned to a plurality of advertisements. It schedules the ads into presentation stream groups based on this evaluation. The statistical ad scheduling allows the system to eliminate “forced” switching between multiple presentation streams, whereby system wears and malfunctions can be decreased.

Description:
[0001]    This patent application claims the benefit of priority based on U.S. Provisional Patent Application No. 60/229,156 filed on Aug. 31, 2000, owned by the same assignee of the present invention and entitled “Method and System for Addressable and Program Independent Advertising,” which is incorporated herein by reference. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    The present invention relates to targeted television advertising and, more particularly, to a system and method for delivering statistically scheduled advertisements in multiple presentation streams to subscribers in a television service network.  
           [0003]    In conventional “program-linked” television advertising, each advertisement is linked to a particular television program so that all viewers viewing the particular program see the same advertisements linked to that program. Viewers who are not viewing that program will not see the advertisements linked to that program. In such program-linked advertising, the advertisements are simply part of the data stream from the head end, i.e., from the central office of the television service provider, to all subscribers of that service.  
           [0004]    However, with modern digital television service systems, such as digital cable systems, DBS (Digital Broadcast Satellite) systems, and SDV (Switched Digital Video) systems, more personalized television service is possible. For instance, in DBS and SDV systems, individual subscriber households can be addressed selectively through set top boxes or STBs. In digital cable systems, a group of subscriber households can be selectively addressed through a cable node serving that group. For this reason, STBs and cable nodes are also referred to herein as addressable units. Through the addressable units, the television service provider can send different data to different subscribers or groups of subscribers.  
           [0005]    The selective addressability of these modern digital television service systems renders more targeted television advertising possible. In accordance with one targeted television advertising method, ads that have been prepared to interest a particular subscriber of the television service network may be inserted into ad spots or “avails” of the television presentation stream at the particular subscriber&#39;s device (e.g., a set top box). As a result, subscribers at different households will see different advertisements that are particularly directed to each subscriber even though they are viewing the same programming. PCT Patent Publication No. WO 99/66719 entitled “Techniques for Intelligent Video Ad Insertion,” which is herein incorporated by reference, discloses at least one such scheme. Other such schemes are discussed in aforementioned Provisional Patent Application No. 60/229,156, owned by the same assignee of the present invention.  
           [0006]    Although these systems provide effective means to deliver targeted ads to the subscribers, in some applications, it may be desirable to have a system which delivers targeted ads to the subscribers without the ad insertion occurring at the subscriber&#39;s STB. Applicant&#39;s co-pending U.S. patent application Ser. No. 09/750,800, filed on Dec. 28, 2000 entitled “System and Method for Delivering Targeted Advertisements using Multiple Presentation Streams,” which is herein fully incorporated by reference, discloses such a system.  
           [0007]    In the system of Applicant&#39;s co-pending application Ser. No. 09/750,800 filed on Dec. 28, 2000 entitled “System and Method for Delivering Targeted Advertisements Using Multiple Presentation Streams”, a television presentation stream corresponding to a particular programming channel is “replicated” to produce a plurality of presentation streams, collectively referred to herein as a presentation stream group. The system produces a plurality of such presentation stream groups each corresponding to one of a plurality of programming channels. All the presentation streams in a presentation stream group have the same programming and the same avails at the same locations. Each single presentation stream in the group carries in its avails a plurality of advertisements each directed to a different advertiser-specific market segment. This is necessary if the system were to use advertiser-specific market segments, i.e., market segments that have been uniquely defined by each advertiser. According to this arrangement, however, a subscriber viewing the same presentation stream will likely view ads that are inappropriate for that subscriber since a single presentation stream can carry ads directed to vastly different market segments.  
           [0008]    To address this problem, the system of Applicant&#39;s co-pending application Ser. No. 09/750,800 filed on Dec. 28, 2000 entitled “System and Method for Delivering Targeted Advertisements Using Multiple Presentation Streams” “forces” switching between the presentation streams in the presentation stream group to select a presentation stream that is most appropriate for the subscriber at any given time. This “forced” switching is triggered every time an avail or a cue tone indicative of an avail is detected. Thus, the use of “forced” switching can increase system wear and malfunctions. Accordingly, a technique is desired which avoids the use of “forced” switching to deliver ads directed to different advertiser-specific market segments to the subscribers in a most targeted manner.  
           [0009]    In view of the foregoing, it is an object of the present invention to provide a system and method which delivers targeted television advertising via a network without the use of “forced” presentation stream switching.  
           [0010]    It is another object of the present invention to provide a system and method for scheduling advertisements in the presentation stream group based on channel change statistics and avail time information.  
         SUMMARY OF THE INVENTION  
         [0011]    The present invention delivers advertisements directed to advertiser-specific market segments to the subscribers of a television service network in a targeted manner without the use of “forced” switching between multiple presentation streams.  
           [0012]    In accordance with the present invention, a plurality of presentation stream groups are produced, each corresponding to a particular programming channel. A presentation stream group is composed of replicated presentation streams that are generated by “copying” one presentation stream corresponding to a particular programming channel. Thus, all the presentation streams in a presentation stream group have the same programming and the same avails at the same locations, into which different ads will be inserted in the different presentation streams.  
           [0013]    The scheduling of the advertisements into the presentation streams is carried out according to certain criteria predetermined based on channel change statistics. The channel change statistics identify the probabilistic percentages of viewers/subscribers who would likely change their television channels during different time durations. By evaluating these channel change percentages, the system or system operator selects at least one particular time duration (e.g., X minutes) that corresponds to an acceptable channel change percentage. The selected time duration is then used as a threshold value to which time durations between avails in a presentation stream are compared. According to the criteria for scheduling the advertisements and based on the probabilistic assumption that any given viewer has changed channels, if a time duration between two adjacent avails in a presentation stream is greater than or equal to the threshold value, ads directed to different market segments (which can be significantly different) can be inserted respectively into these avails; and if a time duration between two adjacent avails in a presentation stream is less than the threshold value (i.e., avails are more closely located to each other), ads directed to similar market segments are inserted respectively into these avails.  
           [0014]    The presentation stream groups carrying the scheduled advertisements are delivered to a plurality of local routing stations. Depending on the type of system, the routing station may reside at a set top box (e.g., for DBS or digital/analog cable system) or a Universal Service Access Multiplexer (USAM) device (e.g., for SDV). Only in response to a channel selection by a viewer/subscriber, the routing station detects (e.g., by detecting cue tones) an ad/avail location in the presentation stream group corresponding to the requested channel and determines which one of the presentation streams in that group is most appropriate for viewing by the viewer. This determination may involve identifying a presentation stream that is carrying an ad directed to a market segment that best matches the demographics or other characteristics of the viewer. The identified presentation stream is displayed to the viewer on the viewer&#39;s display or TV.  
           [0015]    Thus, the present invention provides targeted television advertising by the use of channel change statistics and switching between presentation streams only in response to a viewer&#39;s channel change requests. If a time elapsed from the viewer&#39;s last channel change is relatively short (e.g., less than the threshold value), then the viewer will likely view a series of ads that are directed to similar market segments, whereby targeted advertising is achieved. On the other hand, if a time elapsed from the viewer&#39;s last channel change is long (e.g., greater than or equal to the threshold value), then the channel change statistics indicate that the viewer would likely have changed his or her channel by this time and the channel change would have triggered switching between presentation streams to select the most appropriate presentation stream for the viewer. In this manner, the viewer will likely view the most appropriate ads at any given time. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]    [0016]FIG. 1 is a block diagram of exemplary television service communication network environments in which the present invention may be practiced;  
         [0017]    [0017]FIG. 2 is a diagram of an ad scheduler according to one embodiment of the present invention;  
         [0018]    [0018]FIG. 3 is a diagram of a device for generating channel change statistics according to one embodiment of the present invention;  
         [0019]    [0019]FIG. 4A is an example of a normal distribution graph depicting exemplary channel change statistical data according to the present invention;  
         [0020]    [0020]FIG. 4B is a diagram of a presentation stream representing the channel change statistical data of FIG. 4A;  
         [0021]    [0021]FIG. 5 is a diagram of two exemplary presentation stream groups according to the present invention;  
         [0022]    [0022]FIG. 6 is a diagram of a presentation stream depicting ad insertion windows;  
         [0023]    [0023]FIG. 7 is a block diagram of an advertisement delivery system in accordance with the present invention;  
         [0024]    [0024]FIG. 8 is a block diagram of the routing station shown in FIG. 7; and  
         [0025]    [0025]FIG. 9 is an example of a table of scheduled/inserted ads which may be used in the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0026]    [0026]FIG. 1 is a block diagram of various television service delivery network environments in which the present invention may be practiced. Three of the most common types of television service delivery networks are illustrated in FIG. 1, namely, (1) a Digital Broadcast Satellite (DBS) network system, (2) a digital/analog cable network system, and (3) a Switched Digital Video (SDV) network system.  
         [0027]    In a DBS system, a programming stream comprising upwards of a hundred channels of television programming is delivered directly from a geo-stationary satellite transmitter  12  orbiting the earth to a receiving antenna  14  mounted on or near each subscriber&#39;s house and from the antenna via a cable to a satellite receiving station  15  in the subscriber&#39;s house  16 . The satellite receiving station  15  (which is a form of STB) receives the channels of programming, selects a requested channel and demodulates the signal for delivery to a monitor (e.g., a television, not shown). The DBS network can direct different programming data to different set top boxes  15  or groups of set top boxes  15  such that the set top boxes  15  are selectively addressable by the DBS network. Most DBS systems are arranged such that data can also be sent in the upstream direction, that is, from the set top box  15  to the DBS provider. In most DBS systems, the set top box  15  also is coupled to the telephone line and is designed and programmed to place telephone calls to the DBS service provider to periodically send information in the upstream direction. Such information, for example, may comprise requests for Pay-Per-View programs or requests for changes in the subscription (a request that one or more of premium channels be added to the service, etc.).  
         [0028]    In a typical digital/analog cable network  20 , multiple channels of television information are transmitted from a head end or central office  22  via a cable network  23 . Particularly, the channels are transmitted via cables  24  to nodes  26 . The nodes  26  are essentially switching/routing stations which service multiple homes (usually a few hundred). The nodes  26  route the signals to individual subscribers  28 . The individual subscriber will have set top boxes  27  that select a particular channel from the transmit stream, demodulate it and forward it for display on one or more monitors or televisions (not shown). Different data streams or signals can be sent to the different nodes  26  of the network such that households coupled to the node  26   a  can receive different programming than households coupled to the node  26   b . Thus, such systems are addressable by node, but not by individual subscriber. Upstream information may be sent from the set top box to the central office via a dedicated upstream channel over the cable. In cable systems that do not support two-way communication, the upstream “channel” can be through the telephone as described above in connection with DBS systems.  
         [0029]    In accordance with a third type of system, namely, SDV system  30 , television programming is transmitted over the regular telephone network. In this system, each individual subscriber household may be addressable. For instance, television signals are transmitted from a central office  30  via wire, typically fiber optic cable  32 , to a Universal Service Access Multiplexer (USAM) device  34  which then delivers the data to multiple individual subscriber households  35  via regular telephone twisted wire pair  36  using modems (e.g., VDSL modems). The USAM device  34  receives a wide bandwidth signal comprising some or all of the television channels. However, because of the bandwidth limitations of twisted pair wire, typically only about one channel of television programming at a time can be delivered from the USAM to the household. Accordingly, the subscriber has a set top box  38  that is similar in functionality to the set top box of a digital cable system or DBS system, except that when the viewer changes channels, the STB transmits a request to the USAM device  34 , which switches the channel for the viewer and begins sending the newly selected channel to the household. Typically, the channel selection signal from the viewer is known as a UPCI (User Perceived Channel Indicator) which the USAM device  34  converts into an appropriate BpID (Broadcast Program ID) and uses to send data corresponding to the BpID to the viewer&#39;s STB. SDV systems are essentially fully modern asynchronous two-way communication networks. Thus the set top box can transmit information upstream via the same VDSL modem that receives the downstream signals. SDV systems generally operate using asynchronous transfer mode (ATM) protocol which is well known in the networking arts.  
         [0030]    A preferred embodiment of the present invention will now be described. In accordance with the preferred embodiment, a plurality of presentation stream groups are produced each corresponding to a particular programming channel. A presentation stream group is composed of multiple presentation streams that are generated by “copying” one presentation stream corresponding to a particular programming channel. Thus, all the presentation streams in a presentation stream group have the same programming and the same avails at the same locations. A television service provider may determine how many presentation streams can exist in each presentation stream group. Generally, because of the bandwidth limitations imposed on the programming channels, only a limited number of presentation streams (e.g.,  3 - 7 ) may exist in a presentation stream group.  
         [0031]    In accordance with the present invention, each advertiser defines its own set of advertiser-specific market segments for addressing targeted ads. Applicant&#39;s co-pending U.S. patent application Ser. No. 09/731,606 filed on Dec. 7, 2000 entitled “System for Providing Targeted Advertisements using Advertiser-Specific Target Groups,” which is herein fully incorporated by reference, discloses examples of systems and methods for forming advertiser-specific market segments, which may be used in the present invention. Since the total number of different advertiser-specific market segments will typically exceed the limited number of presentation streams allowed per presentation stream group, each single presentation stream will need to carry ads directed to different advertiser-specific market segments.  
         [0032]    The scheduling of these ads directed to different advertiser-specific market segments into the avails of each presentation stream according to the present invention will now be described. FIG. 2 shows a block diagram of an ad scheduler  44  according to the present invention. As shown in FIG. 2, the ad scheduler  44  generates an ad schedule for inserting ads into the avails of each presentation stream in the presentation stream groups. Generally, the scheduler  44  would reside at the head end of the system.  
         [0033]    In scheduling the ads, the ad scheduler  44  relies on market segment information  41 , ad/avail information  43 , subscriber information  45 , and channel change statistics  46 . The subscriber information  45  may identify all or groups of subscribers on the network and their demographics or other characteristics. The market segment information  41  may identify a list of advertiser-specific market segments created in the system and their characteristics. The ad/avail information  43  may identify a list of ads to be scheduled as well as avail time information such as avail sizes, time durations between adjacent avails in a presentation stream, ad insertion window times, etc. The scheduler  44  correlates this information  41 ,  43  and  45  to identify a list of ads to be scheduled and the market segments associated with the ads, and a list of subscribers or subscriber groups and the market segments to which they belong (which may be used at the local routing level, e.g., STB, USAM, etc.). In one embodiment, individual subscribers may be identified by the MAC IDs of subscribers&#39; STBs and, in digital cable systems, groups of subscribers may be identified by cable node numbers.  
         [0034]    The channel change statistics  46  identify an average channel change frequency for subscribers/viewers on the network and other statistical data pertaining to the channel change habits of the subscribers, such as standard deviations, distribution types. The statistics  46  also indicates an average viewing time for each channel/program, which is the reciprocal of the average channel change frequency. It further indicates different percentages of viewers on the network who would likely change their channels during different time durations. A device as shown in FIG. 3 can be used to generate the channel change statistics  46  utilized in the ad scheduling process of the present invention. This device may be located at a STB or at the head end. If the device is located at the STB, the raw channel change data collected by the STB may be kept within the STB for security reasons, and the STB may only communicate the final outcome (i.e., the change statistics  46 ) to the head end so that the head end can use it to schedule the ads for insertion.  
         [0035]    In the device shown in FIG. 3, a data collector  51  monitors the channel change habits of a group of subscribers on the network during a predetermined time period and collects channel change data from these subscribers. This can be easily achieved in two-way communication systems such as SDV. Also any of the well-known methods for determining the channel to which a TV is tuned, can be used to collect the channel change data. For maximum efficiency, this data can be collected by day part since channel change frequencies may differ significantly based on the time of day. A statistics module  52  receives the channel change data from the data collector  51  and performs statistical calculations on it to generate the channel change statistics  46 , such as an average channel change frequency, a standard deviation, a distribution type, etc.  
         [0036]    By evaluating the channel change percentages identified in the statistics  46 , the ad scheduler  44  or system operator selects at least one particular time duration (e.g., X minutes) that corresponds to an acceptable channel change percentage. The selected time duration is then used as a threshold value to which each time duration between two adjacent avails in a presentation stream is compared. According to the criteria for scheduling the advertisements, if a time duration between two adjacent avails in a presentation stream is greater than or equal to the threshold value, ads directed to different market segments can be inserted respectively into these avails since most viewers/subscribers would likely have changed their channels during this time duration. The channel change would have triggered selection of the most appropriate presentation stream from the presentation stream group corresponding to the newly selected channel, as described later in more detail. However, if the time duration between the adjacent avails is less than the threshold value (i.e., avails are more closely located to each other), ads directed to similar market segments are inserted respectively into these avails since the viewers would less likely have changed their channels during this time duration, i.e., they would be viewing the same presentation stream.  
         [0037]    Now, having described the principles of ad scheduling of the present invention, an example is now provided referring to FIGS. 4A, 4B and  5 . FIGS. 4A and 4B respectively illustrate a graph and a diagram depicting exemplary channel change statistics  46 . As shown in FIGS. 4A and 4B, the channel change statistics  46 , in this example, indicate that the channel change data manifest a normal distribution with the average channel change rate of 15 minutes and a standard deviation of 5 minutes. This indicates that 50 percent of the viewers/subscribers would likely change their channels during a 15-minute time span, 84 percent of the viewers would likely change their channels during a 20-minute time span (one standard deviation), and 96 percent of the viewers would likely change their channels during a 25-minute time span (two standard deviations). In relying on this data, the ad scheduler  44  or system operator may select “20 minutes” as a threshold value (if 84% is an acceptable channel change percentage). Obviously, other threshold values can be selected if desired.  
         [0038]    Then the threshold value is compared to time durations between adjacent avails in the presentation stream groups. For the purpose of explaining this process, FIG. 5 is provided which illustrates two exemplary presentation stream groups  61 a and  61   b . The first presentation stream group  61   a  is composed of replicated presentation streams (CC- 1 , CC- 2  and CC- 3 ) corresponding to “Comedy Central” or CC channel. The second presentation stream group  61   b  is composed of replicated presentation streams (MTV- 1 , MTV- 2 , MTV- 3  and MTV- 4 ) corresponding to “MTV” channel. Obviously, other presentation stream groups may exist. Also, it should be noted that all the presentation streams in each presentation stream group  61   a ,  61   b  have the same programming and the same avails at the same locations as discussed hereinabove. For instance, each presentation stream in the first presentation stream group  61   a  has the same programs (e.g., Program  1 , Program  2 ) and the same avails (e.g., Av 1 , Av 2 , Av 3 , Av 4 ) at the same locations.  
         [0039]    As shown in FIG. 5, the ad scheduler  44  determines, e.g., from the avail information  43 , that a time duration of  21  minutes exists between the scheduled avails Av 1  and Av 2 ,  0  minute between avails Av 2  and Av 3 ,  26  minutes between avails Av 3  and Av 4 , and so on. In accordance with one embodiment, this determination can be made by calculating the time difference between scheduled times of adjacent avails in the presentation streams. Since the time duration between avails Av 1  and Av 2  is 21 minutes which is greater than the threshold value of 20 minutes, a market segment (MK-A 1 ) is assigned to avail Av 1  and a market segment (MK-B 1 ) that is significantly different from the previous market segment (MK-A 1 ) is assigned to avail Av 2 . On the other hand, since the time duration between avails Av 2  and Av 3  is 0 minute, a market segment (MK-B 2 ) that is similarly related to the previous market segment (MK-B 1 ) is assigned to avail Av 3 . Since the time duration between avails Av 3  and Av 4  is  26  minutes which is greater than the threshold value of 20 minutes, a market segment (MK-L 1 ) that is significantly different from the previous market segment (MK-B 2 ) is assigned to avail Av 4 . In this manner, the avails of all the presentation streams in the first group  61   a , the second group  61   b  and other presentation stream groups are assigned to different advertiser-specific market segments. Once the assignment of the market segments is completed, the advertisements that correspond to the assigned market segments are inserted correspondingly into the avails. If a viewer&#39;s channel selection  1  for requesting “CC” channel occurs before avail Av 2  as shown in FIG. 5, the routing station (FIG. 7) examines the market segments/ads assigned to avail Av 2  and selects one of the presentation streams having the market segment/ad that is most appropriate for the viewer.  
         [0040]    In some embodiments, avails may not fall exactly on the scheduled times since the programs segments can vary slightly in length. Also, avails may be offset by certain amounts from their scheduled times in certain special circumstances, such as live events (particularly live sports events) where the avail locations are estimated. In such embodiments, a time duration “α” between the end of an ad insertion window of an avail and the start of an ad insertion window of the next avail may be used in lieu of the time difference between scheduled times of adjacent avails. An ad insertion window in the television art is known to be a window of time located on either side of the start of an avail, during which an ad insertion unit may anticipate the arrival of a cue tone or other ad insertion indicator known in the art. To better understand, FIG. 6 shows an example of an ad insertion window of 5 minutes on either side of the start of the expected avail (Avail # 1  or Avail # 2 ), wherein the window time is measured from the start of the expected avail. The time duration α represents the elapsed time between the two ad insertion windows of adjacent avails. Therefore, in these embodiments, instead of using the time difference between the scheduled times of adjacent avails, the time duration α may be used as the time duration between adjacent avails to schedule the advertisements in the presentation streams.  
         [0041]    In accordance with one embodiment, each market segment characteristic identified in a market segment can be assigned with a characteristic number (e.g., “wealthy” characteristic may be assigned with the number  7 ), so that each market segment may have at least one characteristic number assigned to it. Then the characteristic numbers in one market segment may be compared to the characteristic numbers in another market segment to determine a degree of “relatedness” between these market segments, e.g., by determining if any of the characteristic numbers in one market segment is also present in other market segments. This comparison result indicates how similar or different the advertiser-specific market segments may be and can be used to assign the market segments in the avails of the presentation stream groups.  
         [0042]    In accordance with another embodiment, instead of assigning market segments to the avails, each advertisement may be given one market segment number based on its market segment characteristics, and these numbers can be compared to each other to determine how similar or different the market segments of the ads may be. Then the advertisements will be inserted into the avails based on this comparison results. Other methods of determining the relatedness of market segments are possible and can be used in the present invention.  
         [0043]    [0043]FIG. 7 shows a block diagram of an advertisement delivery system  100 , including the scheduler  44  of FIG. 2, according to a preferred embodiment of the present invention. The advertisement delivery system  100  may be implemented in any of the television service delivery networks (e.g., SDV, digital cable TV, DBS shown in FIG. 1). Although only two presentation stream groups  61   a  and  61   b  are specifically illustrated for the sake of clarity, it is understood that other or additional presentation stream groups may exist.  
         [0044]    As illustrated in FIG. 7, the advertisement delivery system  100  includes an ad database  42  for storing a library of advertisements to be inserted into the avails of the presentation stream groups, the ad scheduler  44  for producing an ad schedule according to the scheduling discussed above, a multiple presentation stream (MPS) generator  40  for generating the presentation stream groups (e.g.,  61   a  and  61   b ) carrying ads directed to different advertiser-specific market segments according to the ad schedule, a distribution network  50  for distributing the presentation stream groups, and a plurality of local routing stations  60 ,  60  for receiving the presentation stream groups through the network  50  and delivering one of the presentation streams in a presentation stream group according to channel requests by the subscribers/viewers on the network. These components are all operatively coupled. In some embodiments, the MPS generator  40  may be located at the head end of the system, and the routing stations  60 ,  60  may be located at the local distribution points, e.g., at STBs for analog/digital cable TV systems and satellite systems such as DBS, USAM devices for SDV systems, etc. In other embodiments, both the MPS generator  40  and the routing stations  60 ,  60  may be located at the head end of the system.  
         [0045]    The MPS generator  40  receives a presentation stream corresponding to each programming channel from a program source or the like. In this example, the MPS generator  40  receives a presentation stream “CC” corresponding to “Comedy Central” channel, and a presentation stream “MTV” corresponding to “MTV” channel. The MPS generator  40  “replicates” these presentation streams to produce the first and second presentation stream groups  61   a  and  61   b  according to the number of presentation streams allotted per presentation stream group. It should be noted that different numbers of presentation streams may be present in different presentation stream groups. For instance, if MTV channel is extremely popular, the TV service provider or the system operator may decide to allot  5  replicated presentation streams to correspond to MTV channel whereas only  3  replicated presentation streams may be allotted to the less popular CC channel. The MPS generator  40  inserts appropriate ads into the avails of the replicated presentation streams according to the ad schedule provided by the ad scheduler  44 . The ads that are inserted into the avails can be provided by the ad database  42  which may be stored in any type of storage unit, such as ROM, RAM, optical disks, magnetic disks, etc.  
         [0046]    The plurality of presentation stream groups (e.g.,  61   a ,  61   b ) are distributed from the MPS generator  40  to each of the routing stations  60 ,  60  through the distribution network  50 , e.g., SDV, DBS, Internet, analog/cable TV, HFC, or wireless TV network such as LMDS (Local Multipoint Distribution System) or MMDS (Multichannel Multipoint Distribution System). The routing station  60  can reside at a STB or the like, or a USAM device depending on the type of television network system.  
         [0047]    The operation of the routing station  60  may also vary slightly depending on the system type. For instance, if the system  100  is a digital/analog cable system or a satellite system such as DBS, the routing station  60  may reside at a STB or the like and receive the plurality of presentation stream groups. Only in response to a channel selection by the viewer, the routing station  60  detects an upcoming avail for the selected channel and selects a presentation stream from the presentation stream group corresponding to the selected channel which is carrying the most appropriate upcoming ad for the viewer. The most appropriate ad may be an ad directed to a market segment that best matches the market segment characteristics or demographics of the viewer or viewer&#39;s household. The selected presentation stream is then displayed to the viewer on a monitor.  
         [0048]    If the system is an SDV system, the routing station  60  may reside at a Universal Service Access Multiplexer (USAM) device. The routing station  60  in the USAM device receives the plurality of presentation stream groups. In response to a particular channel selection by a viewer, the STB located at the viewer&#39;s household generates a channel request to the USAM device serving that STB. Only in response to this request, the routing station  60  in that USAM device selects one of the presentation streams from the presentation stream group corresponding to the requested channel which is carrying the most appropriate upcoming ad for the viewer. The routing station  60  delivers the selected presentation stream to the STB which in turn displays the presentation stream on the viewer&#39;s display device.  
         [0049]    In all these systems, “forced” switching employed in the system of Applicant&#39;s co-pending application Ser. No. 09/750,800 is not needed to display targeted ads, because the ads have be scheduled based on the channel change statistics to compensate for the omission of “forced” switching.  
         [0050]    [0050]FIG. 8 illustrates a block diagram of the routing station  60  in FIG. 7 in accordance with the present invention. Each routing station  60  is assigned with certain demographic or other characteristics based on the characteristics of the individual subscriber or group of subscribers served by the routing station  60 . This characteristic information may be prestored at the routing station  60  or other locations, or may be frequently transferred to the routing station  60  from the head end of the system  100 .  
         [0051]    As illustrated in FIG. 8, each routing station  60  includes a plurality of routing units  70 ,  70  each being responsible for processing one presentation stream group corresponding to a particular programming channel. For instance, the first routing unit  70  receives the first presentation stream group  61   a  corresponding to “Comedy Central” programming channel, whereas the second routing unit  70  receives the second presentation stream group  61   b  corresponding to “MTV” programming channel. Each of the routing units  70  includes a switch  62 , an ad location detector  64 , and a presentation stream selector  66 , all operatively coupled.  
         [0052]    In response to a channel selection request from a viewer (subscriber), only the routing unit  70  responsible for the requested channel is activated. The ad location detector  64  in the active routing unit  70  detects ad locations (e.g., using cue tones or avail time) in the received presentation streams to determine where the upcoming ads may be located. Since all the presentation streams in a presentation stream group have the same programming data and the same avails at the same locations, it is only necessary to monitor one presentation stream in a presentation stream group to detect ad locations for all presentation streams in that group.  
         [0053]    PCT Patent Publication No. WO 99/66719, the disclosure of which is incorporated herein by reference, discloses several methods of detecting ad locations, such as detecting the black frames which television programmers typically provide in the video stream at the beginning of a television commercial avail. These methods may be utilized in the present invention to detect the ad locations. In another embodiment, digital cue tones set by DVS-253 digital video standards promulgated by the Society of Cable and Television Engineers (SCTE), which indicate start of avails, may be used. In still another embodiment, well-known analog cue tones embedded within the vertical blanking interval of a television signal, may be used.  
         [0054]    The ad location detector  64  in the active routing unit  70  outputs a detection signal to the presentation stream selector  66  when the upcoming ad location is detected. In response to the detection signal, the presentation stream selector  66  determines which one of the presentation streams in the presentation stream group is carrying an upcoming ad directed to the market segment that best matches the market segment characteristics or demographics of the viewer served by the routing station  60 . According to this determination, the selector  66  generates a switching signal to the switch  62  to select the identified presentation stream. Based on the switching signal, the switch  62  selects the identified presentation stream and outputs it. The output presentation stream may be delivered to a STB in SDV systems, or displayed on a monitor (e.g., a TV) in digital/analog cable and DBS systems.  
         [0055]    In determining which presentation stream to select, the presentation stream selector  66  may examine a table or list of scheduled/inserted ads identifying which ads are inserted in which avails of the presentation streams of the group. This table may further identify market segment(s) associated with each scheduled ad. The table may be provided to the selector  66  by the ad scheduler  44  through the distribution network  50  or by a server on the network  50 . From the table of scheduled ads, the selector  66  determines a list of ads inserted in the upcoming avails of the presentation streams and identify the market segment assigned to each of these ads/avails. The selector  66  then compares these market segments with the demographics or other characteristics assigned to the routing station  60 . If there is only one match, then the selector  66  instructs the switch  62  to switch to the presentation stream carrying the ad/avail corresponding to that matched market segment. If there is more than one match, then the selector  66  may select one market segment according to some predetermined criteria and generate a switching signal to the switch  62  to select the presentation stream carrying the ad/avail corresponding to the selected market segment. In the alternative, other schemes (e.g., random selection) may be used to select only one of the matched market segments. If there is no match, or a match with a below-threshold correlation level, the selector  62  may select a pre-designated default presentation stream in the presentation stream group as the most appropriate presentation stream, or other selection scheme can be used to select one of the presentation streams in the presentation stream group.  
         [0056]    It should be understood that the components shown in FIG. 8 represent functional aspects of the routing station  60  and that each of these components may be implemented using analog circuits and/or digital circuits, including finite state machines, digital signal processors, computers, central processing units, application specific integrated circuits (ASICs), and programmed general purpose processors.  
         [0057]    In accordance with certain embodiments where the television service delivery system is an SDV system or other system that does not use cue tones, and where avails may not fall exactly on the scheduled times, the switching between replicated presentation streams can be performed based on a time range encompassing the expected/scheduled avail time and the ad insertion window(s) to ensure a smooth and continuous display. In these embodiments, an exemplary table such as one shown in FIG. 9 may be used by the routing station  60  to select appropriate presentation streams. This table may identify avail time range, scheduled/inserted ads, and market segment(s) associated with each ad. In one embodiment, the avail time range may correspond to the end of the ad insertion window of a previous ad and the end of the ad insertion window of the current ad. If the ad insertion windows overlap, the avail time range may start or end at the mid point of the overlap. Further, this table may include UPCIs (User Perceived Channel Indicators) and corresponding BpIDs (Broadcast Program IDS) typically used in SDV systems.  
         [0058]    The use of the table in FIG. 9 can be as follows. If a viewer changes a channel to MTV (UPCI  05 ) during the avail time range, e.g., from 20:01:00 to 20:18:00 during which an avail/ad is expected, the table is searched for an entry that matches the UPCI (i.e., UPCI  05 ) for the given time. The search results in multiple hits, e.g., E 1 -E 3 . Then the market segments assigned to the ads in these entries E 1 -E 3  are compared with the market segment characteristics assigned to the viewer&#39;s STB (e.g., identifiable by the MAC ID) to select the most appropriate presentation stream for the viewer. For instance, assuming that the viewer has been assigned to a “college” market segment, the comparison results will indicate that the entry El is the most appropriate since it has the “College or Wealthy” market segment characteristics. If no match is found, however, one of the hit entries E 1 -E 3  may be selected randomly, or a default entry may be selected. If more than one match is found, certain priority criteria or any other scheme may be used to narrow the multiple hit entries into one that is best suitable for the current viewer. Once the most appropriate entry (e.g., E 1 ) has been identified, then the BpID of the identified entry (e.g.,  178 ) is used to output the presentation stream (data) corresponding to that BpID for viewing by the viewer.  
         [0059]    As discussed above, in some embodiments, the market segments of the present invention may include a “default” segment for capturing any subscriber or subscriber group that does not fall into any of the defined segments. Any number of market segments may be created in accordance with system feasibility. The market segments may not need to encompass all subscribers on the network. It is also possible that some subscribers or groups of subscribers may fall into more than one market segment of a particular advertiser. In those cases, certain priority schemes or other schemes may be used to match the subscriber or group of subscribers to one advertiser-specific market segment, if that is desired.  
         [0060]    Thus, the present invention provides a system and method for scheduling advertisements into the avails of presentation stream groups based on channel change statistics and avail time information. This allows the system to perform presentation stream switching only in response to channel selection requests from subscribers. Thus, “forced” switching can be omitted and targeted advertising using advertiser-specific market segments are achieved. Accordingly, effective targeted television advertising can be achieved.  
         [0061]    The invention has been thus described with respect to delivering targeted ads to the subscribers on a television service network. However, it should be understood by persons of skill in the art that the invention can be used to delivery other data. Furthermore, the principles of scheduling advertisements for insertion into the avails using channel change statistics and avail times can be applied to any other system which requires the insertion of ads directed to different advertiser-specific market segments into a presentation stream.  
         [0062]    Moreover, instead of providing a plurality of routing units each responsible for a different presentation stream group, it is possible to provide one routing unit that is responsible for all presentation stream groups.  
         [0063]    Having thus described a few particular embodiments of the invention, various alterations, modifications, and improvements will readily occur to those skilled in the art. Such alterations, modifications and improvements as are made obvious by this disclosure are intended to be part of this description though not expressly stated herein, and are intended to be within the spirit and scope of the invention. Accordingly, the foregoing description is by way of example only, and not limiting. The invention is limited only as defined in the following claims and equivalents thereto.