Category similarities

• US 8,190,473 B2
• Filed: 03/10/2009
• Issued: 05/29/2012
• Est. Priority Date: 03/10/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Guha, Angshuman, Wang, Xuefu, Zamir, Oren E., Weinberg, Aitan
• Primary Examiner(s): Alvarez, Raquel
• Application Number:
  US12/401,318
• Publication Number:
  US 20100235220A1
• Time in Patent Office: 1,176 Days
• Field of Search: 705/14.4, 705/14.49, 705/14.54, 705/14.73
• US Class Current: 705/14.4
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 30/0254 based on statistics
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

Methods, systems, and apparatus for determining similarity measures between vertical categories based on users'"'"' online activities. The similarity measures are symmetric similarity measures based on both a similarity measure of a first vertical category relative to a second vertical category and a similarity measure of the second vertical category relative to the first vertical category.

Claims

1. A computer-implemented method, comprising:

for each of a plurality of user identifiers;

identifying event data for a user identifier based on past user sessions associated with the user identifier, the event data specifying events that occurred during the past user sessions;

categorizing each of the events as belonging to one or more vertical categories;

for each vertical category, determining a user identifier interest weight for the user identifier based on the events associated with the vertical category;

for each pair of vertical categories, generating, by one or more processors, asymmetric association data representative of an asymmetric association between a first vertical category and a second vertical category of the pair of vertical categories based on the user identifier interest weights, the asymmetric association data being a pair of a first asymmetric similarity measure and a second asymmetric similarity measure, wherein;

the first asymmetric similarity measure is based on an asymmetric similarity measure of the first vertical category with respect to the second vertical category;

the second asymmetric similarity measure is based on an asymmetric similarity measure of the second vertical category with respect to the first vertical category; and

the first asymmetric similarity measure is different from the second asymmetric similarity measure;

for each pair of vertical categories, generating symmetric association data representative of a symmetric association between the first and second vertical categories of the pair of vertical categories, the symmetric association being a pair of equal similarity measures with a first equal similarity measure of the pair being a symmetric similarity measure of the first vertical category with respect to the second vertical category and a second equal similarity measure of the pair being a symmetric similarity measure of the second vertical category with respect to the first vertical category where each equal similarity measure is based on the corresponding first and second asymmetric similarity measures for the first and second vertical categories, and wherein the first equal similarity measure is equal to the second equal similarity measure; and

selecting advertisements for user sessions associated with a user identifier based on the symmetric association data.

2. The method of claim 1, wherein generating the symmetric association data comprises:

generating a first matrix having columns defined by the vertical categories and having rows defined by the plurality of user identifiers, the columns and rows defining cells, each of the cells being, populated with a user identifier interest weight corresponding to a vertical category and a user identifier; and

generating a second matrix from the first matrix, the second matrix haying columns defined by the vertical categories and rows defined by the vertical categories, the columns and rows defining cells, each of the cells including an asymmetric similarity measure.

3. The method of claim 2, wherein generating the symmetric association data comprises:

generating an equal similarity measure based on;

an asymmetric similarity measure in a first cell defined by a column corresponding to a first vertical category and a row corresponding to a second vertical category; and

an asymmetric similarity measure in a second cell defined by a column corresponding to the second vertical category and a row corresponding to the first vertical category; and

replacing each of the asymmetric similarity measures in the first cell and the second cell with the equal similarity measure.

4. The method of claim 3, wherein generating an equal similarity measure comprises:

multiplying the asymmetric similarity measure in the first cell with the asymmetric similarity measure in the second cell.

5. The method of claim 2, wherein generating a second matrix comprises:

for each row in the first matrix, generating a vertical category pair weight for each pair of cells in the row based on a minimum user identifier interest weight from the user identifier interest weights of the pair of cells, and an aggregation of all of the user identifier interest weights in the row; and

aggregating like vertical category pair weights from all of the rows.

6. The method of claim 1, wherein the events include page views of web pages, advertisement click-throughs, or conversions.

7. The method of claim 1, comprising:

restricting the plurality of user identifiers to only user identifiers associated with event data that specify the event of clicking on a specific advertisement.

8. The method of claim 1, wherein selecting advertisements for user sessions associated with a user identifier based on the symmetric association data comprises:

identifying a web page presented on a user device during a user session;

identifying a first vertical category to which the web page belongs;

determining a second vertical category similar to the first vertical category based on the symmetric association data;

selecting an advertisement belonging to the second vertical category; and

providing the advertisement for display on the user device.

9. The method of claim 1, wherein generating symmetric association data comprises:

generating symmetric association data by use of a symmetric association module.

10. The method of claim 1, wherein an equal similarity measure is a symmetric similarity measure of one vertical category with respect to another vertical category independent of user popularity of the vertical categories.

11. A computer-implemented method, comprising:

determining user identifier interest weights for user identifiers in a plurality of vertical categories based on events that occurred during past user sessions for the user identifiers;

for each pair of vertical categories, generating, by one or more processors, asymmetric association data representative of an asymmetric association between a first vertical category and a second vertical category of the pair of vertical categories based on the user identifier interest weights, the asymmetric association data being a pair of a first asymmetric similarity measure and a second asymmetric similarity measure, wherein;

