Note: Descriptions are shown in the official language in which they were submitted.
CA 02240009 1998-06-08
W O 97/Z1~83 PCTnUS96/19509
EJ;-~O~ A~D ~Y~l -.~ FOR PI~CING
ADVERTI~ ' IN A ~OII~U-ll!;K Nk.-l ..'~k
~ NOTICE OF COPYRIGHTED M~TERIAL IN DISCLOSURE
A portion of the disclosure of this patent document
contains material which is subject to copyright protection.
The copyright owner has no objection to the facsimile
reproduction by anyone of the patent document or the patent
disclosure, as it appears in the Patent and Trademark
Office patent file or records, but otherwise reserves all
copyright rights whatsoever.
RJ.C'T~'~OUND OF THE lNV ~llON
Field o~ the Invention
The present invention relates generally to advertising
and, in particular, to a method and system for placing
advertisements in a computer network, such as a wide area
network or a metropolitan area network.
Description of the Prior Art
A number of information services are currently offered
on wide area public networks, such as the Internet. The
basic model of these services is that a query is processed
and a set of answers is returned. For example, a number of
yellow page searchable directories have been developed in
which users can query categories of products or services
(e.g., new car dea~ers) and the system returns a set of
vendors satisfying the ~uery.
One problem with these services is determ; n; ng who
should subsidize the end user's cost of using the services.
One way of providing such a subsidy is through the use of
-- 1 --
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
advertisements. Public networks, such as the Internet, are
starting to see random use o~ advertisements. For example,
some search engines used in public networks are sponsored
by a single vendor or company. The sponsoring vendor or
company will o~ten have an advertisement displayed on a
user's computer screen during use o~ the search engine.
Other search engines display randomly selected
advertisements ~rom a ~ixed set o~ advertisements.
As one example, a number o~ services on the World Wide
Web ("WWW") are currently using ad hoc means o~
advertising. That is, when a user uses certain search
engines ~or conducting a search, the user will be shown
advertisements while doing the searching. These
advertisements are sometimes re~erred to as "banner"
advertisements because they simulate a banner that the user
sees as the user is traveling down a ~road" on the computer
network. These advertisements are typicall~ tied to a
particular search page that the user encounters during the
search.
The current state o~ the art is such that when the
user uses a search e~gine, a randomly selected
advertisement is shown as i~ it is part of the search page.
For example, the user may enter a search request to see a
home page on cooking and, as a part o~ that page, the
existing systems might display an advertisement about cars.
This is a problem, o~ course, because there is no
connection made between the content o~ the advertisements
or the message o~ the advertisements and what the user is
actually searching. Another problem with the current
state o~ the art is that there is no guarantee associated
with the advertisements that they will be shown a certain
number o~ times or in a certain place on the page with
- 2 -
-
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
respect to the other pieces of data on that page. For
these reasons, the existing systems for placing
advertisements on computer networks, such as the Internet,
fail to take full advantage of the interactive/demand
driven environment of the online medium.
SUMMARY OF THE lNv~-lON
It is thus an object of the present invention to
provide an improved method and system for advertising on a
computer network, particularly a wide area or metropolitan
area network, which overcomes the above described problems
of existing advertising systems.
It is a further object of the present invention to
provide an effective advertising medium that anyone with a
personal computer can use to advertise on computer
networks.
It is a further object of the present invention to
provide a method and system for advertising in which
advertisements are more informative and provide a direct
link to additional information about the advertised product
or service or about the advertiser.
It is a further object of the present invention to
provide a method and system for advertising on a computer
network in which advertisements are more focused and
targeted, for example, by user ~ueries and user profiles,
including the past history of the user's interactions with
the system.
It is a further object of the present invention to
provide a method and system for advertising in which new
online publishers can be created with little effort.
It is a further object o~ the present invention to
provide a method and system for advertising in which
- 3 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19S09
advertisers can be guaranteed that their advertisements
will be displayed a certain number of times or in a
particular m~nn~r or under particular circumstances.
Additional objects, advantages and novel ~eatures of
the invention will be set forth in the description which
follows, and will become apparent to those skilled in the
art upon reading this description or practicing the
invention. The objects and advantages of the invention may
be realized and attained by the appended claims.
The present invention provides a new process and
system for online advertising. This new process will be
re~erred to throughout this application as query-based
advertising ("QBA"). In the QBA process, advertisements
are primarily triggered by user gueries. User ~ueries, as
used herein, re~er to requests ~rom an in~ormation consumer
~or one or more pages o~ information from a computer
network. As a result of a ~uery, a user is exposed to
advertisements with the present invention, i.e., the query
triggers advertisements.
In accordance with the present invention, a server
containing a collection o~ advertisements is placed in
electronic communication with a computer network. The
computer network is preferably a wide area network, such as
the Internet, or a metropolitan area network. As used in
this application, the phrase "computer network" refers to
any public or private data c~mml~n;cations network.
The advertisements on the server are ~ot tied to any
particular page cont~' n; ng information on the computer
network. Rather, the advertisements are contained on the
server, distinct from the pages that may or may not later
carry the advertisements. The pages by themselves have no
CA 02240009 l998-06-08
W O 97/21183 PCT~US96/19509
advertisements. Thus, the payes are analogous to a
newspaper or magazine devoid of any advertisements.
When the user requests a certain page or a certain
topic of in~ormation, the relevant pages are retrieved from
the computer network and shown to the user. The present
invention, upon receiving the user's request, retrieves
advertisements that are related to the user's action,
dynamically mixes the advertisements with the content of
the pages according to a particular layout, and displays
the pages with focused, targeted advertisements as a part
o~ the page. The advertisements can be made to satisfy a
set of constraints requested by the advertiser, as well as
the constraints of the publisher of the page, as further
discussed below.
The advertisement triggering mechanism of the present
invention is not random or coincidental, but rather, is
prespecified in advance. This speci~ication will be
referred to in this application as a contract. A contract
specifies the marketing rules that link advertisements with
specific queries. For example, a diet soft drink
advertisement may be shown when a user asks for a page
about exercising e~uipment. These rules are specified by
advertisers implementing the concept of "focus" or
~'relevance" o~ advertisements and help the advertisers to
target a specific audience. Owners of pages specify the
focus content of their pages through special tags within a
page. These tags are not displayed to the information
consumer; the tags are used to decide what advertisement
can be shown when the page is requested by a consumer.
The notion of a contract, however, goes well beyond
just marketing rules. First of all, the advertising space
on the online medium, although technically unlimited, is
- 5 -
CA 02240009 1998-06-08
w o 97nll83 PCT~US96tl9509
severely restricted by the user's attention span. Placing
advertisements on the ~irst page which constitutes the
answer to a ~uery gives the advertisements much higher
probability to be seen than on later pages o~ the answer.
This is analogous to a certain extent, to newspaper
advertising where advertising on the ~irst page of the
newspaper is more expensive than on the last page of the
newspaper. Thus, the present invention introduces the
concept o~ prime space as a part of the QBA.
10 ~ Prime space will be used in this application to refer
to limited advertising space on the first page of the
answer to a ~uery. Prime space is, in principle, as
attractive as prime time television. Prime space, like
prime time, is limited so it may be impossible to show all
the relevant advertisements in prime space.
As a solution to the prime space limitations, the
present invention provides guarantees to advertisers
through the use of contracts. The contracts provide tools
to specify such guarantees and to en~orce them.
Specifically, the present invention provides the following
types of guarantees (or "contracts") to advertisers:
1. Ratio-based: The ad will be shown in prime space
no less than a certain percentage of the times a
relevant ~uery is made by a searcher.
25 - 2. Exclusive or Competitive: Ad A is never to be
shown in prime space when ad B is shown.
3. Dependent: Ad A is to be shown with a
predetermined probability when ad B is shown in
prime space.
4. Story: An ad consisting of several sub-ads will
be shown in prime space in sequence to a
consumer.
- 6 -
,
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
5. Frequency-based: The ad will be shown i~ prime
space a certain number of times in a given time
period (e.g., 100 times per month).
Additionally, the contracts may also specify the type
of layout used to mix ads together with the data. This may
include the layout types, and so ~orth.
The present invention also provides means for
det~rm;n;ng whether there are any contracts that cannot be
satisfied. For example, i~ the prime space is suf~icient
to hold only two ads, it is impossible to guarantee 100%
ratio for more than two ads. Similarly, if ad A is never
to be shown when ad B is shown and if both ad A and ad B
are equally relevant according to ~ocus matching, then it
is impossible to guarantee ratios above 50% ~or both ads A
and B.
The present invention uses algorithms to check ~or
contract consistency to ensure that all contracts that are
accepted can be properly satisfied. An advertiser can ask
~or a certain contract (e.g., 5% relative coverage in prime
space) and the present invention will determine whether
that contract can be satisfied. I~ not, the system
suggests what coverage it can provide. A~ter the contract
is determined to be consistent, the present invention will
en~orce the contract by displaying advertisements in
accordance with the contract.
A consequence of QBA is that ads cannot be placed on
pages a priori because it is the query that determines what
ads are to be placed on a page. This is referred to as
dynamic advertising. The query asks ~or a page that has a
~ocus. Ads that are resident in the system are checked to
determine which ads can potentially be placed on the page
- in question. This decision is based on matching the ~ocus
-- 7 --
-
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/195~9
o~ a page with the ~ocus o~ the ad. When not all matching
ads can be placed on a page because o~ space limitations,
the contract en~orcement ~eature o~ the present invention
ensures that the ads that are placed on the page are
consistent with the contracts signed by the system with the
advertiser.
Another consequence o~ QBA is that it must be
determined where to place an advertisement on a page.
Currently, pages on the WWW have a ~ixed a priori agreed
upon area on a page ~or advertising. The present
invention, however, dynamically determines where an
advertisement should be placed. The present invention
permits owners of pages to be ~ree to organize the layouts
o~ their pages. The page owner makes the ~inal
determination o~ where an advertisement should or should
not be placed. Once the page is organized, the page owner
can speci~y where an advertisement can be placed by placing
a special tag ("ad space") on their page. Like the ~ocus
tag, this ad space tag is not visible to the consumer. It
is a directive to the advertising system that the tag
denotes space available ~or advertising, i.e., the ta~ can
be thought o~ as a billboard stating "this space available
~or advertising."
The present invention also provides a download delay-
time advertising ~eature. Most consumers on computernetworks, such as the Internet, experience a delay ~rom the
moment they ask ~or a page to the time the page is
downloaded to their browser. This delay may be caused, ~or
example, by traf~ic congestion on the WWW. This delay time
will be re~erred to as download delay-time.
The present invention uses the download delay-time to
display ads to the consumer. This will be re~erred to as
- 8 -
,
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
down-load delay time advertising. The time that the
consumer would have waited for a page to be downloaded is
utilized to expose the consumer to ads. Once a page (or a
subpart o~ the page) has been downloaded to the consumer's
~ 5 browser and is available to be displayed, the ads are
replaced by the page content. The consumer does not
e~perience a delay due to advertising by the present
invention. Only the preexisting delay time is utilized by
the advertising system.
In summary, the present invention provides a system
and method for advertising on a computer network,
comprising a server containing a plurality o~
advertisements, means for electronically connecting the
server to a computer network, and means ~or selecting and
retrieving an advertisement from the server in response to
a query entered on the network. The selecting means
comprises means for ensuring that a selected advertisement
is relevant to the query. A mixer means is provided for
combining a retrieved advertisement with a content page
returned by the computer network in response to the query.
The mixer means comprises a layout manager means for
computing an optimum layout of a combined page containing
the retrieved advertisement and the content page The
mixer means also comprises a typography manager means for
detecting special tags and HTML rules in the content page
and for determ; n~ ng which part of the content page the
selected advertisement can be displayed on. The content
page is provided by a home page dispatcher, a search
engine, or a generic HTML content provider in response to
the query.
A transaction means is provided for permitting a user
to make a transaction with the advertiser by interacting
_ g _
CA 02240009 l998-06-08
W O 97/21183 P~TnJS96/19S09
with the displayed advertisement. A prime space manager
means is provided for controlling whe~ the advertisements
contained on the server are selected by the selecting
means, the control being based upon respective advertiser
S contracts associated with each o~ the advertisements.
An ad placement means is provided ~or placing new
advertisements on the server, the ad placement means having
means ~or entering an advertiser contract for each
advertisement placed on the server and means for checking a
new advertiser contract ~or consistency with existing
advertiser contracts. A local client means is provided for
displaying a retrieved advertisement only during a download
delay time period in which a user is waiti~g for a content
page to be downloaded in response to the query. A means
15 = ~or refreshiny a displayed advertisement after a
predetermined time period o~ inactivity by the user, and a
means ~or replacing a displayed advertisement with a
downloaded content page as soon as the content page is
received by the client are also provided. The system
includes means ~or calculating a search time estimation for
the ~uery, and means ~or combining a page containing the
search time estimation and a retrieved advertisement. The
system also includes means for det~rm;n;ng a geographic
location of a user, and means for selecting an
advertisement based upon the user's geographic location.
BRIEF DESCRIPTION OF T~E DRL~WINGS
The present invention will become more clearly
appreciated as the disclosure of the present invention is
made with re~erence to the accompanying drawings, wherein:
Fig. 1 is a schematic diagram providing a general
overview o~ the main components of the present invention.
- 10 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
Fig. 2 is a flow chart showing a process of placing
advertisements on content pages provided by yellow page
publishers of a computer network.
Figs. 3A-3D are screen prints showing page views
displayed during various steps in the process o~ Fig. 2.
Fig. 4 is a flow chart showing the process performed
by the layout manager of the present invention.
Fig. 5 is a flow chart showing the process performed
by the parser of the present invention.
Fig. 6 is a flow chart showing the process performed
by the mixer and ad selector o~ the present invention.
Fig. 7 is a ~low chart showing a process of placing
targeted advertisements in online pages provided by a home
page publisher of a computer network.
Figs. 8A-8C are screen prints showing page views
displayed during various steps in the process shown in Fig.
7.
Figs. 9A and 9B are ~low charts showing a billing
system process according to the present invention.
Fig. 10 is a flow chart showing the steps of an ad
placement process according to the present invention.
Fig. 11 is a flow chart showing the steps o~ a page
placement process according to the present invention.
Fig. 12 is a schematic showing the architecture of a
transaction system according to the present invention.
Figs. 13A and 13B are screen prints showing page views
displayed during various steps in a transaction process of
the present invention.
Fig. 14 is a flow chart showing the steps of the
transaction process according to the present invention.
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
Fig. 15 is a diagram chart showing the process
per~ormed by the prime space manager component o~ the
present invention
5 . DE~A TT-~n DESCRIPTIOW OF THE PREFERRED EMBODIMENT
Reference will now be made in detail to a pre~erred
embodiment o~ the invention, an example o~ which is
illustrated in the accompanying drawings.
Fig. 1 provides a general overview or space
architecture o~ the main components o~ the present
invention. The layout manager 10 is primarily responsible
~or the computation o~ the layout o~ a page to be displayed
to a client. Other modules o~ the system compute the
necessary data that is to be displayed, as described below.
The layout manager 10 then accepts this data ~rom the
other modules and computes the optimum layout for the
display.
The layout manager 10 uses two sub-components to
determine the optimum layout; a rule base and a layout data
base within the layout manager (collectively shown as the
layout rules component 11 in Fig. 1). The layout data base
contains a collection o~ templates that have been
prede~ined and stored in the layout data base. The rule
base contains a collection o~ rules de~ined by the user or
by the placer o~ the layout manager to ascertain which
layout templates are best under what set o~ conditions.
When the layout manager 10 receives the data to display, it
invokes various rules in the layout rules to ~igure out
which rule to trigger and, hence, decides on one layout as
being the best under the present set o~ conditions.
The variables used in the rules are the amount o~ data
that is to be displayed, the kind o~ data that is to be
- 12 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
displayed, the amount of text, the amount o~ advertising
material, and the size o~ the various maps and multi-media
icons that are to be displayed. Based on these variables,
the rules are checked and one or more rules are picked as
delineating the best layout that can be ~ound. The layout
manager 10 then arbitrarily picks one o~ the rules that it
thinks are the best and picks that layout, inserts the data
given to it in the layout template, and gives the ~inal
product to the client to be displayed.
The variables that are expressed in the rules are
based on a number o~ parameters including the size o~ the
text, the amount o~ text, the size of the maps, the size of
the images, and the size of the advertisement. In
principle, there is no limit as to the number o~ parameters
that one can achieve using the layout manager 10. The
rules are pre~erably expressed in a programming language
general enough to take any other parameters that one may
desire to ~urnish.
The layout rules are constructed based on various
parameters. The layout rules are then checked and used to
pinpoint the exact template to be used ~or a certain kind
o~ data situation. The template is then ~illed in by the
layout manager 10 to provide a display to the client.
Next, the segmenter 12 will be described. The
segmenter 12 is responsible ~or analyzing an HTML page and
for extracting the relevant data from the HTML page. The
purpose o~ the segmenter 12 is that, i~ the system is given
a page constructed by another component or by some other
content provider, the segmenter 12 will try to ~ind
reasonable places within that page where a certain
advertisement could be inserted dynamically.
CA 02240009 1998-06-08
W O 97~1183 PCT~US96/19509
The segmenter 12 uses various rules ~or ~inding
advertising space within a page, and for preventing the
essential layout o~ the page ~rom being disturbed. In
particular, the segmenter 12 looks for certain special tags
inserted by the designer o~ the HTML page and replaces
those special tags with advertisements or other types of
in~ormation that it has been given The segmenter 12 then
looks at the page, decides where to insert ads, and
provides that in~ormation to the layout manager 10.
In most instances, the typography manager 14 is the
main input device to the layout manager 10. One exception
to this will be described later. The typography manager
14's role is to '~render" the page. By rendering the page
it is meant that the typography manager 14 takes various
15 : kinds o~ input that has to go on a page and decides which
part o~ the information has to go on the page and which
part o~ the information could in ~act be deleted. Thus,
the typoyraphy manager 14 is similar in ~unction to a
t~pographer in a traditional publishing situation.
The t~pography manager 14 has the ~inal say in what
data gets sent to the layout manager 10. The typography
manager 14 also detects special tags and special HTML rules
that tell it where the markups of the HTML page are
supposed to happen. Ultimately, the layout manager 10 and
the typography manager 14 collaborate on coming up with a
page. This page in its ~inal ~orm is then passed to the
gate 15.
The gate 15 trans~ers a page ~rom the system o~ the
present invention to the client. The gate 15, there~ore,
provides the gate between the client and the server. The
gate 15 gives the page that it wants to display to the WWW
- 14 -
CA 02240009 l998-06-08
W O 97/21183 PCT~US96/19509
Daemon 16 and the Daemon interacts in turn with the client
17 on the user's side.
The above description has explained how the layout
manager 10, the segmenter 12, the typography manager 14,
and the gate 15 operate. Before describing in detail the
r~.-in;ng col-,pon~nts o~ ~he system, an exampIe flow of a
request through the system will be explained.
Initially, a user requests a particular piece of
information through one of the clients 17. The user's
request is given to the WWW Daemon 16, which passes the
information to the gate 15. The gate 15 at this point
decides what piece of information is being requested by the
user and finds other relevant pieces of information that
can be commingled with wha~ the user has asked. The user,
for example, might ask the system to see certain car
dealers, to find a phone number of a car dealer, or to get
a page of a particular magazine.
The gate 15 at this point gives the request to the
matching rule engine 18 ("MRE"). The purpose of the MRE 18
is to look at the content of the user's query and to find a
category within its active index SIC 19 that matches the
same type. If the user has asked for car dealers, the MRE
18 invokes its rules to determine that car dealers are part
of a class of things relating to transportation. Based on
the classification determined by the MRE 18, the system now
knows that the user is asking about cars or about
transportation or about whatever else that the user might
be interested in.
The MRE 18 at this point then returns to the gate 15
the category index of the user's query. If the user had
asked about cars or about ~amily sedans or about sports
~ cars, at this point the MRE 18 would have figured out that
- 15 -
CA 02240009 1998-06-08
W O 97/21183 PCTAUS96/19509
the user's interest ~alls into a certain category. sased
on the user's interest category, the system then retrieves
the advertisements that are relevant to that category.
Thus, the purpose of the MRE 18 is to fi~ure out what the
user reguested, to place the user's reguest in a category
o~ a classification system (i.e., the active index SIC 19)
and, based on that classification, to retrieve relevant
advertisements. At this point there may be several
hundred related advertisements retrieved ~rom the category
containing the user's request. This creates a problem in
that there will be many more advertisements related to the
user~s request than can possibly be shown to the user on
the first page o~ in~ormation. At this point, the prime
space manager 20 comes into play. The purpose of the prime
15 - space manager 20 is to prioritize the advertisements that
are to be shown to the user.
For example, i~ there is only room for five
advertisements and the MRE 18 returns a list o~ 500
possible advertisements to show, the system must determine
which five o~ the ads to show. The operation of the prime
space manager 20 is based on a set of contracts that were
accepted when the advertisers placed their advertisements
with the system. The system supports the ~ollowing five
basic types of contracts:
1. Ratio-based: The ad will be shown in prime space
no less than a certain percentage of the times a
relevant guery is made by a searcher.
2. Dependent: Ad A is to be shown with a
predetermined probability when ad B is shown in
prime space.
3. Exclusive or Competitive: Ad A is never to be
shown in prime space when ad B is shown.
- 16 -
CA 02240009 1998-06-08
WO 97/21183 PCTAUS96/19509
4. Story: An ad consisting of several sub-ads will
be shown in prime space in a particular sequence
to a consumer.
5. Frequency-based: The ad will be shown in prime
space a certain number of times in a given time
period (e.g., 100 times per month).
Additionally, the contracts may also specify the type
of the layout used to mix ads together with the data. This
includes the layout types, and so forth. The various
contracts used by the system will now be discussed in more
detail
The ratio-based contracts are used where an advertiser
wants the advertisement to be displayed a certain
percentage o~ the time in prime space. In other words,
when a query is received that is related to the business of
the advertiser, the advertiser is guaranteed that its
advertisement will be on the first screen of in~ormation
displayed to the user a certain percentage of the time
(e.g., 15% of the time). This percentage is called the
coverage guarantee. The ratio-based contract provides a
coverage guarantee to the advertiser that its advertisement
will be displayed X% of the time for every relevant query.
This guarantee is probablistic in nature, so that over the
long run of the system, the probability will converge to
the percentage that the advertiser has requested.
The second kind of contract that the system supports
is re~erred to as a dependent contract. The dependent
contract guarantees that one advertiser's ad can be shown
in conjunction with another advertiser's ad on the same
screen. For example, a travel destination advertisement
(e.g., "Come to the B~h~?m~ can be shown on the :Eirst
~ screen of information together with a credit card
- 17 -
CA 02240009 1998-06-OX
PCT~US96/19509
W O 97/21183
advertisement (e.g., "Pay for your ticket through VISA").
With this type o~ contract, the system can support
contracts that satisfy the needs of two or more advertisers
at the same time.
The third type of contact supported by the system is
called an exclusive or competitive contract. This type of
contract can be used to guarantee that an advertiser's ad
is not shown at the same time or on the same page as a
competitor's advertisement. For example, a beverage
manufacturer (e.g., Coca-~ola) can prevent a competing
beverage manufacturer's (e.g., Pepsi's~ ads to be shown at
the same time as its own ads and vice versa.
The ~ourth kind o~ contract is called a story
contract. This type of contract is used to guarantee an
advertising package in which a sequence of two or more ads
are shown together. The ads can be displayed so that the
user sees a first part of the advertisement, then sees a
second part of the ad, and then sees a third part of the ad
and so on. For e~ample, an advertisement for co~ee might
consist of a picture on a first page showing somebody
drinking a cup o~ coffee; a picture on a second page
showing them putting the coffee cup away; and a picture on
a third page identifying the name of the advertiser's
product (e.g., "Maxwell House makes a good cup of cof~ee").
Thus, the story contract guarantees that an
advertiser~s ads will be shown in the form of a story. The
story contract is desirable where a group of ads must be
shown together in a particular order to make sense.
The fifth kind of contract is the frequency-based
contract. This contract is used where the advertiser wants
to guarantee that its advertisement will be shown a certain
- 18 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
number of times over a given time period (e.g., 100 times
per week).
Several different combinations of the above-described
types of contracts can also be used. For example, an
~ 5 advertiser can enter a story contract which also guarantees
that its advertisement will not be shown at the same time
as its competitors ads are shown, that its advertisement
will be shown at the same time that a related advertisement
is shown, and that its advertisement will be shown in prime
space a certain percentage o~ the time.
The prime space manager 20 has the responsibility of
det~m,n;ng all the possible advertisements that can be
shown in conjunction with the information requested by the
user. The prime space manager 20 then decides which ads to
show based on the particular contracts that have been
signed. If a contract has already been entered with an
advertiser's competitor, the prime space manager 20 will
make sure that it can in fact satisfy the new contract with
the advertiser. Thus, the prime space manager 20
dynamically makes a decision of which advertisements to
show given the amount and the number of advertisements that
it can possibly show The end result of the prime space
manager 20's computation is that the system knows exactly
which advertisements can and will be shown to the user.
These advertisements are then given to the gate 15.
The gate 15 at this point gives the ads to the typography
manager 14, and the typography manager 14 determines how
best to display the in~ormation The page information then
comes back to the gate 15 and is forwarded to the client
- 30 17. In the above description of the present
invention, the advertisement contracts, the active index
SIC 19, the layout rules 11, the segmenter 12, the segment
- 19
CA 02240009 1998-06-08
W O 97~1183 PCTrUS96/19S09
rules 13, the layout manager 10, and the typography manager
14 have been explained.
During the computation of the advertisements and all
the other computations that the system o~ the present
invention per~orms, a logging module 22 of the system
per~orms extensive logging of what the user has asked, what
advertisements were shown, how long the advertisements were
shown, and which advertisements were shown to which user.
The logging module 22 then stores these logs in a SYS logs
database 23. Various scanned reports can be produced and
de~ined using the information in the SYS logs database 23.
A local client 24 of the present invention provides a
download delay-time advertising feature. Download delay
time re~ers to the delay experienced by most users of
computer networks from the moment a page is requested to
the time the page is downloaded to their browser. The
download delay-time advertising feature utilizes the time
that the consumer would have waited ~or a page to be
downloaded to expose the consumer to ads. Once a page (or
a subpart of the page) has been downloaded to the
consumer's browser and is available to be displayed, the
ads are replaced by the page content.
In most cases, when a user asks for a page there is a
considerable download delay time. The user must wait ~or
the page after the request ~or a few seconds or, in certain
cases, a ~ew minutes before the page is ~inally downloaded
by the network. The present invention uses this delay time
to show advertisements, while taking care that the delay
time of the user is not increased by showing the ad. Thus,
the on-y time an advertisement is displayed is the time
that the user would have had to wait anyway. While the
- 20 -
CA 02240009 1998-06-OX
W O 97/21183 PCT~US96/19509
user waits ~or the page, the user can view the
advertisements on the local client 24.
The in~ormation brokers or content providers shown in
Fig. 1 include a home page dispatcher 25, a search engine
INFORMIX 26, and a generic HTML 27. For purposes of the
present invention, it is assumed that there are three broad
classes o~ publishers that can utilize the advertising
~eatures o~ the present invention. A "publisher~' can
include virtually anyone that provides content to the
network. For example, anyone who is a home page owner is a
publisher in the category shown as Generic HTML 27. A
second kind of publisher is the search engine publi~her 26,
which includes phone company yellow page providers, such as
NYNEX. And a third kind o~ publisher is the so-called home
page dispatchers, which include traditional magazines and
newspapers, such as Business Week.
The present invention distinguishes between these
three types o~ publishers. I~ the publisher is a home page
dispatcher 25, the publisher provides its own content and
intersperses the content with certain special tags
indicating where ads can and cannot be placed and
indicating where the ~ocus of the content is about certain
topics. These special tags are then used to trigger
certain actions in the system o~ the present invention
relating to the type of content contained on the page and
the kinds o~ advertisements that can be placed on the page.
The second kind o~ publisher that the present
invention is used with is the search engine publisher 26.
Currently, there are many companies on the WWW that permit
users to query their database and then return a set o~
answers ~rom the database to the user. For example, a
telephone company may have a site that allows a user to
- 21 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
obtain a set o~ phone numbers and business names ~or a
particular type o~ business (i.e., a yellow page
directory).
For purposes of the present invention, the search
engine publisher 26 is distinguished ~rom the home page
dispatcher 25 in the sense that the content returned by the
search engine publisher 26 does not contain any special
tags or meta comments put in by the publisher to de~ine the
layout of the content and the ads. In this case, the
10 = layout manager 10 o~ the present invention computes the
optimum layout based upon the rules and layout templates,
as described above. The ~inal result, there~ore, is that
output is taken from the search engine publisher 26,
adorned with certain relevant advertisements, and then
shown to the users.
The third kind o~ publisher, the generic HTML
publisher 27, includes those publishers that the present
invention assumes are people who have designed their own
home page, perhaps taking great care to provide a desired
appearance. These publishers will probably not have
inserted any special tags or meta comments into their home
page to guide the advertising system o~ the present
invention. In this case, the system of the present
invention can either try to ~ind a space in the home page
-- that it thinks is reasonable without violating the desired
appearance of the page, or it can insert the advertisement
be~ore or a~ter the page. That is, i~ the segmenter 12
cannot find a suitable place within the page that the
generic HTML publisher 27 has already designed, it will
place the advertisement on the proceeding or the ~ollowing
page. This is more likely to occur i~ the owner o~ the
page has not provided any special tags or meta comments, or
- 22 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
if copyright concerns prevent the insertion of a certain
advertisement within the page.
In summary, the present invention partitions the
publishers (i.e, the information brokers) into three~ 5 categories: the home page dispatchers 25, the search engine
publishers 26, and the generic HTML home page providers 27.
The distinction between the three is that the home page
dispatchers 25 intersperse their content with special tags
or meta comments which helps the present invention in
det~rmin;ng where to place the advertisements and what kind
of advertisements to place, the search engine kind of
publishers 26 return unadorned results of queries and the
present invention is free to reformat and relay out the set
of answers, and the generic HTML home page publishers 27
are publishers that have meticulously crafted their home
pages, usually without special tags or meta comments, so
that no guidance is provided to determine an appropriate
space for placing an ad.
The segmenter 12, which is the module of the present
invention whose responsibility is to find a place somewhere
on a generic HTML page to place an advertisement, may not
succeed in finding a space on a generic HTML home page. In
this case, it will either place the advertisement on a
proceeding or a following page. Most, if not all, of the
publishers on the WWW will fall into one or more of these
three categories.
In Fig. 1, the acronym LA refers to List of Ads, Q
refers to the user's query, CGI is a standard WWW
abbreviation for "common gateway interface,~ HTML is a
st~n~d abbreviation for hypertext markup language, and Ly
is the list from the layout manager 10 to the typography
- 23 -
CA 02240009 1998-06-08
W O 97/21183 PCTAJS96/19S09
manager 14 that indicates a list of pages that have to be
displayed.
Referring to Fig. 2, a flow chart is provided that
describes the main flow of the process o~ placing ads on
content pages provided by yellow page publishers, in
accordance with the present invention. The process begins
at START 30 when the client provides a query to the system.
For purposes of illustration, the query depicted is a
yellow page query in which a user requests some item of
interest, and the publisher is a yellow page publisher
(please re~er to the previous discussion for a description
of the three kinds of publishers).
For example, the user may submit a query form asking
for a listing of all car dealers in Morristown, New Jersey.
- This query form is evaluated by the box 31 entitled ~P
QUERY FORM. The purpose o~ this evaluation is to determine
the type of the query (e.g., is the user interested in
cars, a particular geographic region, etc.).
In using a yellow page publisher there are two broad
distinctions for a query. A client may be asking for a
certain category of listings, or the client may be asking
for a particular vendor. For example, the user could ask
for car dealers in Morristown, NJ (i.e., a category of
listings), or the user could ask for Morristown BMW located
on South Street in Morristown, NJ (i.e., a particular
vendor). The system determines which of the two types of
queries or searches the user has made, as illustrated by
box 32 in Fig. 2. If the query is for a certain category,
the process will go to the left hand side of the flow chart
of Fig. 2, and if the query is for a certain vendor, the
process will go to the right h,~d side of the flow chart of
- 24 -
_ _ _
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
Fig. 2. The left hand side of the flow chart will be
explained first.
After determ;nlng the type of query, the category
search engine 33 next determines which category best fits
the user's request. The user may have asked for "car," but
the category in the yellow page provider's index may in
fact say "automobile." Or, the user may have asked for
"spectacles," and the category in the yellow page provider
may be called "optician." The matching of these variations
o~ terms is performed by the category search engine 33.
Once it has been determined which category the user's
request falls into, the advertisement selection process
comes into play with the ad selector 34. The ad selector
34 determines what advertisements are best suited to be
mixed in with what the user has requested. The content
from the category search engine 33 and the ad(s) from the
ad selector 34 are then given to a mixer 35. The mixer 35
functions to mix the content coming from the search engine
with the ad(s) selected by the ad selector 34. The result
is the creation o~ a page that is of interest to the user.
I~ the user's category was about cars, at this point
the ad selector 34 would have presumably found
advertisements related to cars and displayed these ads at
step 36 to the user. The user at this point can select one
or more of the listed or advertised car dealers. This
again results in more advertisements being selected by the
ad selector 34, as well as the accessing o~ a vendor search
engine 37 provided by the yellow page publisher, and a new
page being shown to the user.
Referring to the right hand side of Fig. 2, i~ the
user requests a particular vendor, the system will first do
~ a search time estimation 38 to figure how long it will take
- 25 -
CA 02240009 1998-06-08
WO 97/21183 PCT~US96/19509
to ~ind the piece of information requested by the user. At
the same time, the ad selector 34 will perform a search for
the advertisements that are to be shown to the user. As
soon as the relevant ads are found by the ad selector 34,
the ads are mixed with the search time estimation
information and both are displayed to the user. At this
point 40 in the process, the user is asked ~or a
confirmation of whether to continue with the requested
search given the estimated search time. Upon receiving
confirmation from the user, the ad selector 34 will again
be accessed, as will be the vendor search engine 41. The
first set o~ ads returned by the ad selector will continue
to be displayed to the user ~or viewing until the search
results from the vendor search engine 41 are available.
15 _ When the vender search engine 41 completes the search,
it returns the search results to the mixer 35. Similarly,
the ad selector 34 returns a second set o~ ads to the mixer
35. The mixer 35 mixes the ads with the content provided
by the vendor search engine 41 and forwards the combined
~ page to the page display 42.
The result o~ this process is that a yellow page
inquiry posed by the user is categorized either as a
category search or a vendor search. In both cases, the
type of the query is matched with a certain category o~
ads, the search results and the ads are mixed, and a page
is constructed and shown to the user. Upon ~urther input
from the user, the system selects and mixes a second set of
ads with the content page o~ the publisher, and another
page containing ads is constructed and shown to the user.
The "focus" arrows 43 shown in Fig. 2 indicate that a
certain ~ocus is associated with each category. The ~uery
may have been directed to a category o~ listings or a
- 26 -
-
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
particular vendor. In both cases there is a "focus"
associated with the content of the query (e.g.,
automobiles, physicians, lawyers, etc.). In addition,
there may be a focus associated with the geographic
location of the user to permit advertisers to target users
in particular geographic regions. The focus process plays
a major part in the present invention. No advertisements
are shown unless it can be determined that the
advertisements are in some way focused or related to the
content of what the user requested.
Referri~g to Figs. 3A-3D, the page views displayed to
the user during the process of Fig. 2 will be described.
Figs. 3A-3D show four ~orm views labeled successively Form#
YP_1, Form# YP_2, Form# YP_3, and Form~ YP_4. These form
views correspond to the re~erences made to the same form
numbers in the flow chart of Fig. 2.
The user is first presented with a user's screen that
looks like Form# YP_1 and the user is prompted to type in a
query. For example, the user can type in a query ~or car
dealers in Morristown, NJ. This query will result in a
search type as previously described, either as a category
or a vendor. In fact, the user can pick one or the other
by selecting the appropriate box on Form~ YP_~. At this
point, the system knows whether the search type is category
or vendor and, because the user has typed in car dealers,
the system knows the focus.
At this point, if the search type is vendor, the
system will show a screen that looks like Form# YP_2. This
screen in~orms the user that it will take approximately 30~ 30 seconds for the system to respond to the user and asks the
user whether this is okay. If the user wants to proceed,
- 27 -
CA 02240009 l998-06-08
W O 97/21183 PCT~US96/19509
the user clicks on the box la~eled "Search it now" and the
system begins the search.
If the search type is category, the system displays a
screen that looks like Form~ YP_3. This Form~ YP_3 shows a
list of categories under the heading of car dealers. The
user is then asked to make a selection o~ one o~ these
categories. Simultaneously, the system goes into the ad
selection mode and selects and places ads on the Form# YP_3
that is being displayed to the user. In this case the
advertisement shown on Form# YP_3 is the Bellcore logo.
The user then selects one o~ the subcategories being
displayed and clicks on the box "Search it now.~'
The system next displays a screen that looks like
Form# YP_4. The ads placed on this Form# YP_4 have been
selected by the ad selector 34, and the listings on the
form have been searched and retrieved by the vendor DB
entries search engine 41.
In summary, the general process ~or a yellow page
search request in the system is that first the user states
a ~uery, the result of the ~uery is a set of possible
categories that the user wants to see. The system then
makes a choice of one category from this list o~ categories
and shows the relevant providers in that category to the
user. When the user states a query and the system displays
to the user a list of ca~egories, certain advertisements
are shown to the user as well. This is the top half of the
~low chart o~ Fig. 2 where the category search engine 33 or
search time estimator 38 and the ad selector 34 provide the
two components to the mixer 35 and the mixer 35 comes up
with a page cont~;n~ng both an advertisement and a list o~
categories or the search time estimation of how long it
will take.
- 2~ -
_
CA 02240009 l998-06-08
W O 97/21183 PCTnUS96/19509
If a user requested a category, the user will be shown
advertisements and a list o~ categories that relate to the
user's query. If the user requested a particular vendor,
the user will be shown advertisements related to the focus
of the user's query and an estimation of how long it will
take ~or the system to process the query. In both cases,
the user has been shown advertisements and some part of the
information and then asked to make a ~urther choice. Once
the user makes the further choice, the system again tries
to find what the user requested plus what advertisements to
show as a part of this process. Thus, whenever the user
asks the system to do something, the system will do what
the user asks, but at the same time will find
advertisements that it can mix in with what the user
requested.
Although the flow chart o~ Fig. 2 illustrates the
present invention only in conjunction with a yellow page
publisher, similar processes are used with other types of
publishers. The process of the present invention ~or
placing ads with home page providers is described below in
conjunction with the ~low chart of Fig. 7.
Re~erring now to Fig 4, the layout manager 10 of the
present invention will be described in ~urther detail. At
step 50, the layout manager 10 is given the collection of
data to be displayed. The layout manager 10 has a
collection of rules that it evaluates so that it can return
the best layout ~or each page. When the layout manager 10
receives data it reads the parameters o~ the data for each
rule (step 51~ and expands on the expand meta template 53.
There are two main components o~ the layout manager
10, as previously discussed -- a layout data base and a
layout rule base. The layout rules describe certain
- 29 -
CA 02240009 l998-06-08
W O 97/21183 PCT~US96/19509
parameters that can be used to determine the best layout to
use under a given set o~ situations. The layout data base
is a collection of templates that can be thought of as
forms that need to be filled out with certain kinds of
5 ~ data.
When the layout manager 10 is given a piece of data,
it uses the rules to determine which templates to use.
Speci~ically, the layout manager 10 evaluates each and
every rule in its rule base to figure out which rule is the
best for a given piece of data. The rules are evaluated at
step 54 by calculating a meta and a target function cost.
The meta template is the template that describes what the
layout is about. For example, the template may provide
that there are only five places ~or advertisements in a
particular layout.
There is a cost associated with each kind of layout.
The basic problem that the layout manager lD is faced with
is that are a certain number of advertisements to show and
there is a certain amount of user-requested data that has
to be shown. This creates a spectrum of objective versus
subjective content that has to be e~aluated. That is, it
must be determined how much subjective content to provide
and how much objective content to provide. If the
publisher is a yellow page publisher, the layout manager 10
must decide how many telephone listings to display and how
much o~ the page to ~ill with advertisements. The system
could, for example, display only three telephone listings
and fill the rest of the page with advertisements, or the
sys~em could display twenty telephone listings and only one
ad. Each template in the layout database has a set o~ meta
attributes associated therewith indicating the number of
advertisements that can be displayed, the amount o~ content
- 30 -
-
CA 02240009 1998-06-08
W O 97/21183 PCTAUS96/19509
to be displayed, and the cost function associated with the
template.
In summary, the layout manager 10 picks up a rule in
the data base, calculates the cost function for each
template and stores the template with the m; n 1 mllm cost in a
safe place (step 55). At the end of this computation the
layout manager 10 succeeds in finding the m; nl mum cost
layout within its data base that it can use for the current
data account. It then picks the m;n;mum cost layout as the
best layout and returns the best layout (step 52) to the
typography manager 14 for display to the user.
Re~erring to Fig. 5, a flow chart of a parser 60 of
the present invention will be described. The purpose of
the parser 60 is to interpret the meta comments and meta
tags inserted on the publishers' pages. As described
above, these are generally pages constructed by magazine or
newspaper publishers that have provided special tags in
their content for the present system to interpret in a
special way. These pages are referred to in Fig. 5 as
enhanced HTML or E_HTML 61.
The parser 60 ~irst searches for special tags (step
62) in the input E_HTML. There are two kinds of special
tags: tags for focus and tags ~or advertisement space.
Tags ~or focus are tags that tell the system what the focus
of the page is or what the context or content of the page
is about. For example, a focus tag might indicate that the
page is about sports cars, cooking, or travel destinations
in the Caribbean. The advertisement space tags, on the
other hand, indicate a space on the page that is so many
pixels by so many pixels and that can be used for
advertisements. The parser 60 searches for these special
tags and identifies the tag name as either a focus or an
- 31 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/1950~
advertiseme~t tag (step 63). If the parser 60 cannot ~ind
any special tags, it simply returns ~rom where it was
called.
I~ the parser 6Q ~inds a ~ocus kind o~ tag, it
5 = extracts and stores the focus words (step 64). I~ the
parser 60 finds an advertisement kind o~ tag, it extracts
and stores the size value (step 65). In both cases, the
process returns the ~ocus and ads information to another
module in the system (step 67) after reaching the end of
the paye (EOF) 66.
Re~erring to Fig. 6, a process flow of the mixer and
ad selector will be described. The purpose o~ the mixer 35
(as previously described in reference to Fig. 2) is to take
publishers' content and advertisements and combine them
together so that the content and the advertisements are
mixed on the same page.
In Fig. 6, the mixer 35 is shown receiving two inputs
from the publishers: data 50 ~which is the content) and E-
HTML 61 (which contains the special tags). The layout
manager 10 and parser 60 both ~orm a part of the mixer 35.
The data 50 is input to the layout manager 10, and the
E_HTML 61 is input to the E_HTML parser 60, as previously
discussed. soth o~ these sub-modules then determine where
the advertisements can be placed on the publisher's page.
25 ~ The advertisement list is then input ~rom the ad
selector 34. The ad selector 34 receives a ~ocus input 43,
retrieves relevant ads (step 70), and creates the
advertisement list using the prime space manager 20 ~step
71). These advertisements are then placed in the parser 60
~ and the layout manager 10 (step 72), as described above.
The mixer 35 then logs all the essential billing and other
user in~ormation (step 73) ~or keeping track o~ the
- 32 -
CA 02240009 1998-06-08
W O 97t21183 PCT~US96/19509
system's placement of an advertiser's ad. At this point, a
refresh tag is inserted (step 74) and the system outputs an
HTML page (step 75).
The HTML page output from the mixer 35 has no special
tags and can be displayed by any client that can understand
HTML. The E_HTML 61 is peculiar to the present invention.
The HTML 75 is the standard HTML used on computer
networks. The E_HTML ~1 is peculiar in the sense that it
has the special tags for advertisements and focus, as
discussed above.
The refresh tag inserted at step 74 is a special tag
inserted into every page that is to be displayed. The
purpose of this tag is to refresh the page if the user does
not take any action for a predetermined period of time.
The system will refresh and show a new advertisement in ~he
ad space, while leaving the rest of the page the same.
Thus, while the user is viewing the page, the system will
not show the same advertisements for more than a
predetermined period of time so as to take advantage of the
user~s limited attention span. This permits the system to
effectively run as many ads as possible.
For example, while a user is reading an online
magazine page, the advertisement may change every so often
as the user is viewing the same page. If the user is
making changes to the page or is going back and forth on
the page, then the advertisements will not be changed by
the re~resh tag function. The timer for the refresh tag
function can be specified by the advertiser or determined
by the system.
As described above, there are ~ive basic types of
contracts supported by this system. One type of contract,
- the ratio-based contract, requires that a certain
- 33 -
CA 02240009 1998-06-08
W O 97~1183 PCT~US96/19509
advertisement has to be shown on the first screen o~
information or the prime space screen o~ in~ormation ~or a
certain percentage o~ the time. In order to satisfy this
contract, the system has to be able to refresh the prime
space screen Otherwise, once an advertisement was placed
on a user's screen it would remain on the screen the entire
time that the user is viewing the screen. The insert
re~resh tag ~unction 74 ensures that the user will be shown
new advertisements and not be subjected to the same
advertisement for any great length o~ time.
Re~erring to Fig. 7, a ~low chart o~ the present
invention as used with a home page provider will be
described. The ~low chart o~ Fig. 7 is somewhat similar to
the ~low chart of Fig. 2. However, while the ~low chart of
Fig. 2 shows the process used with yellow page publishers,
the flow chart of Fig. 7 shows the process used with home
page pro~ider publishers. As described above, home page
providers are publishers that have provided special tags
and special focus and advertisement space tags in the meta
content supplied to the present system.
To start (step 80), the user enters a query. For
example, the user may enter restaurants or cars as a query.
The query has a ~ocus, as described above. The system
determines what the ~ocus is and, as described above, the
system provides the user with a list of categories that
relate to the query. For example, i~ the user requests
restaurants, the user might be shown a list of restaurant
types, such as Chinese, American, French, Italian, and so
forth. The guery entered by the user is e~aluated by a
query form manager (step 81) to determine the ~ocus of the
query.
- 34 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
The screen ("Form# 1") illustrated in Fig. 8A is the
graphical inter~ace used to enter the ~uery. Form# 1 shows
~ the space (immediately following the phrase "SEARCH FOR")
where the user types in the query (in this case "car").~ 5 The result of the query is a list of relevant subcategories
for cars, as shown in Fig. 8B ("Form# 2").
Referring again to Fig. 7, the category search engine
33 generates a number of subcategories of the ~uery (e.g.,
cars), and the ad selector 34 (Fig. 7) finds certain
advertisements that are related to cars. The mixer 35
mixes these two screens to create the display shown as
Form# 2 in Fig. 8B (step 82).
At this point (step 82) the user is asked to make a
further selection. That is, the user is asked to pick one
or more of the categories displayed in Form# 2 so that the
system will provide more specific information. The user
may pick, for example, "new and used car dealers retail" by
highlighting that item and clicking on the submit button.
Upon clicking the submit button, the content provider
search engine 83 is accessed. At the same time the ad
selector 34 is directed to find appropriate advertisements
for the category "new and used car dealers retail."
The content provider search engine 83 and the ad
selector 34 then return their respective outputs to the
mixer 35. The mixer 35 then mixes the outputs and produces
a list of matching content providers plus the
advertisements (step 84). The combined display at this
point is shown as Form# 3 in Fig. 8C. Form# 3 shows a list
of different car dealers in the center of the display, and
five advertisements along both sides of the display.
The user is then further asked to make a selection of
~ a particular dealer (e.g., a Mazda 626 dealer or a Ford
- 35 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
Mustang dealer) that the user wants to visit. The user
makes the choice, and the cholce o~ the user is given to
the content provider dispatcher 85 and the ad selector 34.
As the content provider dispatcher 85 is retrieving the
requested home page, the ad selector 34 again ~inds an
appropriate advertisement based on the user's request.
For example, the user can pick a Mazda 626 dealer by
clicking on Mazda 626. As the page ~or a Mazda 626 dealer
is being retrieved, the ad selector 34 ~inds advertisements
that can be inserted on this page. There may or may not be
advertising space on the home page ~or the Mazda 626
dealer.
I~ there are no spaces on the home paae ~or the system to
place ads, the system will either insert the ads be~ore or
_ a~ter the page, or the system may decide not to place any
advertisements at all. In any case, for any home pages
requested, the ad selector 34 will attempt to ~ind suitable
advertisements and give these ads to the mixer 35, and the
mixer 35 at that point will display the content provider's
home page with or without ads.
In summary, Figs. 8A-8C show three screen displays
re~erred to in Fig. 7 as Form# 1, Form# 2 and Form# 3,
respectively. Form# 1 is the ~irst screen that the user
sees and in which the user is expected to type in a general
query in the typeable space. This results in a second
screen (Form# 2) where the user is asked to make a choice
~rom a list o~ categories. After choosing ~rom the list of
categories in the second screen, a third screen (Form# 3)
is shown to the user ~rom which the user makes a choice
~rom a list o~ subcategories. The present invention uses
these three screens also to show ads related to the user's
re~uests. Form# 1 shows two ads ~or the owner o~ the
- 36 -
CA 02240009 l998-06-08
W O 97/21183 PCT~US96/19509
service provider (e.g., Bellcore in this case). Form# 2
shows advertisements related to cars because the user typed
in cars. Form# 3 shows more car advertisements relating to
particular makes of cars because the user asked for retail
car dealers.
Referring to Figs. 9A and 9B, a description o~ the
billing system o~ the present invention will be provided.
Figs. 9A and 9B show two submodules of the system called
the info bank and ad auditing. The purpose o~ these two
modules is to construct log reports of various usages o~
the present invention.
Fig. 9A shows the process ~low for the info bank
submodule 90. The purpose o~ the in~o bank submodule 90 is
to log certain kinds of in~ormation during a particular
client's session. The logged information is then used to
provide advertisers with a description o~ what
advertisements have been shown, what the user has bought
after seeing an ad, and so ~orth. Thus, the in~o bank
submodule provides an in~ormation bank to show advertisers
who has been accessing the system and how successful the
ads have been.
The screen for the relevant module contains a link
called the info bank which the user can select. When the
user clicks on the info bank link, the user is shown the
start 91 of the info bank submodule. At this point the
user is asked ~or authentication in~ormation (step 92),
such as the user's name and personal identi~ication number
~PIN). The system then goes into the authentication mode
93 and veri~ies whether the user ID and PIN number typed in
are valid. If the authentication is successful, the system
then searches the transaction log and filter (step 94) and
~ pulls up the appropriate log re~uested by the user. The
- 37 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
user can ask to see all transactions per~ormed by the
client or all o~ the things o~ a certain type that the user
has bought. A report o~ the results (step 95) is
automatically produced ~or the client and displayed.
The submodule ~or ad auditing 96 has a similar purpose
to the in~o bank submodule. With the ad auditor, an
advertiser that has placed an advertisement with the system
is able to go lnto the system at any point in time and ~ind
out who has seen his ad, what was the content of the ~uery
10 ~ when the advertisement was displayed, how many times has
the advertisement been displayed, and so forth. The
authentication and other process steps are similar to the
corresponding steps of the in~o bank submodule 90.
More speci~ically, in order to use the ad auditing
submodule 96 the advertiser is shown a screen with a link
~or ad auditing. The user clicks on the ad auditing link
and is led into the start 97 o~ the ad auditing module.
The advertiser is then asked to type in authentication
in~ormation (step 98), which consists o~ the user name
~ollowed by a PIN number. If the PIN and the user name
check out and are authenticated by the authentication step
99, the user is then asked to tell the system which
advertisement or which subset o~ advertisements they want
to verify or audit (step 100). Once the user specifies the
= advertisement by name or by browsing all the advertisements
in the system and clicking on the ones that the user wants
to get a report on, the system generates a report (step
101), which is a log of who has seen the ad, what machine
they were using, what time and for how long the
advertisement was displayed, and other desired in~ormation.
All the log information accessed by the info bank and
ad auditing submodules is logged in a single database 23
- 38 -
-
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
(Fig. 1). Whether the user is looking for auditing
information, transactions, things that the user has bought,
or user demographics, the information is all in the same
database. However, when a user uses the info bank
submodule 90, the user is interested in only certain
things, as described above. But when the user uses the ad
auditing submodule 96, the user is interested in other
things. Therefore, the reports that are produced by the
info bank and ad auditing submodules contain different
data. The database is filtered and only the items of
interest for a certain report are retained so that the rest
of the database need not be used.
Referring to Fig. 10, the flow of an ad placement
process 110 according to the present invention will be
described. The purpose of ad placement is to allow
advertisers to enter their advertisements into the system.
For entering an ad, the system provides a screen that is
shown to the user asking whether the user wants to enter an
ad. If the user indicates yes by clicking on that
particular choice, the system enters the start 111 o~ the
ad placement mode. At this point the system asks the user
for the focus (step 112). The advertiser may say, for
example, that he is in the car business, the car washing
business, or that he is a physician, a lawyer or whatever
other category name that he wants to give. The user is
also asked for an advertisement name at step 112. This is
just a name for future reference.
The purpose of the focus in step 112, as discussed
above, is to prevent an advertisement from being shown that
is not relevant to the guery at hand. The system of the
present invention always shows advertisements that are
~ relevant to what the user has asked for. Therefore, it is
- 39 -
CA 02240009 l998-06-08
W O 97~1183 PCTnUS96/19509
o~ paramount importance that the system know the context o~
the ad. Thus, when the advertiser places an ad, the system
establishes the focus.
The present invention describes the world in terms of
SIC codes, which is a categorization of approximately
64,000 categories. For example, the system knows that
there is a distinction between opera glasses and operating
tables. It knows a distinction between lawyers and
physicians, as well as the distinction between different
10 = kinds of physicians. For example, when the user types in
bicycle as the focus, the present invention accesses the
ca~egory search engine 33 and returns a list of
subcategories related to the bicycle business (e.g.,
bicycle repair, bicycle sales, bicycling as a sport, and so
= forth). The user is prompted ~step 114) to select one or
more of the subcategories from the list that are relevant
to the user's ad. The user can also create his or her own
categories at this point. The result is that the
advertisement is tied to all o~ the categories selected or
created by the user.
The user may also be asked to provide certain
demographic or profile information. For instance, the user
can require that his advertisement be shown only to people
in age group 30 to 40 or only to people living in
Morristown, NJ or any other geographic location. The last
item that the user is asked to specify is the contract.
The various contracts available to the advertiser are
explained above. When the user is finished entering all of
this information, the system updates the ad info database
(step 115).
The system then either accepts the advertisement (step
116), or the system rejects it. The system might reject
-- ~0 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
the advertisement because the contract that the user wants
cannot be satis~ied by the system. If the system decides
at this point that the user's contract cannot be satisfied,
the system displays to the user the next best possible
contract that it can satisfy, and the user is then free to
either choose that contract or to suggest a different one
for consideration by the system. Upon con~irmation of the
ad placement, the advertisement becomes a part of the
database.
Referring to Fig. 11, the ~low of a page placement
process 120 according to the present invention will be
described. The purpose of the page placement process is
similar to the ad placement process described above with
reference to Fig. 10. The page placement process 120 is
distinct ~rom the case where the page resides outside of
the present system, either as a part o~ a search engine or
because somebody else owns the home page. The page
placement process is used for publishers interested in
creating a home page for use in the present system. The
page placement process permits publishers to provide a page
with meta tags and meta contacts.
The page placement process has a starting screen 121
in which one of the menu choices is, "Would you like to
place a page?" If the user clicks on that menu choice, a
screen is shown to the user asking the user to type in a
page name, a page URL (i.e., Universal Resource Locator),
and a ~ocus. The URL is a physical address in terms o~ the
WWW of where the page is actually residing. As discussed
above, the ~ocus is a list of key words that the user
believes captures the content of the page.
Upon entry of the ~ocus, page name, and page URL, the
system retrieves a list of subcategories ~rom the category
- 41 -
_
CA 02240009 1998-06-08
W O g7/21183 PCTnUS96/19509
search engine 33 that are related to the ~ocus at hand and
displays those subcategories to the user (step 124). The
user picks one or more of these subcategories as being
relevant to the content o~ the page. The system is then
able to integrate the page into the page database of the
present invention (step 125) and return a con~irmation o~
the new home page being linked to the relevant categories
(step 126).
Re~erring to Fig. 12, an architecture o~ the
underlying transaction system o~ the present invention will
be described. One of the basic ~eatures of the present
invention is that the advertisements ~isplayed to users
provide a gateway ~or the client to take ~urther action
with the advertiser. That is, the ads are not just there
~or the user to see, they are interactive.
For example, i~ the system shows the user a picture o~
a car or a cookie and the user wants to buy or receive
~urther in~ormation about the advertised product, the user
can make a transaction with the system. The transaction
can be very simple, such as where the user clicks on the
advertisement and is displayed all in~ormation about that
particular product. Or the transaction could be something
more complicated, such as where the user actually enters a
dialogue with the system and buys the product.
The ~low chart shown in Fig. 12 describes a typical
scenario in which the client has seen a certain
advertisement and clicks on that advertisement to actually
buy something. In particular, whatever this person is
going to buy is going to involve multiple servers. The
client is running on Host 1, and the transaction that the
client is re~uesting will involve multiple servers, perhaps
geographically distributed. Host 4 is a bank server
- 42 -
CA 02240009 1998-06-08
WO 97/21183 PCT~US96/19509
running at a bank somewhere on the computer network. Host
3 is a transaction server for logging and serving as the
transaction Eocal point. Host 2 is a server that accepts
the start o:E the transaction i~rom the client housed at Host
1.
A typical transaction where the client 130 sees an
advertisement and clicks on the advertisement will now be
described by re:Eerence to the transaction system
architecture diagram shown in Fig. 12 and the screen
displays shown in Figs. 13A and 13B. The action o:E
clicking on the advertisement is captured by the gate 131
in Host 2, and the appropriate in:Eormation is then
displayed to the client by the transaction client 132 in
Host 2. For example, the transaction client 132 might
prompt the client to enter the type o~ transaction desired.
The transaction client in Host 2 is a client ~or a
transaction server 133 in Host 3.
Referring to Figs. 13A and 13B, in the typical
transaction the user first clicks on an item :Erom a list of
~eatures o~ ered by the particular publisher (Fig. 13A), in
this case, the item "Internet DMV." A second screen
display (Fig. 13B) then appears in which an advertisement
is provided in the middle o:~ the page that says "Division
of Motor Vehicles, Morristown, New Jersey, Automatic
Renewal o~ Driving License." The user may then click on
this particular advertisement. At this point a screen is
displayed to the user asking the user what type o:E
transaction the user wants to make. The next screen
generated by the transaction client at Host 2 would say,
~or example, "Would you like to renew your license?" or
"Would you like to get a new car registration?l' I~ the
~ user says, "I would like to renew my driver~s license," the
- 43 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
request is captured by the transaction client 13~ at Host 2
and given to the transaction server 133 in Host 3. The
transaction server 133 in Host 3 then receives this re~auest
for renewal of~ driving license, extracts the appropriate
forms to be i~illed out from its local database, and
provides the ~orms to the transaction client 132 in Host 2.
The transaction client 132 at Host 2 then receives these
forms and ~ills them out with the client's information with
help from the client 130 at ~lost 1. Thus, the client's
name, address, car ID and other necessary information are
filled in :Eor the cllent automatically.
The client 130 is asked to type in a PIN number to
start the second part of the transaction. If the client
130 types in the PIN number, the second part of the
transaction starts. The second part oi~ the transaction is
that the :~orm that has now been filled in and constitutes
the re~[uest ~or a renewal of driver's license is sent from
the client 130 in Host 1 to the transaction client 132 in
Host 2, and :Erom the transaction client 132 in Host 2 to
the transaction server 133 in Host 3. At this point, there
are two things that have to happen at Host 3. First, the
particular re~[uest for renewal of~ the driving license has
to be processed by making a record that this person has
renewed the license and by sending con~irmation back to the
-client. Second, the transaction server 133 must be paid
for the renewal of the driving license. In other words,
there has to be a monetary fee that has to be exchanged
between the client and the DMV.
In exchanging the monetary fee, the transaction server
_133 will also act as a transaction client 134 to the bank
server 135 in Host 4. The transaction client 134 sends a
message to the bank server 135 in Host 4 indicating that it
- 44 -
CA 02240009 1998-06-08
W O 97/21183 PCTAUS96/19509
has the client's PIM number and the authorization to deduct
a certain ~ee ~rom the client's account. The bank server
135 authenticates that information, logs the in~ormation in
its own records, and sends back an electronic approval for
the debit.
The transaction client 134 at that point indicates
receipt of the payment to the transaction server 133 in
Host 3. The transaction server 133 in Host 3 logs receipt
o~ the money, receipt of the re~uest, and sends a
confirmation message through the transaction client 132 and
gate 131 back to the client 130 at Host 1. The
con~irmation might say, for example, "We have received your
request; we have deducted $17 from your account; your
license is in the mail; here is your new driving license
number; thank you very much.~
Re~erring to Fig. 14, the transaction process of the
present invention will now be described by re~erence to a
flow chart. The user starts the process (step 140) by
clicking on an appropriate advertisement to ask for a
transaction. The system then links the user (step 141) to
the transaction server (step 142). The transaction server
then returns the required ~orm to the client (step 143),
and the client ~ills in the ~orm with the user's pro~ile
in~ormation. The form is then resubmitted to the
transaction server (step 144). The transaction server
accesses the bank server (step 145) to determine whether
the user has the re~uired money and whether the money can
be withdrawn.
Upon authentication by the bank server, the
transaction server receives con~irmation from the bank
server (step 146) that the user has given a valid account
number, and that the bank server has in ~act authenticated
- 45 -
CA 02240009 1998-06-08
wo 97n~183 PCT/USg6/195(~g
the user and has authenticated the deduction of the
appropriate sums from the bank. The transaction server
then makes the deduction and puts the deducted amount into
the bank server's log (step 147). These logs are
maintained so that at any time users can ~ind out how much
money they have spent or who has bought what things. The
transaction server also maintains a transaction server log
of the transaction time and any other particulars of the
transaction desired (step 1~8). Once the logging is
complete, the transaction server then generates a
confirmation o~ the transaction which is then displayed to
the client (step 149).
Referrin~ to Fig. 15, the prime space manager 20 will
now be described in further detail. As explained above, an
15 _ important ~eature of the present invention is that it
o~fers advertisers certain contractual guarantees as to how
and when their ads will ~e shown in prime space (the ~irst
screen of information displayed to the user). These
contractual guarantees include frequency-based contracts,
ratio or percentage-based contracts, exclusive or
competiti~e contracts, dependent contracts, and story
contracts. These contracts can be used alone or combined
in a variety of ways, as previously explained.
The prime space manager 20 has a prime space algorithm
150 that accepts as inputs the list of relevant ads that
are related to the query at hand, the size o~ the prime
space, and the list of all ad contracts. The prime space
manager 20 then looks at all the ad contracts and
determines which advertisements to show to the user. The
prime space manager 20 then updates the contracts (step
151) to indicate which ads were selected (this information
is used in considering which ads to select the next time).
- 46 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
The prime space manager 20 then provides a list of prime
space ads to be shown to the appropriate module. That is,
the prime space manager 20 accepts a possibly very long
list of advertisements and, based on the contracts that it
has, filters the ads to a smaller list cont~;n;ng exactly
the number of advertisements that it can show based on the
size of prime space.
The following examples of prime space algorithms are
provided to further illustrate the function and operation
of the prime space manager 20 o~ the present invention. It
should be noted that many variations of these algorithms
are possible, and that the specific examples provided are
for purposes of illustration only.
Notations:
Let A1.... An denote the advertisements in the system
o~ the present invention.
Let P1.... Pn denote the contract values associated
with the corresponding advertisements (Pi denotes the
contract value associated with advertisement Ai, as a
function of the price paid by the advertiser.)
Let S denote the size of the prime space in the
system.
CA 02240009 1998-06-08
W O 97/21183 PCTAUS96/19509
Prime S~ace:
The prime space on a user~s t~rm;n~l means the first
screen of data which constitutes the answer to the user's
query (plus the relevant advertisements). In this context,
advertisers will be assured of "fair" treatment in the
sense that their advertisements will be presented to the
targeted users in a manner that is commensurate with the
fees they were charged. Fairness means e~ual access as
well as controlled access--ensuring that advertisers who
pay more are more accessible than those who pay less.
Contracts:
Contracts are speci~ications that indicate the
~requency of display of a given advertisement in response
to relevant user queries.
The example prime space algorithms provided below may
be used for the following four types o~ advertisement
contracts:
1. Frequency-based: These contracts specify the
number o~ times a given advertisement is to be shown
in response to the relevant user gueries.
2. Ratio-based: These contracts specify how o~ten a
given advertisement is to be shown in the prime space
in response to the relevant user ~ueries.
3. Dependent: An ad Ai can have a dependent contract
of X% with another ad Aj. The dependent contract will
ensure that ad Ai is shown together with Aj at least X%
30 = of the times ad Ai will be shown.
- 48 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
4. Exclusive: An ad Ai can have an exclusive contract
with another ad Aj. The exclusive contract will ensure
that ad Ai will not be displayed along with ad Aj.
Algorithm for Freguency-based Contracts:
WHILE (screen space is not filled)
begin
1. Select an advertisement, say Ai, with the
selection biased by the contract value Pi
2. Include Ai in the screen space
end
Algorithm for Ratio-baYed Contract~:
WHILE (prime space is not filled)
begin
1. Select an advertisement, say Ai, with the
selection biased by the contract value P
2. Include Ai in the prime space
end
Algorithm for Dep~n~t Contracts:
WHILE (Prime space is not filled)
begin
1. Select an advertisement, say Ai, with the
selection biased by the contract value P
2. Assign Ai to ~
3. WHILE (some advertisement is selected AND prime
space is not filled)
- Select one of the dependents of ~, say Aj,
with the selection biased by the contract
value Pj
- 49 -
CA 02240009 1998-06-08
W O 97/21183 PCTfUS96/19509
- Assign Aj to A
- Include A in the prime space
end
Al~orithm ~or Exclusive Contracts:
WHILE ~prime space is not :Eilled)
begin
1. Select an advertisement, say Ai, with the
selection biased by the contract value Pi
2. Remove all advertisements Aj's that have an
exclusive contract on Ai
3. Remove all advertisements Ak's that Ai has an
exclusive contract on
4. Include Ai in the prime space
15 - end
Algorithm ~or Overall Prime Space Mana
WHILE (prime space is not :Eilled)
begin
1. Select an advertisement, say Ai, with the
selection biased by the contract value P
2. Assign Ai to A
3. WHILE (some advertisement is selected AND prime
space is not filled)
25 - - Remove all ad~ertisements Aj's that have an
exclusive contract on A
- Remove all advertisements Ak's that A has an
exclusive contract with
- Select one o~ the dependents o~ A, say A
with the selection biased by the contract
value Pm
- 50 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
- Assign Am to A
- Include A in the prime space
end
Algorithm ~or ~h~ck;~g Consistency:
Notations:
Let PA denote the prime space contract value o~ Node A.
Let D(A, B, X) denote the dependency contract value ~rom
advertisement A to advertisement B (A should appear
together with advertisement B, X% of the times
advertisement B appears).
Let E (A, B) denote the exclusive contract ~rom
advertisement A to advertisement B (note that no value is
associated with exclusive contracts).
I~ a new advertisement A is to be introduced into the
system with a prime space contract value o~ PA~ a set o~
dependency contracts D(A,l,x),...,D(A,~,y) and a set o~
exclusive contracts E(A,l),..., E (A, qJ, then ~or checking
the consistency o~ all the contracts, the ~ollowing basic
checks have to be carried out (more speci~ic checks may be
required ~or speci~ic algorithms and their
implementations):
1. Check whether Inequality (I) can be satis~ied
2. For each of the dependency contracts D ~A, i, X)
check whether Inequality (II) can be satis~ied
3. For each o~ the exclusive contracts E(A, i) check
whether conditions (III) can be satisfied
The consistency checking algorithm veri~ies if the new
advertisement can be accommodated with the corresponding
contract. I~ the new advertisement can be accommodated,
the contract is approved and the system is updated to
- 51 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
re~lect the new addition, else, the consistency checking
algorithm in~orms the advertiser o~ the maximal contract
that can be accommodated for the new advertisement.
Install Equation Editor and double-
click here to view equation.
InstaD Equation Editor and double-
click here to view equation.
For checking the Dependency Contracts and the
- Exclusive Contracts a graph is drawn by representing all
the advertisements as nodes in a directed graph. A
dependency contract "Advertisement C appears 50~ o~ the
times as advertisement D appears (together)" is represented
as an edge ~rom the node "C" to the node "D". A weight of
0.5 is assigned to this edge. For each exclusive contract
E (C, DJ, there exists an edge in the graph. Thus, a graph
is ~ormed where the nodes denote the advertisements, and
the edges denote the dependency and exclusive contracts.
If a new dependency contract D (A, B, X) is to be
introduced, then the ~ollowing check has to be made for
consistency:
Install Equation Editor and double-
click here to view equation.
If a new exclusive contract E~A,BJ is to be
introduced, the ~ollowing conditions ( III ) should hold (~or
any value o~ x):
- 52 -
CA 02240009 1998-06-08
W O 97/21183 PCT~US96/19509
Install Equation Editor and double-
click here to view equation.
.
where XtA,E~) denotes the weight o:~ the dependency edge :Erom A
to B, i.e., D(A,B,X(A,~J).
CA 02240009 1998-06-08
W O 97/21183 PCTAUS96/19S09
Fairness:
The ~airness guarantees o~ an algorithm for the
system ensures that the advertisements are displayed in a
way that is proportional to the fee charged for that
advertisement. The fairness of the ~reguency-based
contract algorithm, ratio-based contract algorithm, and the
dependent contract algorithm follows from the probability
distribution o~ the contract values and the random number
generator that selects an advertisement with the correct
random bias. The probability that the random number
generator will gene~ate a number in a particular range is
proportional to the length of the range. The larger the
range, the more probable that a number corresponding to
that range will be selected. Each advertisement is
assigned a range o~ values depending on the fee charged for
that advertisement. The more the fee charged, the greater
the range assigned to that advertisement. This ensures
that the larger the ee, the more ~requently (more number
of times) that advertisement will be displayed.
Exclusive contracts are constraints imposed on t~e
display o~ advertisements. Fairness in meeting the
exclusive contracts means that the contracts are satis~ied
(no two advertisements that have an exclusive contract are
displayed together). The prime space management algorithm
150 ensures that the exclusive contracts are met, by
removing all the advertisements that have a relative
contract with an advertisement A, as soon as advertisement
A is selected for display in the prime space.
In order to ensure fairness, the contracts have to be
consistent. When contracts are negotiated with the
advertiser, certain consistency checks (using the
- 54 -
CA 02240009 1998-06-OX
W O 97~1183 PCTAUS96/19509
consistency checking algorithm) are made in order to ensure
that the fairness guarantees can in fact be met.
Story Advertisements:
Story advertisement is a kind of advertisement in
which the advertisement changes dynamically as time
progresses. The story advertisement is composed of a
sequence of static conventional advertisements, which
together tell a story. A story advertisement is displayed
using the notion of refresh-insert tags. A refresh tag
that is associated with a page denotes the time period
after which the story advertisements are refreshed (the
next advertisement in the sequence is displayed). All
other static advertisements are unaffected by the refresh
timer. The refresh tag can be set by the client or the
application. Thus, the story advertisement is a logical
sequence of a number of advertisements, that will be
displayed one at a time at each refresh cycle.
It will be appreciated that the present invention is
not limited to the exact construction or process steps that
have been described above and illustrated in the
accompanying drawings, and that various modifications and
changes can be made without departing from the scope
thereof. It is intended that the scope of the invention
only be limited by the appended claims.
- 55 -
