INFERENCE DETECTION ENABLED BY INTERNET ADVERTISING

• US 20100049682A1
• Filed: 08/20/2008
• Published: 02/25/2010
• Est. Priority Date: 08/20/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica N., Golle, Philippe Jean-Paul, Chow, Richard
• Granted Patent: US 10,311,445 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

One embodiment of the present invention provides a system that performs inference detection based on Internet advertisements. In doing so, this system first receives a set of topic words, performs a search query on each topic word using a search engine, and gathers a set of Uniform Resource Locators (URLs) associated with sponsored advertisement from the search results corresponding to each search query. Then, the system determines a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement, and produces a result which indicates groups of correlated topic words.

Claims

1. A computer-executed method for performing inference detection based on web advertisements, the method comprising:

receiving a set of topic words;

for each topic word, performing a search query on the topic word using an Internet search engine;

gathering a set of Uniform Resource Locators (URLs) associated with sponsored advertisement from the search results corresponding to each search query;

determining a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement; and

producing a result which indicates groups of correlated topic words.

2. The computer-executed method of claim 1, wherein determining a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement comprises:

generating a bipartite graph based on the topic words and the URLs associated with sponsored advertisement, wherein a first set of vertices of the bipartite graph is associated with one or more topic words, wherein a second set of vertices of the bipartite graph is associated with one or more URLs associated with sponsored advertisement, and wherein a respective edge of the bipartite graph associates an advertisement URL with a corresponding topic word;

generating a first collapsed graph from the bipartite graph by collapsing the vertices associated with the URLs for sponsored advertisement into a number of edges between topic words, wherein there exists an edge between two topic words in the first collapsed graph if the bipartite graph has edges between the corresponding topic words and an advertisement URL; and

clustering topic words into groups that are joined by at least a predetermined number of edges in the first collapsed graph.

3. The computer-executed method of claim 2, further comprising clustering the URLs associated with sponsored advertisement into groups by:

generating a second collapsed graph from the bipartite graph by collapsing the vertices associated with the topic words into a number of edges between URLs associated with sponsored advertisement, wherein there exists an edge between two URLs associated with sponsored advertisement in the second collapsed graph if the bipartite graph has edges between the corresponding URLs associated with sponsored advertisement and a topic word;

clustering the URLs associated with sponsored advertisement into groups that are joined by at least a predetermined number of edges in the second collapsed graph; and

producing a result which indicates the clusters of URLs associated with sponsored advertisement.

4. The computer-executed method of claim 1, wherein determining the correlation between two topic words based on their corresponding URLs associated with sponsored advertisement comprises:

using a similarity metric computation to rank pairs of topic words; and

clustering the topic words into groups whose similarity metric computation is greater than or equal to a predetermined value.

5. The computer-executed method of claim 4, wherein the similarity metric is computed based on a Jaccard index or a cosine similarity.

6. The computer-executed method of claim 1, wherein determining the correlation between two topic words based on their corresponding URLs associated with sponsored advertisement comprises:

gathering location-based information associated with a respective topic word from the URLs associated with sponsored advertisement; and

clustering the topic words into groups that have location-based information in common.

7. The computer-executed method of claim 6, wherein gathering location-based information from the URLs associated with sponsored advertisement comprises searching the title of the URLs associated with sponsored advertisement for location-based information associated with the respective topic word.

8. The computer-executed method of claim 7, wherein gathering location-based information from the URLs associated with sponsored advertisement comprises searching for location-based information in a web page referenced by the URLs associated with sponsored advertisement associated with the respective topic word.

9. The computer-executed method of claim 8, wherein the location-based information includes neighboring cities and neighboring points of interest related to the topic word.

10. The computer-executed method of claim 1, wherein a respective topic word corresponds to a product name, and wherein a respective group of topic words is associated with a group of related products.

11. The computer-executed method of claim 1, further comprising filtering the set of URLs associated with sponsored advertisement to remove URLs associated with sponsored advertisement produced by known aggregators.

12. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing inference detection from web advertisements, the method comprising:

receiving a set of topic words;

for each topic word, performing a search query on the topic word using an Internet search engine;

gathering a set of Uniform Resource Locators (URLs) associated with sponsored advertisement from the search results corresponding to each search query;

determining a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement; and

producing a result which indicates groups of correlated topic words.

13. The computer-readable storage medium of claim 12, wherein determining a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement comprises:

generating a bipartite graph based on the topic words and the URLs associated with sponsored advertisement, wherein a first set of vertices of the bipartite graph is associated with one or more topic words, wherein a second set of vertices of the bipartite graph is associated with one or more URLs associated with sponsored advertisement, and wherein a respective edge of the bipartite graph associates an advertisement URL with a corresponding topic word;

generating a first collapsed graph from the bipartite graph by collapsing the vertices associated with the URLs for sponsored advertisement into a number of edges between topic words, wherein there exists an edge between two topic words in the first collapsed graph if the bipartite graph has edges between the corresponding topic words and a URL associated with sponsored advertisement; and

