(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization
`International Bureau
`
`(43) International Publication Date
`25 April 2002 (25.04.2002)
`
`
`
`PCT
`
`(10) International Publication Number
`WO 02/33973 A2
`
`(51) International Patent Classification7:
`
`H04N 7/16
`
`(74) Agents: MAJERUS, Laura, A. et al.; Fenwick & West
`LLP, Two Palo Alto Square, Palo Alto, CA 94306 (US).
`
`(21) International Application Number:
`
`PCT/US01/32169
`
`(22) International Filing Date: 15 October 2001 (15.10.2001)
`
`(81) Designated State (national): JP.
`
`(25) Filing Language:
`
`English
`
`(84) Designated States (regional): European patent (AT, BE,
`CH, CY, DE, DK, ES, FI, FR, GB, GR, IE, IT, LU, MC,
`NL, PT, SE, TR).
`
`(26) Publication Language:
`
`English
`
`Published:
`
`(30) Priority Data:
`60/240,715
`60/240,714
`
`15 October 2000 (15.10.2000)
`15 October 2000 (15.10.2000)
`
`US
`US
`
`(71) Applicant: SONICBLUE INCORPORATED [US/US];
`2841 Mission College Boulevard, Santa Clara, CA 95054—
`1838 (US).
`
`(72) Inventors: ROSENBERG, Scott, A.; 119 Prospect Street,
`Apt. B, Somerville, MA 02143 (US). SELF, Matthew, H.;
`768 Bain Place, Redwood City, CA 94062 (US).
`
`without international search report and to be republished
`upon receipt of that report
`
`For two-letter codes and other abbreviations, refer to the ”Guid-
`ance Notes on Codes andAbbreviations ” appearing at the begin-
`ning ofeach regular issue ofthe PCT Gazette.
`
`02/33973A2
`
`(54) Title: METHOD AND SYSTEM FOR PAUSE ADS
`
`O
`a (57) Abstract: A system and method for placing ads on a client—side Video replay system during a pause mode.
`
`Page 1 of 36
`
`OPENTV EXHIBIT 2007
`
`NETFLIX, INC. v. OPENTV, INC.
`IPR2014-00252
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Method and System for Pause Ads
`
`Related Applications
`
`This application claims priority under 35 U.S.C. § 119(e) to both U.S. Provisional
`
`Application No. 60/240,715, filed October 15, 2000, and entitled “Method and System
`
`for Dynamic Ad Placement,” and U.S. Provisional Application No. 60/240,714, filed
`October 15, 2000, and entitled “Method and System for Pause Ads,” both of which are
`
`incorporated by reference herein in their entirety.
`
`Technical Field
`
`The present invention relates generally to video data recorders and, more
`
`specifically, to a method and system for determining and playing ads in video data
`
`recorders.
`
`Background of the Invention
`
`Advertisers have long tried to make sure that the right people are watching their
`
`advertisements. Television advertisers spend large amounts of money trying to make
`
`sure their advertisements (“ads”) are aired during television shows having the proper
`
`demographics. Thus, television advertisers attempt to match the ad to the demographics
`
`of the audience for particular television programs, purchasing advertising slots for those
`
`television programs that they hope will attract the proper audience for their ads.
`
`Unfortunately, there is no way for the advertisers to know in real time Whether people are
`
`watching their ads or whether the ads are reaching the targeted demographic groups.
`
`Similarly, there is no way for television advertisers to determine the viewing patterns of
`
`individual viewers or to target ads to individual viewers since the same ads are broadcast
`
`to everyone watching a particular program.
`
`Page 2 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Advertisers on the Internet have been targeting their ads for several years. An
`
`Internet advertiser can currently register for an ad-serving service, which attempts to
`
`distribute the advertiser’s ads to users who will be receptive to the ads. To View a web
`
`page on the Internet, a user enters the URL of the web page or clicks on a link to the web
`
`page. The web page itself is fetched fiom the appropriate web server, and an ad is
`
`fetched from the ad service. The ad service attempts to determine which ad to send to the
`user based on which web page the user has requested and on various other factors known
`
`about the user (such as, for example, information about the user gleaned from cookies or
`
`from user registration procedures). Because the ad service is located on the server side,
`
`the ad service generally relies on one-size—fits-all rules to determine which ads to display
`
`for a particular page request. Because the ad selection process is centrally located,
`performance requirements often necessitate a simplification of the logic used to select an
`
`ad.
`
`In addition, an Internet ad service is “coupled” to the user request. An Internet ad
`
`server bases the ad it serves, at least partly, on the URL of the requested web page. It is
`
`also important to note that the Internet ad server needs to send an ad to the user as quickly
`
`as possible, because the user is expecting to receive the requested web page (along with
`
`any other third party content, such as ads) as soon as possible. The fact that the typical
`
`Internet ad server is time—constrained makes it more difficult for the ad server to perform
`
`elaborate methods to determine which ads to send. Overcoming this problem typically
`
`requires the use of very high-end computers to serve the ads.
`
`Ultimately, Internet ad serving solutions are request-based. That is, an ad is
`
`served from the central server in response to a request. Because many requests are
`
`fulfilled in parallel, ads for competing products may be served for each of the separate
`
`requests. While in theory the server could track ads being served to each client and
`
`eliminate the serving of two competing ads to the same client, the centralized ad serving
`
`environment, with millions of users and with ad serving distributed over many actual
`
`servers, makes this extremely difficult.
`
`Page 3 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Moreover, an Internet ad server needs to be in substantially constant
`
`communication with the Intemet, since ad requests are received constantly. Such a
`
`system was not designed to work in situations where the ad-receiving client is only
`
`intermittently connected to the Internet.
`
`What is needed is a way to deliver ads to receptive audiences where there is
`
`ample time to determine who might be the best target for each particular ad and where the
`decision is sensitive to the context in which the ad request was made. In addition, it is
`
`desirable to be able to place ads extremely quickly for each individual user. Lastly, it is
`
`. desirable to locate opportunities to insert additional ad content to the video playback.
`
`Summary of the Invention
`
`The described embodiments of the present invention display an ad or similar
`
`video picture during a pause interval that occurs when the user places the video replay
`device in a pause mode. The pause ad (or other video) can be a still or a moving picture.
`One embodiment displays an advertisement (either a still or a moving picture). One
`
`embodiment displays a user-selected ad or wallpaper design (such as family photos or
`
`.
`video movies).
`The process of determining which ad to display is called the ad selection process.
`The described embodiments decouple the ad selection process from the request for ad
`content. It should be understood that the invention can be employed in a variety of
`devices, such as video data recorders and set-top boxes, where the device is not in
`
`continuous communication with an initial ad source.
`The context in which the described embodiment operates is an individual user’s
`video replay system, although the invention is not intended to be limited to video replay
`systems. In a Video replay system, a user selects program content by replaying
`previously “taped” content from a hard drive or similar storage medium or by turning on
`his television (or other content source) and selecting a program or show to watch. In the
`latter case, the selected program content is received by the replay system; it is first stored
`on the storage medium and then displayed on a display device such as a television set or
`monitor. A dynamic ad placement engine of a preferred embodiment preferably operates
`
`3
`
`Page 4 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Within the video replay system and needs to select ads only for a single video replay
`
`system. The ad placement engine in a particular video replay system always selects ad
`
`content for that video replay system and does not have to spend time trying to determine ‘
`
`the identity and preferences of every possible viewer of the content since only a very
`
`small subset of viewers watch content on a particular video replay system.
`
`In the described embodiment, the device containing the dynamic ad placement
`
`engine is not necessarily always in communication with an initial source of ads. For
`
`example, an ad source might communicate with a video replay system periodically, such
`
`as once a day or several times a week, either at a set time or in response to an instruction
`
`or query, to obtain information about ads that may be displayed on the device.
`
`Additionally, in the described embodiment, a dynamic ad placement engine
`
`knows about the current context of the system before an ad request is received. In the
`
`described embodiment, the ad selection process is “decoupled” from the ad content
`
`delivery process. Various software applications in the video replay system can determine
`
`at which times and under which circumstances they desire to display ads. The
`
`applications do not necessarily rely on whether the user has changed the content being
`viewed to determine when to request and display ads. This system is CPU-efficient and
`
`allows ads to be evaluated “at leisure” before they are served.
`
`The described embodiments of the present invention do not select ads for
`
`placement at the time that the user selects his viewing content. Instead, the described
`embodiment of the present invention allows the user to select content as a separate
`
`function. Ad selection is not performed at the time of user content selection, but instead,
`
`is asynchronous to the user’s actions in selecting programming to watch. Thus, the ad
`selection engine gains evaluation time to make a more informed decision about which ad
`
`should be displayed next by the Video replay system.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Fig. 1(a) is a block diagram of a video replay system that can include ad
`
`placement software in accordance with the present invention.
`
`Page 5 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Fig. 1(b) is an example of a video replay system displaying a full page ad.
`
`Fig. 1(c) is an example of a video replay system displaying a banner ad.
`
`. Fig. 2 is an overview of a video replay system.
`
`Fig. 3 is a diagram of interaction between an application and ad placement engine
`
`in a video replay system.
`
`Fig. 4 is a block diagram of elements in the ad placement engine of Fig. 3. Fig. 5
`
`is an example set of rules that comprise an ad control file.
`
`Fig. 6 shows examples of types of ad parameters
`
`Fig. 7(a) shows the example rules of Fig. 5 in table form.
`
`Fig. 7(b) shows an example trigger table, including the trigger for the ad of Fig. 5.
`
`Fig. 8 shows an example of a heap data structure.
`
`Fig. 9(a) shows a flowchart of a method performed when a new ad control file is
`
`received from the server.
`
`Fig. 9(b) shows a flowchart of a method performed when a context update occurs.
`
`Fig. 9(c) is a flow chart showing a method for selecting an ad in response to an ad
`
`request.
`
`Fig. 10 is a flow chart showing a method of displaying a pause ad (or other
`
`video).
`
`DETAILED DESCRIPTION OF PREFERRED ENIBODIMENTS
`
`Embodiments of the present invention are now described with reference to the
`
`figures where like reference numbers indicate identical or fimctionally similar elements.
`The described embodiment contains a dynamic ad placement engine as one
`
`component in an advertising system. The described advertising system is preferably
`
`located in a device, such as a video replay system, (for example, a video replay system
`sold by ReplayTV, Inc. ofMountain View, CA), although the present invention can be
`used with other devices, including other video replay systems, including but not limited
`
`to interactive TV, set—top applications and devices, and handheld video players.
`
`1. Example Video Replay System
`
`Page 6 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`Fig. 1(a) is a view of a client-side video replay system 104 and a display 106. In
`
`the Figure, the program 112 (such as a television program) is received from a broadcaster
`and is passed to a display (such as a television set) 106, along with other content such as
`ads and programming guides. The invention can be implemented in a wide range of
`devices and is not limited to video replay units. The client-side unit 104 contains a
`
`storage medium (not shown), such as a hard drive, which is used to store the incoming
`program signal and other information. The saved signal can then be Viewed at a later
`time or can be viewed immediately from the storage medium. The client-side unit 104
`includes a processor and memory (or similar components used to direct the functionality
`of the unit) and implements the described functions for the particular unit 104. Client—
`side video replay system 104 can make placement decisions When disconnected from the
`
`initial source of ads, such as an ad server.
`The client—side video replay system .104 receives control information 128, such as
`ads and program guides, fiom a server and sends control information 129, such as ad
`impressions and accounting information, to the server. It should be understood that the
`system can receive various types ofprogramming, including but not limited to cable
`content, television content, high definition TV content, digital TV content, pay per view
`content, and content broadcast over the Internet. It should also be understood that display
`device 106 can be any appropriate type of display device, including but not limited to a
`
`digital or analog television set, an Internet appliance, a cellular device, or a wireless
`device. The video replay unit and the display device may be separate (as shown),
`
`integrated together, or broken into even more functional units than shown.
`It will be understood that one implementation of the video replay system uses a
`
`telephone line to implement one or more of control lines 128/129. The information is
`passed to and from the client side 104 on a regular basis (such as every 24 hours). Thus,
`the system downloads ads from the server relatively infrequently. In the described
`embodiment, the system receives information over a telephone line and receives daily all
`
`the ads it is going to place for the next 24 hours. Other implementations use an Internet
`connection as control lines 128/129 and connect regularly or on a more frequent basis.
`
`Fig.1 (a) also shows a remote control device 130, which is used to control the
`
`Page 7 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`video replay system. In other embodiments, the system is controlled, for example, over
`the Internet or by way of controls on the client-side unit 104 itself.
`
`2. Client—Side Video Replay System
`
`a. Ad placement engine
`
`The primary responsibility of an ad placement engine in accordance with the
`described embodiments is evaluation, placement, and logging of advertising placement
`on its individual video replay system. In a described embodiment, a software application
`requests an ad (or indicates the existence of an ad opportunity). These ads may be, for
`example, ads displayed during a user-initiated pause in the displayed video stream. ‘Other
`types of ads include main ads to be placed in a main menu of the Video player and ads to
`be placed in banners or in areas of the display reserved for ads. The described
`embodiments of the present invention can be used in any client side element with any
`software application that places ads in an appropriate location and circumstance.
`
`The described embodiments decide which ads to place based on factors such as
`the context, history, user profile, and constraints specific to each ad. One example of
`user context might include the program currently being viewed by the user. It should be
`noted that the user may have been viewing this current program for any previous amount
`of time (hours, minutes, or seconds). In some implementations, ad placement may occur
`after a user’s initial request for a video program or other content.
`
`Fig. 1(b) is an example of a video replay system displaying a full-page ad. In the
`example, display 106 in a Video replay system is caused to display the current program
`164, which can either be a program currently being received by the system or a program
`received previously. At some point in time, in this example, a software application that
`controls the display decides to display a full page ad. As described below in detail, the
`application requests an ad from a dynamic ad placement engine and displays the resulting
`ad 166 on the display 106. It is important to note that, in the displayed embodiment, the
`
`Page 8 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`- application’s request for an ad is decoupled from the user’s request for content. For
`example, the user may have watched the same prOgram/content for several hours, but
`when he pauses the program to get a snack, the application may decide to request and
`display a full page ad as shown. In contrast, the user may channel surf all night, changing
`the programs displayed on display 106 every few minutes. In certain implementations,
`the user’s actions may trigger a request for an ad and in other implementations, a night of
`
`channel surfing will not trigger such as request. Request and display of ads is under
`
`control of the controlling application. In some embodiments, an ad is requested as soon
`
`as the user presses the pause button. In other embodiments, for example, the ad is
`requested a predetermined amount of time after the user presses the pause button.
`
`Fig. 1(c) is an example of a video replay system displaying a banner ad 176. A
`banner ad can be displayed in a predetermined portion of the display or in a portion of the
`display decided by the application controlling the display. In one embodiment, banner ad
`176 is displayed along with the program guide displayed on display 106. In other
`embodiments, banner ad 176 is displayed as part of a “zone” guide display or next to the
`
`program content.
`
`Fig. 2 is a block diagram of a server side and a client side of an example video
`replay system 200 that can include ad placement software in accordance with the present
`invention. The figure includes a server 102, as well as client 104 and display 106. The
`
`system receives signals from a broadcaster 110, such as a television, cable, or pay-per-
`view broadcaster that broadcasts one or more programs 112 (such as a video broadcast) to
`a video capture engine 131 on the client side 104. The Video capture engine 131 contains
`a tuner (if needed) to select which of the possible programs 112 to receive and a storage
`medium (such as a hard drive) that retains the program 112 as it is received. The user can
`then choose to either display the program 112 as it is being received or save the program
`
`112 for playback at a later time (or both).
`
`Server 102 includes an advertising section 120 that allows a user to create ad
`
`campaigns, perform ad management, and perform advertisement tracking (both
`
`Page 9 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`placement and viewing tracking); an asset manager 122 that manages distribution of ads,
`tracking information, etc; a program guide creation section 124, and One or more replay
`
`servers 126. Lineups 114 of programs to be broadcast in the future are sent to program
`creation guide 124, which creates program guide data 123 that is passed to the client side
`104 via replay server 126. Asset manager 122 collects, tags, and creates scheduling rules
`for ads (digital assets“ 125). Digital assets 125 (such as ad content and ad rule sets) are
`passed to the client side 104'for display in accordance with the present invention. A
`broadcast schedule (such as scheduling rules) is passed to the client side 104 for use in
`electronic programming guide applications. As discussed below, some of the electronic
`programming guide data may also be used in guiding placement of ads. Information
`passed to client side 104 from replay server 102 is designated as reference numeral 128.
`
`The client 104 includes the video capture engine 131, which passes captured
`programming content to asset manager 130. Asset manager 130 also passes tuning data
`to video capture engine 131, indicating when the user has, for example, changed the
`
`television or cable channel.
`
`The client side 104 also includes an ad placement engine 132 that communicates
`
`with asset manager 130. Ad placement engine 132 is described in detail below. One or
`more applications 133 communicate with ad placement engine 132 to register ads. It will
`be understood that the described system is but one possible example of a video replay
`
`system incorporating the present invention.
`
`Fig. 3 is a diagram of interaction between one or more software applications 133
`and ad placement engine 132 in a client—side video replay system 104. It should be
`understood that the application 133 can be any appropriate application, including but not
`limited to an electronic programming guide or video viewed by a user. The. described
`applications 133 have the ability to detect a change of viewing context in the system. For
`example, the user might change the television channel so that a new program is displayed
`on display 106. This channel change causes a change in viewing context.
`
`When application 133 detects a viewing context change (or soon thereafter), it
`
`9
`
`Page 10 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`sends a context update 310 to ad placement engine 132. Ad placement engine 132
`
`updates its context information as discussed below. (For example, the global parameter
`g_programtitle as shown in Fig. 5 might be altered to reflect the new program title).
`In
`the Figure, zero or more viewing context changes can occur before a request for an ad is
`made. If, for example, the user is channel surfing, many frequent context updates might
`
`be made before a request for an ad is made. If the user watches the same program for
`
`several hours, many requests for ads might be made, but no context updates might occur.
`
`' The context changes can include, but are not limited to context changes resulting from
`
`the user changing the channel on the video replay system. Other context changes include
`
`changes in time (i.e., time passing) and program changes within a channel.
`
`As shown in Fig. 3, when ad placement engine 132 receives a context update, it
`
`recalibrates an order and weight of ads in a heap data structure (see Fig. 8). This step may
`
`also add ads to or delete ads from the heap. In the described embodiment, this step
`
`constitutes recalibrating the ad heap as described below in connection with Fig. 9(b).
`
`When a screen with an ad opportunity is to be displayed, application 133 requests
`
`320 an ad fiom ad placement engine 132. In the described embodiment, an application
`might request an ad in several situations. For example, the user can choose to “pause”
`programming that he is currently viewing. Because the programming is “spooled” in
`Video capture engine 131 (or was previously stored in Video capture engine 131 and is
`now being replayed), the video capture engine 131 saves the incoming programming
`signal during the period that the display is “paused.” In the described embodiment, the
`pause fimction begins to display an ad for a predetermined period of time after the pause
`occurs. For example, the ad may be displayed 10 or 20 seconds after the display has been
`paused. In the described embodiment, the ad displayed in pause mode is generally a full-
`page ad (see Fig. 1(b)), although it could also be another appropriate type of ad. Thus,
`the user no longer sees the paused content on display 106 and begins seeing the ad. In
`
`the described embodiment, the user can indicate that he does not want to see pause ads —
`
`either as a global indication that affects all pause ads, or on a case by case basis, Where
`
`the user cancels individual pause ads. Certain applications also allow the user to set the
`
`10
`
`Page 11 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`amount of time that passes before pause ads are displayed in pause mode.
`
`After an ad is selected, it is returned 322 to the application 133, where it is
`
`displayed.
`
`In another embodiment, the application interj ects ads into predetermined areas of
`
`the electronic programming guide (see, for example, Fig. 1(c)). Thus, whenever the
`application is going to display the electronic programming guide, it requests an ad and
`inserts the ad into the predetermined area of the electronic programming guide. This ad
`may be a fullscreen ad or a banner ad that does not fill the whole screen. For example,
`the ad may be a banner ad inserted by the application into a “zone” page that displays
`various categories or “zones” ofprogramming (news, sports, content from predefined.
`licensing partners, etc). It should be understOod that a dynamic ad placement engine in
`accordance with present invention can be used to supply ads to any appropriate
`application. Moreover, in certain embodiments, the application 133 and the ad placement
`engine 132 are merged and are not separate modules.
`
`After an ad is successfully displayed, application 133 sends a request 330 to log
`
`placement of the ad.
`
`Fig. 4 shows detail of ad selection. In response to a request for an ad 320, ad
`placement engine 132 selects an ad from the top of an ad heap 350 and returns 322 the
`selected ad to the requesting appliCation where it is displayed in an appropriate manner.
`As shown in Figs. 3 and 4, the heap 350 may have been recalibrated between the time a
`context update 310 was received and an ad request 320 was received. Ad placement
`engine 132 preferably is not directly responsible for user-interface (U1) functionality,
`such as ad rendering or user navigation. On the other hand, ad placement engine 132
`makes informed decisions based on the current application context. The fact that the
`context update information 310 is exchanged in advance of a request for the ad allows the
`ad placement engine more time to select an optimal ad. When the user finally surfs to an
`appropriate screen location for ad placement (as determined by the application), the
`application 133 requests an ad from the ad placement engine 132. When an ad placement
`
`11
`
`Page 12 of 36
`
`

`

`W0 0
`
`2/33973
`
`.
`
`,
`
`PCT/US01/32169
`
`request 320 occurs, the ad placement engine 132 consults it ad heap 350 and returns the
`ad at the top ofthe heap (or the ad that is highest weighted thus far if it runs out of time in
`systems requiring an ad to be returned within a maximum time frame). The information
`returned in response to an ad request contains enough information that the application can
`
`display the ad.
`
`Lastly, after the ad has been displayed, application 302 sends logging information
`330 to ad placement engine 132 to inform ad placement engine 132 that the ad has been
`displayed. Ad placement engine 132 logs the logging information and eventually passes
`the logging information to server 102.
`
`Fig. 4 is a block diagram of elements in ad placement software 132 ofFig. 3.
`These elements include executable ad placement software 302 and interpreted runtime
`rules 304. The executable ad placement software 302 contains the runtime functionality
`of the ad placement software 132. The rules 304 are executed by a rule interpreter at
`runtime. In the described embodiment, the entry and exit points for rule evaluation are
`known and fixed at compile time of software 302. For example, the weight afforded a
`particular ad may be determined by a rule executed at runtime and, therefore, be known
`only at run—time, while the timing and frequency of the evaluation of the weight
`determination ruleIS performed only as determined at compile—time of software 302.
`Additionally, data structures that are used to prioritize and manage the ads (e.g., the heap
`350) exist in the executable domain 302. The mix of executable/binary functionality and
`interpreted rules in the described embodiment provides a combination ofboth flexibility
`and performance. Other embodiments may use other combinations of binary and/or
`interpreted software. Fig. 4 is provided by way of example only.
`
`In this embodiment, ads maintain their own state (for example, through local
`parameters discussed below). Rules for an ad reference that ad’s local state, as well as
`global context parameters, permitting some flexibility in the values returned by the rule.
`
`When a new ad is loaded from server 102, executable ad placement software 302
`loads the ad control file containing the rule set that describes the ad and stores it as a new
`
`12
`
`Page 13 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`rule set in rule sets 351 on the executable side. In certain embodiments, ads have a rule
`
`that determines the ad’s expiration date. For each ad, executable ad placement software
`
`302 evaluates the interpreted rules 304 to determine whether an older version of the
`loaded rule has expired 360. If the older version of the ad has expired, its rule set is
`removed from the system. In any case, the new rule set for the new ad is stored in rule
`
`sets 351. A status is returned 362 from the expiration request.
`
`When a context change is received (or a trigger event occurs as described below),
`
`the placement and weight of the ads are reevaluated 370 in accordance with the
`placement and weight rules of the respective ads. A placement and weight result is
`returned 372 for each ad and the position of the ads in the heap are modified accordingly.
`
`When an application indicates that it has placed an ad, a state update is sent to
`interpreted rules 304 so that the local parameters of the rule set for the ad can be updated.
`
`A status of the update is returned 382.
`
`b. Example ad control file
`
`Fig. 5 is an example rule set that comprises an ad control file. Each ad has an
`associated ad control file. An ad control file is the unit sent to client 104 and defines the
`appearance, placement, and other rules associated with an ad. The example is encoded in
`XML format, although any appropriate format will suffice. Each rule 502-532 has a
`parameter name, type, and value. Note that the rules whose names start with “exp” and
`“stmt” reference both local parameters for the ad and to global parameters (discussed
`below.) The rules whose names start with “l_*” define local parameters. Each rule
`evaluates to a value of the type defined in the rule (value32, string, etc).
`As shown in Fig. 5, the name space includes <parameter, value> pairs.
`Parameters can be one of several types, including string, int, floating point. In a preferred
`embodiment, the. parameters are stored on disk, which is memory efficient, but slow.
`Because the decisiOn as to ad placement is decoupled from the context change and does
`
`13
`
`Page 14 of 36
`
`

`

`WO 02/33973
`
`PCT/US01/32169
`
`not have to be performed quickly, the slow access due to storage of the parameters on
`
`disk is acceptable. Other embodiments may store parameters in memory.
`
`0. Ad parameters
`
`Fig. 6 shows examples oftypes of ad parameters that are referenced in the rules.
`' Global and context parameters (such as time and day of week, genre, and channel) are
`
`updated asynchronously to ad placement. Local ad parameters (such as impressions and
`“previous/last placemen ”) are updated following ad placement.
`
`(1. Data structures
`
`Fig. 7(a) shows some ofthe example rules ofFig. 5 in table form as they might be
`stored in interpreted rules software 304. Any appropriate manner of storing parameters,
`
`rules (here, a type ofparameter), and triggers may be used to implement the present
`
`invention.
`Fig. 7(b) shows an example trigger table, including the trigger parameter for the
`ad of Fig. 5. In this example, the trigger is TOD (time of day). Whenever the global
`TOD parameter is updated, the placement value of the ad 1025 is re-evaluated. It should
`, be noted that not all ads have an associated trigger. Some ads have more than one
`
`associated trigger.
`
`'
`
`Fig. 8 shows an example of a heap data structure. As known to persons of
`ordinary skill in the art, a heap is a data structure in which the children of a node are
`guaranteed to have a lower priority than the parent. In the present case, this means that
`the node at the top of the heap 350 has a highest placement priority and is the ad that
`should be placed next in response to an ad request. Note that, in a preferred embodiment,
`the heap is updated after a system context change. However, when an ad request is
`received by the ad placement engine, the heap is already ordered such that the node on
`. the top of