CATEGORY SIMILARITIES

• US 20100235220A1
• Filed: 03/10/2009
• Published: 09/16/2010
• Est. Priority Date: 03/10/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Xeufu, Weinberg, Aitan, Guha, Angshuman, Zamir, Oren E.
• Granted Patent: US 8,190,473 B2
• Time in Patent Office: Days
• US Class Current: 705/10
• 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;

generating symmetric association data representative of a symmetric association of a given vertical category with at least one other vertical category based on the user identifier interest weights, the symmetric association being pairs of equal similarity measures where an equal similarity measure is based on a first similarity measure of a first vertical category relative to a second vertical category and a second similarity measure of the second vertical category relative to the first vertical category; 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 representative of a symmetric association of a vertical category with another vertical category 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 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, the asymmetric similarity measure being a similarity measure of a vertical category relative to another vertical category.

3. The method of claim 2, wherein generating the symmetric association data representative of a symmetric association of a vertical category with another vertical category 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. 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;

generating symmetric association data representative of a symmetric association of a vertical category with at least one other vertical category based on the user identifier interest weights, the symmetric association being pairs of equal similarity measures where an equal similarity measure is based on a first similarity measure of a first vertical category relative to a second vertical category and a second similarity measure of the second vertical category relative to the first vertical category;

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.

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

12. The method of claim 10, 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.

13. The method of claim 10, wherein generating symmetric association data comprises:

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

14. A system, comprising:

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;

generate symmetric association data representative of a symmetric association of a vertical category with at least one other vertical category based on the user identifier interest weights, the symmetric association being pairs of equal similarity measures where an equal similarity measure is based on a first similarity measure of a first vertical category relative to a second vertical category and a second similarity measure of the second vertical category relative to the first vertical category; and

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

15. The system of claim 14, 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, the asymmetric similarity measure being a similarity measure of a vertical category relative to another vertical category.

16. The system of claim 15, 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.

17. The system of claim 16, 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.

18. The system of claim 15, 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.

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

20. The system of claim 15, 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.