Maintaining state transition data for a plurality of users, modeling, detecting, and predicting user states and behavior

• US 7,941,383 B2
• Filed: 12/21/2007
• Issued: 05/10/2011
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Heck, Larry P.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/962,753
• Publication Number:
  US 20090164395A1
• Time in Patent Office: 1,236 Days
• Field of Search: 706/16, 706/12, 706 45- 47, 707/706, 707708-709
• US Class Current: 706/21
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

Mechanisms model, detect, and predict user behavior as a user navigates the Web. In one embodiment, mechanisms model user behavior using predictive models, such as discrete Markov processes, where the user'"'"'s behavior transitions between a finite number of states. The user'"'"'s behavior state may not be directly observable (e.g., a user does not proactively indicate what behavior state he is in). Thus, the behavior state of a user is usually only indirectly observable. Mechanisms use predictive models, such as hidden Markov models, to predict the transitions in the user'"'"'s behavior states.

Claims

1. A method for providing targeted data, the method comprising:

maintaining state transition information for a plurality of states, wherein the state transition information indicates state-to-state transitions made by one or more users as the one or more users navigate from web resources associated with one state to web resources associated with other states;

wherein a first state of the plurality of states is associated with a first plurality of web resources;

wherein a second state of the plurality of states is associated with a second plurality of web resources that are different than the first plurality of web resources;

receiving a request, by a first user, to retrieve a particular web resource;

in response to receiving the request, determining that the particular web resource is in the first plurality of web resources that are associated with the first state;

based on the particular web resource being associated with the first state, determining that, having requested the particular web resource, the first user is in the first state;

in response to determining that the first user is in the first state, inspecting the state transition information to determine a next state associated with said first state;

generating predictive data in association with the next state;

based on the state transition information indicating that the next state is the next state associated with the first state, causing at least a portion of said predictive data associated with the next state to be displayed to the first user;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein inspecting the state transition information to determine a next state associated with said first state comprises executing a predictive model to select the next state.

4. The method of claim 1, wherein the state-to-state transitions are specific to the first user.

5. The method of claim 1, wherein:

said portion of said predictive data includes a web resource; and

causing at least a portion of said predictive data associated with the next state to be displayed to the first user includes causing said web resource to be displayed by a web browser.

6. The method of claim 1, further comprising anonymously updating the state transition information to record that a user navigated from the first state to the second state.

7. The method of claim 1, further comprising updating the state transition information to record that a user navigated from the first state to the second state, wherein updating includes receiving an indication of consent from the user before state transition information is recorded.

8. The method of claim 1, wherein inspecting the state transition information to determine a next state associated with said first state includes evaluating the state-to-state transitions to find a common pattern of state access among the one or more users.

9. The method of claim 1, wherein the second state corresponds to the next state.

19. The method of claim 1, wherein:

the state transition information indicates that the first state transitions to a third state of the plurality of states and, alternatively, to a fourth state of the plurality of states;

inspecting the state transition information to determine a next state associated with said first state includes determining one of the third state or the fourth state;

said next state is one of the third state or the fourth state.

20. The method of claim 19, wherein:

the transition to the third state from the first state is associated with a first probability;

the transition to the further state from the first state is associated with a second probability that is different than the first probability; and

determining one of the third state or the fourth state is based on the first and second probabilities.

21. The method of claim 1, wherein said portion of said predictive data includes one or more of the following:

a link associated with said next state, an advertisement associated with said next state, or sponsor-based data associated with said next state, wherein said sponsor-based data includes data, submitted by one or more sponsors, that is to be displayed when a set of one or more users are determined to be in a particular state.

22. The method of claim 21, wherein said portion of said predictive data includes an advertisement associated with said next state.

3. The method of 2, wherein the predictive model is a hidden Markov model.

10. A volatile or non-volatile machine-readable storage medium storing instructions for providing targeted data to a set of users, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform:

maintaining state transition information for a plurality of states, wherein the state transition information indicates state-to-state transitions made by one or more users as the one or more users navigate from web resources associated with one state to web resources associated with other states;

wherein a first state of the plurality of states is associated with a first plurality of web resources;

wherein a second state of the plurality of states is associated with a second plurality of web resources that are different than the first plurality of web resources;

receiving a request, by a first user, to retrieve a particular web resource;

in response to receiving the request, determining that the particular web resource is in the first plurality of web resources that are associated with the first state;

based on the particular web resource being associated with the first state, determining that, having requested the particular web resource, the first user is in the first state;

in response to determining that the first user is in the first state, inspecting the state transition information to determine a next state associated with said first state;

generating predictive data in association with the next state;

based on the state transition information indicating that the next state is the next state associated with the first state, causing at least a portion of said predictive data associated with the next state to be displayed to the first user.

11. The machine-readable storage medium of claim 10, wherein inspecting the state transition information to determine a next state associated with said first state comprises executing a predictive model to select the next state.

13. The machine-readable storage medium of claim 10, wherein the state-to-state transitions are specific to the first user.

14. The machine-readable storage medium of claim 10, wherein:

said portion of said predictive data includes a web resource; and

causing at least a portion of said predictive data associated with the next state to be displayed to the first user includes causing said web resource to be displayed by a web browser.

15. The machine-readable storage medium of claim 10, wherein the instructions, when executed by the one or more processors, further cause anonymously updating the state transition information to record that a user navigated from the first state to the second state.

16. The machine-readable storage medium of claim 10, wherein the instructions, when executed by the one or more processors, further cause updating the state transition information to record that a user navigated from the first state to the second state, wherein updating includes receiving an indication of consent from the user before state transition information is recorded.

17. The machine-readable storage medium of claim 10, wherein inspecting the state transition information to determine a next state associated with said first state includes evaluating the state-to-state transitions to find a common pattern of state access among the one or more users.

18. The machine-readable storage medium of claim 10, wherein the second state corresponds to the next state.

23. The machine-readable storage medium of claim 10, wherein:

the state transition information indicates that the first state transitions to a third state of the plurality of states and, alternatively, to a fourth state of the plurality of states;

inspecting the state transition information to determine a next state associated with said first state includes determining one of the third state or the fourth state;

said next state is one of the third state or the fourth state.

24. The machine-readable storage medium of claim 10, wherein:

the transition to the third state from the first state is associated with a first probability;

the transition to the further state from the first state is associated with a second probability that is different than the first probability; and

determining one of the third state or the fourth state is based on the first and second probabilities.

25. The machine-readable storage medium of claim 10, wherein said portion of said predictive data includes one or more of the following:

a link associated with said next state, an advertisement associated with said next state, or sponsor-based data associated with said next state, wherein said sponsor-based data includes data, submitted by one or more sponsors, that is to be displayed when a set of one or more users are determined to be in a particular state.

26. The machine-readable storage medium of claim 25, wherein said portion of said predictive data includes an advertisement associated with said next state.

12. The machine-readable storage medium of 11, wherein the predictive model is a hidden Markov model.