Methods and system for search engine revenue maximization in internet advertising

• US 7,831,472 B2
• Filed: 08/22/2006
• Issued: 11/09/2010
• Est. Priority Date: 08/22/2006
• Status: Active Grant

• Current Assignee: III Holdings 1, LLC
• Original Assignee: Yan M. Yufik
• Inventors: Yufik, Yan M.
• Primary Examiner(s): Weiss, John G
• Assistant Examiner(s): VANDERHORST, MARIA VICTORIA
• Application Number:
  US11/507,570
• Publication Number:
  US 20080052152A1
• Time in Patent Office: 1,540 Days
• Field of Search: 705/14, 705/14.4, 705/14.6, 705/37, 705/26, 707/6, 707/5, 707/723, 707/3, 707/1
• US Class Current: 705/14.4
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0234 Rebates after completed purchase
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0244 Optimization
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 30/0254 based on statistics
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A method for improving Search Engine revenues from advertisements by selecting and displaying advertisements from a portfolio of advertisements that are likely to attract user traffic while maximizing the expected Search Engine revenues. Conventionally, each sponsored advertisement in the Search Engine portfolio is associated with one or more keywords from a list of advertiser sponsored keywords, such that if a user enters a keyword contained in an advertisement in the portfolio, a corresponding sponsored link is displayed. According to this invention, in addition to the sponsored links, complementary links can be displayed to some of the paid advertisements containing none of the user-entered keywords. The method for computing the complementary links is based on “overlapping queries” and “overlapping intent” models. With the help of such models, integrated search histories are represented as an associative network, in which associative probabilities for the entire list of keywords and the entire portfolio of advertisements are stored and updated according to the actions of all users, such that each user'"'"'s input during a given search session becomes part of the overall record of searches, and is thus used to optimize all future searches. In a particular search session, the associative probabilities are used to compute revenue-maximizing combinations of complementary links and displaying such combinations in addition to the sponsored links.

Claims

1. A method for selecting and displaying links to paid advertisements of an advertiser selected from a portfolio of such advertisements in response to a user inquiry, said method comprising the steps of:

in a server device operated by a search engine service provider, establishing a data base containing an associative network comprising probabilistic associations between each advertisement in the portfolio and each keyword in a list of keywords, such that in response to entry of a particular keyword contained in the list by a user at a remote client device, complementary links to advertisements are displayed to the user at the remote client device which do not contain the particular keyword but still have substantial probability of being visited by the user and recognized as relevant to the search objectives;

in a server device operated by a search engine service provider, representing integrated search histories as an associative network, in which associative probabilities for the entire portfolio of advertisements and the list of keywords are stored and updated according to the actions of all users, such that each user'"'"'s input during a given search session becomes part of the overall record of searches, and is thus used to optimize all future searches similarly;

in a particular search session, initiated by a user at a user device, using such probabilistic associations stored by said data base and said associative probabilities stored by said associative network at a server device to compute near-optimal combinations of complementary links responsive to a user entering a keyword by way of said user device, wherein said complementary links and the corresponding advertisements do not contain user-entered keywords but still have substantial probability of being visited by the user and recognized as relevant to the search objectives, and

identifying the complementary links offering the highest expected revenue for the search engine service provider based on the compensation paid by the advertiser to the search engine service provider and the probability of the user visiting the link in response to a particular search and displaying the identified complementary links offering the highest expected revenue for the search engine service provider to the user at the user device.

2. The method of claim 1 comprising the further step of computing initial probabilistic associations between paid keywords and advertisements in the portfolio based on query overlap, wherein such overlaps are identified when the same keywords are associated with more than one advertisement.

3. The method of claim 1 comprising the further step of computing initial probabilistic associations between user-entered keywords and advertisements in the portfolio based on intention overlaps, wherein such overlaps are identified responsive to entry of consecutive keywords by the user in the course of a particular search session.

4. The method of claim 1, comprising the further step of analyzing the histories of recent searches carried out in a particular search session and updating the list of keywords and associative probabilities between the keywords and advertisements in the portfolio responsive to said analyzing step.

5. The method of claim 1, comprising the further step of partitioning the associative network into clusters in order to improve accuracy in determining associative probabilities and to reduce the amount of processing required to compute the complementary links.

6. The method of claim 1, comprising the further step of determining the complementary link probabilities, determined as the probabilities of users visiting complementary advertisements.

7. The method of claim 6, comprising the further step of using matrices of complementary link probabilities to improve search engine revenues, by computing near-optimal combinations of complementary links offering the highest cumulative complementary link probabilities and/or the highest expected pay-per-view revenues.

8. The method of claim 1, comprising the further step of applying the order of keyword entries during search sessions to infer the user'"'"'s priorities and to apply such priorities to improve optimization results.

9. The method of claim 1, wherein said step of selecting and displaying links to optimal advertisements is performed using a Finite State Probabilistic Automaton (FSPA) comprised of augmented associative networks, or History Graphs, including the steps of:

a) representing integrated search histories as augmented associative networks, or History Graphs in which nodes represent advertisements and directed connections between nodes represent user transitions between the nodes,

b) assigning weights to the nodes based on the characteristics of user activities when visiting the nodes,

c) assigning weights to the connections based on the relative frequencies of traversal, and

d) mapping user entries of keywords and user selections of links during search sessions onto History Graphs and computing complementary link probabilities based on such mappings, and

wherein said step of computing near-optimal combinations of complementary links responsive to a user entering a keyword is performed using the complementary link probabilities thus computed to identify complementary links for display to the user at the user device.

10. The method of claim 9, wherein the computational burden of FSPA modeling is reduced by performing the further steps of:

partitioning the History Graph into cohesive clusters comprising groups of nodes connected by relatively heavily-weighted connections, where connection to nodes outside the clusters are relatively lightly weighted; and

using such clusters to improve results and expedite execution when computing near-optimal combinations of complementary links in response to user queries.

11. The method of claim 10, wherein user traffic and the resulting revenues are increased by performing the further steps of offering monetary or other incentives to users by computing rebate amounts for sales of products responsive to advertisements in such clusters and offering such rebates when the expected revenue increment due to increased traffic inside the cluster exceeds the expected amount of rebate payoffs.

12. The method of claim 11, wherein rebates are offered by displaying cluster contents to users entering clusters, and offering rebates for purchases inside such clusters.

13. The method of claim 10, comprising the further step of increasing revenues by improving conversion rates in selected advertisements, by:

a) identifying link subsets inside History Graph clusters having the highest complementary link probability,

b) offering increased rebates to users entering and completing purchases inside such subsets, and

c) making arrangements with the corresponding advertisers such that their expected payments to the Search Engine provider exceed the expected amount of rebate payoffs.

14. The method of claim 1, comprising the further step of using the comparative duration of link visits during search sessions, to augment selection of complementary links in the current and/or subsequent sessions by the same user.