User-based advertisement positioning using markov models

• US 8,271,328 B1
• Filed: 12/17/2008
• Issued: 09/18/2012
• Est. Priority Date: 12/17/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gasser, Ralph U., Frumkin, Michael, Gopalratnam, Karthik, Baltz, Edward A., Nguyen, Khanh, Sussman, Myles, Friedman, Gregory J.
• Primary Examiner(s): Le, Khanh H
• Application Number:
  US12/337,066
• Time in Patent Office: 1,371 Days
• Field of Search: 705 141- 1473, 705 729- 731, 706 12- 62, 707/999.003
• US Class Current: 705/14.4
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Methods and systems to modify the number and/or positioning of advertisements presented to a user based on that user'"'"'s activity patterns (e.g., previous queries, query result selections, ad selections, etc.) and the order in which events constituting the activity patterns occurred. For example, the methods and systems can be based on a Markov model utilizing the user'"'"'s activity patterns.

Claims

1. A computer-implemented method, comprising:

receiving a set of advertisements to be displayed to a user, wherein advertisements in the set of advertisements are arranged according to a first order;

accessing user history data, the user history data defining a set of past user events, including a most recent past user event, associated with the user and defining an order in which the past user events occurred and the user history data comprising impression type data defining a display configuration of advertisements associated with the most recent past user event, wherein the display configuration specifies an arrangement of advertisements as displayed to a user;

constructing, by one or more computer processors, sequences of data from the set of past user events, the constructed sequences including a first sequence that includes user history data defining the most recent past user event from the set of past user events and the impression type data and one or more successive sequences successive to the first sequence, wherein;

each of the one or more successive sequences includes user history data of a previous sequence and user history data defining an additional past user event from the set of past user events according to the order in which the past user events occurred;

generating, by one or more computer processors, positioning data based on the constructed sequences and the order in which the past user events occurred, wherein the positioning data specify changes to the first order of the set of advertisements to be displayed to the user, the changes to the first order resulting in a second order that is different from the first order, wherein generating positioning data comprises;

determining a product of positioning multipliers, each positioning multiplier corresponding to a constructed sequence and representing a commerciality of a user that performed the corresponding constructed sequence, the commerciality of a user being indicative of the user'"'"'s interests in commercial offerings; and

providing one or more advertisements from the set of advertisements for display to the user in the second order based at least in part on the positioning data.

2. The method of claim 1, wherein the user history data includes time data defining for each of the past user events a time associated with the event.

3. The method of claim 1, wherein each of the past user events corresponds to an action of the user in response to a query submitted by the user, the action including at least one of no query results or advertisements selected, one query result selected from a first set of query results, one query result selected from a second set of query results, multiple query results selected, a top advertisement selected, a right-hand-side advertisement selected, multiple advertisements selected, and both a query result and an advertisement selected.

4. The method of claim 1, wherein:

the set of past user events includes;

a first past user event;

a second past user event occurring after the first past user event; and

wherein the most recent past user event occurs after the second past user event; and

the constructed sequences include;

a second sequence including user history data defining the most recent past user event and the second past user event; and

a third sequence including user history data defining the most recent past user event, the second past user event, and the first past user event.

5. The method of claim 4, wherein the positioning multipliers include:

a first positioning multiplier corresponding to the first sequence;

a second positioning multiplier corresponding to the second sequence; and

a third positioning multiplier corresponding to the third sequence.

6. The method of claim 5, wherein determining a product of positioning multipliers includes determining a product of the first positioning multiplier, the second positioning multiplier, and the third positioning multiplier.

7. The method of claim 1, wherein generating positioning data based on the constructed sequences includes:

accessing a multiplier data store that stores positioning multipliers partitioned according to corresponding sequences; and

selecting positioning multipliers from the multiplier data store according to the constructed sequences.

8. The method of claim 1, wherein constructing sequences of data from the set of past user events includes:

constructing sequences of data from the set of past user events based on a Markov model utilizing the set of past user events and the order in which the past user events occurred.

9. The method of claim 1, wherein an advertisement from the set of advertisements has a first click-through-rate, the method further comprising:

adjusting the first click-through-rate to a second click-through-rate for the advertisement based at least in part on the positioning data.

