CATEGORIZING ONLINE USER BEHAVIOR DATA

• US 20110077998A1
• Filed: 09/29/2009
• Published: 03/31/2011
• Est. Priority Date: 09/29/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhuang, Dong, Liu, Ning, Yan, Jun, Ji, Lei, Chen, Zheng
• Application Number:
  US12/568,707
• Publication Number:
  US 20110077998A1
• Time in Patent Office: Days
• US Class Current: 705/10
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A method for categorizing online user behavior data, including creating a target set of users based on an advertiser query, identifying two or more users in the target set having one or more first similar behavior attributes using a Minhash algorithm; and modifying the target set according to the two or more identified users.

Claims

1. A method for categorizing online user behavior data, comprising:

creating a target set of users based on an advertiser query;

identifying two or more users in the target set having one or more first similar behavior attributes using a Minhash algorithm; and

modifying the target set according to the two or more identified users.

2. The method of claim 1, wherein creating the target set comprises:

receiving user behavior data from a search logging system, the user behavior data having information pertaining to one or more users and one or more behavior attributes corresponding to the users;

categorizing the user behavior data into a second category according to the behavior attributes; and

determining the target set based on the second category and the advertiser query.

3. The method of claim 2, wherein the behavior attributes comprise one or more queries performed by the users, one or more web page addresses accessed by the users, one or more amounts of time that the users spend on one or more web pages, one or more links selected by the users, one or more time stamps at which the web pages are accessed by the users, one or more time stamps at which the links are selected by the users, or combinations thereof.

4. The method of claim 1, wherein the two or more users are identified using parallel computer systems.

5. The method of claim 2, wherein identifying the two or more users comprises:

categorizing the user behavior data into a first category according to the users;

partitioning the first category into two or more partitioned categories;

sending the partitioned categories to one or more computer systems, wherein each computer system is configured to identify two or more users having one or more second similar behavior attributes in one of the partitioned categories using the Minhash algorithm;

receiving the two or more users having the second similar behavior attributes in the one of the partitioned categories; and

combining the two or more users having the second similar behavior attributes in the one of the partitioned categories.

6. The method of claim 5, wherein the Minhash algorithm is an incremental Minhash algorithm.

7. The method of claim 2, wherein identifying the two or more users comprises:

categorizing the user behavior data into a first category according to the users;

defining one or more Minwise independent permutations of the first category;

defining one or more Minwise hash functions based on the Minwise independent permutations;

determining one or more Minhash signatures using the Minwise hash functions; and

determining one or more similarities between two or more of the users based on the Minhash signatures.

8. The method of claim 7, wherein modifying the target set comprises grouping the two or more identified users based on the similarities.

9. The method of claim 2, further comprising revising the advertiser query based on the modified target set.

10. The method of claim 9, further comprising creating an updated target set based on the second category and the revised advertiser query.

11. The method of claim 1, wherein the advertiser query comprises one or more behavior attributes defined by an advertiser.

12. The method of claim 1, wherein the Minhash algorithm is a parallel Minhash algorithm, an incremental Minhash algorithm, or a parallel incremental Minhash algorithm.

13. A computer-readable storage medium having stored thereon computer-executable instructions which, when executed by at least one computer, cause the at least one computer to:

receive user behavior data from a search logging system, the user behavior data having information pertaining to one or more users and one or more behavior attributes corresponding to the users;

categorize the user behavior data into a first category according to the users;

categorize the user behavior data into a second category according to the behavior attributes;

create a target set of users based on the second category and an advertiser query;

identify two or more users in the target set having one or more similar behavior attributes based on the first category; and

modify the target set based on the two or more identified users.

14. The computer-readable storage medium of claim 13, wherein the two or more users are identified using an incremental Minhash algorithm that incrementally applies a Minhash algorithm based on one or more time stamps corresponding to the user behavior data.

15. The computer-readable storage medium of claim 13, wherein the computer-executable instructions which, when executed by the computer, cause the computer to identify the two or more users comprises computer-executable instructions which, when executed by a computer, cause the computer to:

define one or more Minwise independent permutations of the first category;

define one or more Minwise hash functions based on the Minwise independent permutations;

determine one or more Minhash signatures using the Minwise hash functions; and

determine one or more similarities between two or more of the users based on the Minhash signatures.

16. The computer-readable storage medium of claim 13, wherein the two or more users are identified using multiple computers.

17. A computer system, comprising:

at least one processor; and

a memory comprising program instructions that when executed by the at least one processor, cause the at least one processor to;

receive user behavior data from a search logging system, the user behavior data having information pertaining to one or more users and one or more behavior attributes corresponding to the users;

categorize the user behavior data into a first category according to the users;

categorize the user behavior data into a second category according to the behavior attributes;

create a target set of users based on the second category and an advertiser query;

identify two or more users having one or more similar behavior attributes based on the first category;

modify the target set based on the two or more identified users;

revise the advertiser query based on the modified target set; and

create an updated target set based on the second category and the revised advertiser query.

18. The computer system of claim 17, wherein the behavior attributes comprise one or more queries performed by the users, one or more web page addresses accessed by the users, one or more amounts of time that the users spend on one or more web pages, one or more links selected by the users, one or more time stamps at which the web pages are accessed by the users, one or more time stamps at which the links are selected by the users, or combinations thereof.

19. The computer system of claim 17, wherein the two or more users are identified using a parallel incremental Minhash algorithm.

20. The computer system of claim 17, wherein the advertiser query comprises one or more behavior attributes defined by an advertiser.