Representing user behavior information

• US 7,809,752 B1
• Filed: 12/06/2005
• Issued: 10/05/2010
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: AudienceScience, Inc.
• Original Assignee: AudienceScience, Inc.
• Inventors: Kozyrczak, Maciek, Chen, Cheng C., Nayfeh, Basem
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US11/294,756
• Time in Patent Office: 1,764 Days
• Field of Search: 707 1- 4, 707100-102, 707/104.1
• US Class Current: 707/790
• CPC Class Codes: G06F 16/95 Retrieval from the web
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A facility for analyzing user behavior information is described. The facility receives a stream of user behavior information. The facility augments a representation of user behavior in accordance with the received stream of user behavior information. The representation augmented by the facility is a sparse matrix of user behavior facts. The facility analyzes the sparse matrix to obtain an analysis result for the received stream of user behavior.

Claims

1. A method performed by a computing system including a processor and a memory for analyzing user behavior information, comprising:

receiving a stream of user behavior information, wherein the received stream of user behavior information comprises a request from a particular user for a web page;

augmenting a representation of user behavior in accordance with the received stream of user behavior information, the representation comprising a sparse matrix of user behavior facts, wherein the augmentation is performed solely in response to the request from the particular user for the web page and comprises—

in response to receiving the stream of user behavior information, creating an entry in the sparse matrix comprising details of the request;

placing a first pointer to the created entry in a chain of pointers corresponding to the user; and

placing a second pointer to the created entry in a chain of pointers corresponding to the request; and

analyzing the sparse matrix to obtain an analysis result for the stream of user behavior.

2. The method of claim 1 wherein the analyzing comprises traversing a first dimension of the sparse matrix representation at a selected position in a second dimension of the sparse matrix representation to analyze user behavior facts relating to a selected value in the second dimension that corresponds to the selected position in the second dimension, and wherein the first dimension corresponds to a range of user action types and the second dimension corresponds to a range of user identities.

3. The method of claim 1 wherein the analyzing comprises traversing a first dimension of the sparse matrix representation at a selected position in a second dimension of the sparse matrix representation to analyze user behavior facts relating to a selected value in the second dimension that corresponds to the selected position in the second dimension, and wherein the first dimension corresponds to a range of user identities and the second dimension corresponds to a range of user action types.

4. The method of claim 1 wherein the entirety of the augmented representation of user behavior resides in volatile memory of a single computer system during the analysis.

5. The method of claim 1 wherein the received stream of user behavior information reflects web browsing behavior.

6. The method of claim 1 wherein the received stream of user behavior information reflects television viewing behavior.

7. The method of claim 1 wherein the received stream of user behavior information reflects audio listening behavior.

8. The method of claim 1 wherein the received stream of user behavior information reflects online product purchasing behavior.

9. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type,

the method further comprising receiving a request for analysis, wherein the analyzing is performed upon receiving the request for analysis, and wherein the received request for analysis includes one or more user identities.

10. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type,

the method further comprising receiving a request for analysis, wherein the analyzing is performed upon receiving the request for analysis, and wherein the received request for analysis includes one or more action types.

11. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type,

the method further comprising receiving a request for analysis, wherein the analyzing is performed upon receiving the request for analysis, and wherein the received request for analysis includes a time range indicating a set of facts to consider as part of the analysis.

12. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type,

the method further comprising receiving a request for analysis, wherein the analyzing is performed upon receiving the request for analysis, and wherein the received request for analysis includes an analysis type indicating the particular variety of analysis to perform.

13. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type, and wherein the received stream of user behavior information contains user action indications, each user action indication containing information identifying a user and information identifying an action performed by the identified user, the method further comprising, for each received user action indication:

applying a selected hashing algorithm to the user identification information to obtain a hash result;

using a local user identifier table to translate the hash result into a smaller local user identifier;

using the local user identifier to select a position in the first dimension of the sparse matrix;

using a local action type identifier table to translate the action identification information into a local action type identifier;

using the local action type identifier to select a position in the second dimension of the sparse matrix;