10. The method of claim 9, wherein the first click-through-rate does not exceed a promotion threshold, the method further comprising:

determining that the second click-through-rate for the advertisement exceeds the promotion threshold; and

changing an order of the advertisement in the set of advertisements in response to determining that the second click-through-rate for the advertisement exceeds the promotion threshold.

11. The method of claim 9, wherein the positioning data specify at least one of a number and positioning of advertisements in the set of advertisements to be displayed to the user.

12. A system, comprising:

a user history data store storing user history data, the user history data defining a set of past user events, including a most recent past user event, associated with the user and defining an order in which the past user events occurred and the user history data comprising impression type data defining a display configuration of advertisements associated with the most recent past user event, wherein the display configuration specifies an arrangement of advertisements as displayed to a user; and

a positioning system configured for;

receiving a set of advertisements to be displayed to the user, wherein advertisements in the set of advertisements are arranged according to a first order;

accessing the user history data store;

constructing sequences of data from the set of past user events, the sequences including a first sequence that includes user history data defining the most recent past user event from the set of past user events and the impression type data and one or more successive sequences successive to the first sequence, wherein;

each of the one or more successive sequences includes user history data of a previous sequence and user history data defining an additional past user event from the set of past user events according to the order in which the past user events occurred;

generating positioning data based on the constructed sequences and the order in which the past user events occurred, wherein the positioning data specify changes to the first order of the set of advertisements to be displayed to the user, the changes to the first order resulting in a second order that is different from the first order, wherein generating positioning data comprises;

determining a product of positioning multipliers, each positioning multiplier corresponding to a constructed sequence and representing a commerciality of a user that performed the corresponding constructed sequence, the commerciality of a user being indicative of the user'"'"'s interests in commercial offerings; and

providing one or more advertisements from the set of advertisements for display to the user in the second order based at least in part on the positioning data.

13. The system of claim 12, further comprising:

a multiplier data store storing positioning multipliers, each positioning multiplier corresponding to a sequence; and

wherein to generate positioning data based on the constructed sequences, the positioning system is configured for;

accessing a multiplier data store that stores positioning multipliers partitioned according to corresponding sequences; and

selecting positioning multipliers from the multiplier data store according to the constructed sequences.

14. The system of claim 13, wherein:

the set of past user events includes;

a first past user event;

a second past user event occurring after the first past user event; and

wherein the most recent past user event occurs after the second past user event; and

the constructed sequences include;

a second sequence including user history data defining the most recent past user event and the second past user event; and

a third sequence including user history data defining the most recent past user event, the second past user event, and the first past user event.

15. The system of claim 14, wherein the positioning multipliers include:

a first positioning multiplier corresponding to the first sequence;

a second positioning multiplier corresponding to the second sequence; and

a third positioning multiplier corresponding to the third sequence.

16. The system of claim 15, wherein determining a product of positioning multipliers includes determining a product of the first positioning multiplier, the second positioning multiplier, and the third positioning multiplier.

17. A computer-implemented method, comprising:

receiving a set of advertisements to be displayed to a user, wherein advertisements in the set of advertisements are arranged according to a first order;

accessing user history data, the user history data defining a set of past user events for the user, an order in which the past user events occurred, and including time data defining for each of the past user events a time associated with the event and impression type data defining for each past user event a display configuration of advertisements associated with the event;

constructing, by one or more computer processors, sequences of data from the user history data, the sequences including a first sequence and one or more successive sequences successive to the first sequence, wherein;

the first sequence includes user history data defining a past user event from the set of past user events, and including at least one of time data and impression type data associated with the past user event; and

each of the one or more successive sequences includes;

user history data of a previous sequence; and

user history data defining an additional past user event from the set of past user events according to the order in which the past user events occurred, and including at least one of time data and impression type data associated with the additional past user event;

generating an aggregate user history data set defining an aggregation of the set of past user events, wherein the aggregate user history data set does not define an order in which past user events occurred;

generating positioning data, by one or more computer processors, based on the constructed sequences that include the user history data that does define an order in which the past user events occurred and on the aggregate user history data set that does not define an order in which past user events occurred, wherein the positioning data specify changes to the first order of the set of advertisements to be displayed to the user, the changes to the first order resulting in a second order that is different from the first order, wherein generating positioning data comprises;