the first asymmetric similarity measure is based on an asymmetric similarity measure of the first vertical category with respect to the second vertical category;

the second asymmetric similarity measure is based on an asymmetric similarity measure of the second vertical category with respect to the first vertical category; and

the first asymmetric similarity measure is different from the second asymmetric similarity measure;

for each pair of vertical categories, generating symmetric association data representative of a symmetric association of a first vertical category with a second vertical category, the symmetric association being a pair of equal similarity measures where an equal similarity measure is based on the corresponding first and second asymmetric similarity measures, wherein each equal similarity measure of the pair is a same equal similarity measure;

identifying a web page presented on a user device during a user session;

identifying a vertical category to which the web page belongs;

determining a vertical category similar to the vertical category to which the web page belongs based on the symmetric association data;

selecting an advertisement belonging to the determined vertical category; and

providing the advertisement for display on the user device.

12. The method of claim 11, wherein the events include page views of web pages, advertisement click-throughs, or conversions.

13. The method of claim 11, comprising:

selecting an advertisement belonging to the vertical category to which the web page belongs; and

providing the advertisement belonging to the vertical category to which the web page belongs for display on the user device along with the advertisement belonging to the determined vertical category.

14. The method of claim 11, wherein generating symmetric association data comprises:

generating symmetric association data by use of a symmetric association module.

15. A system, comprising:

one or more data processing devices;

software stored on a computer storage apparatus and comprising instructions executable by the one or more data processing devices and upon such execution cause the one or more data processing devices to define;

a user interest module configured to;

for each of a plurality of user identifiers;

identify event data for a user identifier based on past user sessions associated with the user identifier, the event data specifying events that occurred during the past user sessions;

categorize each of the events as belonging to one or more vertical categories; and

for each vertical category, determine a user identifier interest weight for the user identifier based on the events associated with the vertical category;

a symmetric association module configured to;

for each pair of vertical categories, generating asymmetric association data representative of an asymmetric association between a first vertical category and a second vertical category of the pair of vertical categories based on the user identifier interest weights, the asymmetric association data being a pair of a first asymmetric similarity measure and a second asymmetric similarity measure, wherein;

the first asymmetric similarity measure is based on an asymmetric similarity measure of the first vertical category with respect to the second vertical category;

the second asymmetric similarity measure is based on an asymmetric similarity measure of the second vertical category with respect to the first vertical category; and

the first asymmetric similarity measure is different from the second asymmetric similarity measure;

for each pair of vertical categories, generating symmetric association data representative of a symmetric association between the first and second vertical categories of the pair of vertical categories, the symmetric association being a pair of equal similarity measures with a first equal similarity measure of the pair being a symmetric similarity measure of the first vertical category with respect to the second vertical category and a second equal similarity measure of the pair being a symmetric similarity measure of the second vertical category with respect to the first vertical category where each equal similarity measure is based on the corresponding first and second asymmetric similarity measures for the first and second vertical categories, and wherein the first equal similarity measure is equal to the second equal similarity measure; and

an advertisement selection module configured to select advertisements for user sessions associated with a user identifier based on the symmetric association data.

16. The system of claim 15, wherein the symmetric association module is configured to:

generate a first matrix having columns defined by the vertical categories and having rows defined by the plurality of user identifiers, the columns and rows defining cells, each of the cells being populated with a user identifier interest weight corresponding to a vertical category and a user identifier; and

generate a second matrix from the first matrix, the second matrix having columns defined by the vertical categories and rows defined by the vertical categories, the columns and rows defining cells, each of the cells including an asymmetric similarity measure.

17. The system of claim 16, wherein the symmetric association module is configured to:

generate an equal similarity measure based on;

an asymmetric similarity measure in a first cell defined by a column corresponding to a first vertical category and a row corresponding to a second vertical category; and

an asymmetric similarity measure in a second cell defined by a column corresponding to the second vertical category and a row corresponding to the first vertical category; and

replace each of the asymmetric similarity measures in the first cell and the second cell with the equal similarity measure.

18. The system of claim 17, wherein the symmetric association module is configured to:

multiply the asymmetric similarity measure in the first cell with the asymmetric similarity measure in the second cell.

19. The system of claim 16, wherein the symmetric association module is configured to:

for each row in the first matrix, generate a vertical category pair weight for each pair of cells in the row based on a minimum user identifier interest weight from the user identifier interest weights of the pair of cells, and an aggregation of all of the user identifier interest weights in the row; and

aggregate like vertical category pair weights from all of the rows.

20. The system of claim 16, wherein the symmetric association module is configured to:

restrict the plurality of user identifiers to only user identifiers associated with event data that specify the event of clicking on a specific advertisement.

21. The system of claim 20, wherein the advertisement selection module is configured to select advertisements for user sessions associated with a user identifier based on symmetric association data derived from event data for the restricted plurality of user identifiers.

22. The system of claim 15, wherein the events include page views of web pages, advertisement click-throughs, or conversions.