if an element exists in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension, modifying the contents of the element to reflect the user action indicated by the user action indication; and

if no element exists in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension, creating an element in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension whose contents reflect the user action indicated by the user action indication.

14. The method of claim 1 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type, and wherein the sparse matrix includes elements only for combinations of values of the first and second dimensions for which at least one user behavior fact has been received.

15. A computer-readable storage medium encoded with instructions to cause a computing system to perform a method for analyzing user behavior information, the method comprising:

receiving a stream of user behavior information, wherein the received stream of user behavior information comprises an action performed by a user;

augmenting a representation of user behavior in accordance with the received stream of user behavior information, the representation comprising a sparse matrix of user behavior facts, wherein the augmentation is performed solely in response to the action performed by the user and comprises—

in response to receiving the stream of user behavior information, creating an entry in the sparse matrix comprising details of the action performed by the user;

placing a first pointer to the created entry in a chain of pointers corresponding to the user; and

placing a second pointer to the created entry in a chain of pointers corresponding to the action performed by the user; and

analyzing the sparse matrix to obtain an analysis result for the stream of user behavior.

16. The computer-readable storage medium of claim 15 wherein the analyzing comprises traversing a first dimension of the sparse matrix representation at a selected position in a second dimension of the sparse matrix representation to analyze user behavior facts relating to a selected value in the second dimension that corresponds to the selected position in the second dimension, and wherein the first dimension corresponds to a range of user action types and the second dimension corresponds to a range of user identities.

17. The computer-readable storage medium of claim 15 wherein the analyzing comprises traversing a first dimension of the sparse matrix representation at a selected position in a second dimension of the sparse matrix representation to analyze user behavior facts relating to a selected value in the second dimension that corresponds to the selected position in the second dimension, and wherein the first dimension corresponds to a range of user identities and the second dimension corresponds to a range of user action types.

18. The computer-readable storage medium of claim 15 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type, and wherein the received stream of user behavior information contains user action indications, each user action indication containing information identifying a user and information identifying an action performed by the identified user, the method further comprising, for each received user action indication:

applying a selected hashing algorithm to the user identification information to obtain a hash result;

using a local user identifier table to translate the hash result into a smaller local user identifier;

using the local user identifier to select a position in the first dimension of the sparse matrix;

using a local action type identifier table to translate the action identification information into a local action type identifier;

using the local action type identifier to select a position in the second dimension of the sparse matrix;

if an element exists in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension, modifying the contents of the element to reflect the user action indicated by the user action indication; and

if no element exists in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension, creating an element in the sparse matrix at the selected position in the first dimension and the selected position in the second dimension whose contents reflect the user action indicated by the user action indication.

19. The computer-readable storage medium of claim 15 wherein a first dimension of the sparse matrix corresponds to user identity and a second dimension of the sparse matrix corresponds to action type, and wherein the sparse matrix includes elements only for combinations of values of the first and second dimensions for which at least one user behavior fact has been received.

20. One or more computer memories collectively storing a user behavior data structure, the data structure comprising a sparse matrix of elements, each element containing information indicating a user behavior fact,

wherein the sparse matrix has at least two dimensions, including a first dimension for user identity and a second dimension for action type,

wherein the sparse matrix is capable of being used by a processor to analyze user behavior represented in the sparse matrix, and

wherein a recurring time period is indicated in connection with the data structure, and

wherein each element of the sparse matrix identifies an instance of the recurring time period to which the user behavior fact indicated by the information contained by the element relates,

wherein each element of the sparse matrix indicates a number of times a particular user performed an action of a particular type during the identified instance of the recurring time period.

21. The computer memories of claim 20 wherein each user behavior fact indicated by an element of the sparse matrix relates to web-browsing activity.

22. The computer memories of claim 20

wherein, for each element of the sparse matrix, the particular user is identified by a position in a first dimension of the matrix occupied by the element, and the particular action type is identified by a position in a second dimension of the matrix occupied by the element.

23. The computer memories of claim 20 wherein the sparse matrix includes elements only for combinations of values of the first and second dimensions for which at least one user behavior fact has been received.