determining a product of positioning multipliers, each positioning multiplier corresponding to a constructed sequence and representing a commerciality of a user that performed the corresponding constructed sequence, the commerciality of a user being indicative of the user'"'"'s interests in commercial offerings; and

providing one or more advertisements from the set of advertisements for display to the user in the second order based at least in part on the positioning data.

18. The method of claim 17, wherein generating sequences of data from the set of past user events includes:

generating sequences of data from the set of past user events based on a Markov model utilizing the set of past user events, the order in which the past user events occurred, the time data, and the impression type data.

19. A system comprising:

one or more data processors; and

instructions stored on a computer readable storage medium that when executed by the one or more data processors cause the one or more data processors to perform operations comprising;

receiving a set of advertisements to be displayed to a user, wherein advertisements in the set of advertisements are arranged according to a first order;

accessing user history data, the user history data defining a set of past user events for the user, an order in which the past user events occurred, and including time data defining for each of the past user events a time associated with the event and impression type data defining for each past user event a display configuration of advertisements associated with the event;

constructing sequences of data from the user history data, the sequences including a first sequence and one or more successive sequences successive to the first sequence, wherein;

the first sequence includes user history data defining a past user event from the set of past user events, and including at least one of time data and impression type data associated with the past user event; and

each of the one or more successive sequences includes;

user history data of a previous sequence; and

user history data defining an additional past user event from the set of past user events according to the order in which the past user events occurred, and including at least one of time data and impression type data associated with the additional past user event;

generating an aggregate user history data set defining an aggregation of the set of past user events, wherein the aggregate user history data set does not define an order in which past user events occurred;

generating positioning data, by one or more computer processors, based on the constructed sequences that include the user history data that does define an order in which the past user events occurred and on the aggregate user history data set that does not define an order in which past user events occurred, wherein the positioning data specify changes to the first order of the set of advertisements to be displayed to the user, the changes to the first order resulting in a second order that is different from the first order, wherein generating positioning data comprises;

determining a product of positioning multipliers, each positioning multiplier corresponding to a constructed sequence and representing a commerciality of a user that performed the corresponding constructed sequence, the commerciality of a user being indicative of the user'"'"'s interests in commercial offerings; and

providing one or more advertisements from the set of advertisements for display to the user in the second order based at least in part on the positioning data.

20. The system of claim 19, wherein generating sequences of data from the set of past user events includes:

generating sequences of data from the set of past user events based on a Markov model utilizing the set of past user events, the order in which the past user events occurred, the time data, and the impression type data.

21. A computer-readable storage medium having instructions stored thereon, which, when executed by one or more data processors, causes the one or more data processors to perform operations comprising:

receiving a set of advertisements to be displayed to a user, wherein advertisements in the set of advertisements are arranged according to a first order;

accessing user history data, the user history data defining a set of past user events, including a most recent past user event, associated with the user and defining an order in which the past user events occurred and the user history data comprising impression type data defining a display configuration of advertisements associated with the most recent past user event, wherein the display configuration specifies an arrangement of advertisements as displayed to a user;

constructing sequences of data from the set of past user events, the constructed sequences including a first sequence that includes user history data defining the most recent past user event from the set of past user events and the impression type data and one or more successive sequences successive to the first sequence, wherein each of the one or more successive sequences includes user history data of a previous sequence and user history data defining an additional past user event from the set of past user events according to the order in which the past user events occurred;

generating, by one or more computer processors, positioning data based on the constructed sequences and the order in which the past user events occurred, wherein the positioning data specify changes to the first order of the set of advertisements to be displayed to the user, the changes to the first order resulting in a second order that is different from the first order, wherein generating positioning data comprises;

determining a product of positioning multipliers, each positioning multiplier corresponding to a constructed sequence and representing a commerciality of a user that performed the corresponding constructed sequence, the commerciality of a user being indicative of the user'"'"'s interests in commercial offerings; and

providing one or more advertisements from the set of advertisements for display to the user in the second order based at least in part on the positioning data.