clustering topic words into groups that are joined by at least a predetermined number of edges in the first collapsed graph.

14. The computer-readable storage medium of claim 13, wherein the method further comprises clustering the URLs associated with sponsored advertisement into groups by:

generating a second collapsed graph from the bipartite graph by collapsing the vertices associated with the topic words into a number of edges between URLs associated with sponsored advertisement, wherein there exists an edge between two URLs associated with sponsored advertisement in the second collapsed graph if the bipartite graph has edges between the corresponding URLs associated with sponsored advertisement and a topic word;

clustering the URLs associated with sponsored advertisement into groups that are joined by at least a predetermined number of edges in the second collapsed graph; and

producing a result which indicates the clusters of URLs associated with sponsored advertisement.

15. The computer-readable storage medium of claim 12, wherein determining the correlation between two topic words based on their corresponding URLs associated with sponsored advertisement comprises:

gathering location-based information associated with a respective topic word from URLs associated with sponsored advertisement by searching through the title of a respective advertisement URL or searching through a web page referenced by a respective advertisement URL; and

clustering the topic words into groups that have location-based information in common.

16. The computer-readable storage medium of claim 15, wherein the location-based information includes neighboring cities and neighboring points of interest related to the topic word.

17. The computer-readable storage medium of claim 12, wherein a respective topic word corresponds to a product name, and wherein a respective group of topic words is associated with a group of related products.

18. The computer-readable storage medium of claim 12, wherein the method further comprises filtering the set of URLs associated with sponsored advertisement to remove URLs produced by known aggregators.

19. An apparatus for performing inference detection from web advertisements, comprising:

a receiving mechanism configured to receive a set of topic words;

a search engine interface configured to perform, for each topic word, a search query on the topic word using an Internet search engine, and further configured to gather a set of Uniform Resource Locators (URLs) associated with sponsored advertisement from the search results corresponding to each search query;

an analysis mechanism configured to;

determine a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement; and

a result-presentation mechanism configured to produce a result which indicates groups of correlated topic words.

20. The apparatus of claim 19, wherein while determining a correlation between two topic words based on their corresponding URLs associated with sponsored advertisement, the analysis mechanism is configured to:

generate a bipartite graph based on the topic words and the URLs associated with sponsored advertisement, wherein a first set of vertices of the bipartite graph is associated with one or more topic words, wherein a second set of vertices of the bipartite graph is associated with one or more URLs associated with sponsored advertisement, and wherein a respective edge of the bipartite graph associates an advertisement URL with a corresponding topic word;

generate a first collapsed graph from the bipartite graph by collapsing the vertices associated with the URLs associated with sponsored advertisement into a number of edges between topic words, wherein there exists an edge between two topic words in the first collapsed graph if the bipartite graph has edges between the corresponding topic words and an advertisement URL;

determine the strong links in the first collapsed graph; and

create clusters of topic words by categorizing the topic words into groups that are joined by strong links in the first collapsed graph.

21. The apparatus of claim 20, wherein the analysis mechanism is further configured to cluster the URLs associated with sponsored advertisement into groups by:

generating a second collapsed graph from the bipartite graph by collapsing the vertices associated with the topic words into a number of edges between URLs associated with sponsored advertisement, wherein there exists an edge between two URLs associated with sponsored advertisement in the second collapsed graph if the bipartite graph has edges between the corresponding URLs associated with sponsored advertisement and a topic word;

determining the strong links in the second collapsed graph;

clustering the URLs associated with sponsored advertisement into groups that are joined by strong links in the second collapsed graph; and

producing a result which indicates the clusters of URLs associated with sponsored advertisement.

22. The apparatus of claim 19, wherein while determining the correlation between two topic words based on their corresponding URLs associated with sponsored advertisement, the analysis mechanism is configured to:

use a similarity metric computation to rank pairs of topic words; and

cluster the topic words into groups whose similarity metric computation is greater than or equal to a predetermined value.

23. The apparatus of claim 22, wherein the similarity metric is computed based on a Jaccard index or a cosine similarity.

24. The apparatus of claim 19, wherein while determining the correlation between two topic words based on their corresponding URLs associated with sponsored advertisement, the analysis mechanism is configured to:

gather location-based information associated with a respective topic word from URLs for sponsored advertisement by searching through the title of a respective advertisement URL or searching through a web page referenced by a respective advertisement URL; and

cluster the topic words into groups that have location-based information in common.

25. The apparatus of claim 24, wherein the location-based information includes neighboring cities and neighboring points of interest related to the topic word.

26. The apparatus of claim 19, wherein a respective topic word corresponds to a product name, and wherein a respective group of topic words is associated with a group of related products.

27. The apparatus of claim 19, wherein the analysis mechanism is further configured to filter the set of URLs associated with sponsored advertisement to remove URLs produced by known aggregators.