# US 10,311,445 B2 · Inference detection enabled by internet advertising > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,445 B2 - Document ID: US10311445B2 - Status: Granted - Kind: B2 - Application number: 12/194,920 - Filed: 2008-08-20 - Published: 2010-02-25 - Granted: 2019-06-04 - Earliest claimed: 2008-08-20 - Assignees: Palo Alto Research Center Incorporated - Applicants: Richard Chow; Philippe Jean-Paul Golle; Jessica N. Staddon - Inventors: Richard Chow; Philippe Jean-Paul Golle; Jessica N. Staddon - Web page: https://patentgrep.com/patent/US10311445B2 ## CPC - G06Q 30/02: Marketing; Price estimation or determination; Fundraising - G06Q 30/0631: {Recommending goods or services} - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## 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 ### Claim 1 A computer-executed method, comprising: receiving, by a computing device, a set of words from an end-user; for each word in the received set, performing a search query on the word over a computer network using an Internet search engine; receiving, by the computing device and from the Internet search engine over the computer network, search results corresponding to at least a first word and a second word in the set of words; identifying a first set of sponsored Uniform Resource Locators (URLs) from a search result corresponding to the first word; identifying a second set of sponsored URLs from a search result corresponding to the second word; generating a bipartite graph based on the words and the sponsored URLs identified from the search results of the words, wherein a first set of vertices of the bipartite graph is associated with one or more of the words, wherein a second set of vertices of the bipartite graph is associated with one or more of the sponsored URLs, and wherein a respective edge of the bipartite graph maps a sponsored URL to a word; generating a first collapsed graph from the bipartite graph by collapsing the vertices associated with the sponsored URLs into a set of edges between words, wherein there exists an edge between two words in the first collapsed graph for a pair of words that are coupled to a common sponsored URL through corresponding edges of the bipartite graph; and responsive to determining that a number of edges coupling the first word and the second word in the first collapsed graph exceeds a predetermined plural threshold, indicating in a result that the first word and the second word are related. ### Claim 2 (depends on 1) The computer-executed method of claim 1, further comprising: clustering words into groups that are joined by at least a predetermined number of edges in the first collapsed graph. ### Claim 3 (depends on 2) The computer-executed method of claim 2, further comprising clustering the sponsored URLs into groups by: generating a second collapsed graph from the bipartite graph by collapsing the vertices associated with the words into a number of edges between sponsored URLs, wherein there exists an edge between two sponsored URLs in the second collapsed graph if the bipartite graph has edges between the corresponding sponsored URLs and a word; clustering the sponsored URLs 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 sponsored URLs. ### Claim 4 (depends on 1) The computer-executed method of claim 1, further comprising: using a similarity metric computation to rank pairs of words; and clustering the words into groups whose similarity metric computation is greater than or equal to a predetermined value. ### Claim 5 (depends on 4) The computer-executed method of claim 4, wherein the similarity metric is computed based on a Jaccard index or a cosine similarity. ### Claim 6 (depends on 1) The computer-executed method of claim 1, further comprising: gathering location-based information associated with a respective word from the sponsored URLs; and clustering the words into groups that have location-based information in common. ### Claim 7 (depends on 6) The computer-executed method of claim 6, wherein gathering location-based information from the sponsored URLs comprises searching the title of the sponsored URLs for location-based information associated with the respective word. ### Claim 8 (depends on 7) The computer-executed method of claim 7, wherein gathering location-based information from the sponsored URLs comprises searching for location-based information in a web page referenced by the sponsored URLs associated with the respective word. ### Claim 9 (depends on 8) The computer-executed method of claim 8, wherein the location-based information includes neighboring cities and neighboring points of interest related to the word. ### Claim 10 (depends on 1) The computer-executed method of claim 1, wherein a respective word corresponds to a product name, and wherein a respective group of words is associated with a group of related products. ### Claim 11 (depends on 1) The computer-executed method of claim 1, further comprising filtering the set of sponsored URLs to remove a URL produced by a known aggregator. ### Claim 12 A non-transitory 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 from an end-user; for each topic word in the received set, performing a search query on the topic word over a computer network using an Internet search engine; receiving, by the computing device and from the Internet search engine over the computer network, search results corresponding to at least a first topic word and a second topic word in the set of topic words; identifying a first set of sponsored advertisement Uniform Resource Locators (URLs) from a search result corresponding to the first topic word; identifying a second set of sponsored advertisement URLs from a search result corresponding to the second topic word; generating a bipartite graph based on the topic words and the sponsored advertisement URLs identified from the search results of the topic words, wherein a first set of vertices of the bipartite graph is associated with one or more of the topic words, wherein a second set of vertices of the bipartite graph is associated with one or more sponsored advertisement URLs, and wherein a respective edge of the bipartite graph maps a sponsored advertisement URL to an associated topic word; generating a first collapsed graph from the bipartite graph by collapsing the vertices associated with the sponsored advertisement URLs into a set of edges between topic words, wherein there exists an edge between two topic words in the first collapsed graph for a pair of topic words that are coupled to a common sponsored advertisement URL through corresponding edges of the bipartite graph; and responsive to determining that a number of edges coupling the first topic word and the second topic word in the first collapsed graph exceeds a predetermined plural threshold, producing a result which indicates the first topic word and the second topic word as being related. ### Claim 13 (depends on 12) The computer-readable storage medium of claim 12, wherein the method further comprises: clustering topic words into groups that are joined by at least a predetermined number of edges in the first collapsed graph. ### Claim 14 (depends on 13) The computer-readable storage medium of claim 13, wherein the method further comprises clustering the sponsored advertisement URLs 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 sponsored advertisement URLs, wherein there exists an edge between two sponsored advertisement URLs in the second collapsed graph if the bipartite graph has edges between the corresponding sponsored advertisement URLs and a topic word; clustering the sponsored advertisement URLs 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 sponsored advertisement URLs. ### Claim 15 (depends on 12) The computer-readable storage medium of claim 12, wherein the method further comprises: gathering location-based information associated with a respective topic word from sponsored advertisement URLs by searching through the title of a respective sponsored advertisement URL or searching through a web page referenced by a respective sponsored advertisement URL; and clustering the topic words into groups that have location-based information in common. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 12) 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. ### Claim 18 (depends on 12) The computer-readable storage medium of claim 12, wherein the method further comprises filtering the set of sponsored advertisement URLs to remove a URL produced by a known aggregator. ### Claim 19 An apparatus for performing inference detection from web advertisements, comprising: a processor; a memory; a non-transitory computer-readable storage medium coupled to the processor storing instructions that, when executed by the processor, cause the apparatus to perform a method comprising: receiving a set of topic words from an end-user; for each topic word in the received set, performing a search query on the topic word over a computer network using an Internet search engine; receiving, by the computing device and from the Internet search engine over the computer network, search results corresponding to at least a first topic word and a second topic word in the set of topic words; identifying a first set of sponsored advertisement Uniform Resource Locators (URLs) from a search result corresponding to the first topic word; identifying a second set of sponsored advertisement URLs from a search result corresponding to the second topic word; generating a bipartite graph based on the topic words and the sponsored advertisement URLs identified from the search results of the topic words, wherein a first set of vertices of the bipartite graph is associated with one or more of the topic words, wherein a second set of vertices of the bipartite graph is associated with one or more sponsored advertisement URLs, and wherein a respective edge of the bipartite graph maps a sponsored advertisement URL to an associated topic word; generating a first collapsed graph from the bipartite graph by collapsing the vertices associated with the sponsored advertisement URLs into a set of edges between topic words, wherein there exists an edge between two topic words in the first collapsed graph for a pair of topic words that are coupled to a common sponsored advertisement URL through corresponding edges of the bipartite graph; and responsive to determining that a number of edges coupling the first topic word and the second topic word in the first collapsed graph exceeds a predetermined plural threshold, producing a result which indicates the first topic word and the second topic word as being related. ### Claim 20 (depends on 19) The apparatus of claim 19, wherein the method further comprises: determining one or more strong links in the first collapsed graph; and creating clusters of topic words by categorizing the topic words into groups that are joined by strong links in the first collapsed graph. ### Claim 21 (depends on 20) The apparatus of claim 20, wherein the method further comprises clustering the sponsored advertisement URLs 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 sponsored advertisement URLs, wherein there exists an edge between two sponsored advertisement URLs in the second collapsed graph if the bipartite graph has edges between the corresponding sponsored advertisement URLs and a topic word; determining one or more strong links in the second collapsed graph; clustering the sponsored advertisement URLs into groups that are joined by strong links in the second collapsed graph; and producing a result which indicates the clusters of sponsored advertisement URLs. ### Claim 22 (depends on 19) The apparatus of claim 19, wherein the method further 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. ### Claim 23 (depends on 19) The apparatus of claim 19, wherein the method further comprises: gathering location-based information associated with a respective topic word from sponsored advertisement URLs by searching through the title of a respective sponsored advertisement URL or searching through a web page referenced by a respective sponsored advertisement URL; and clustering the topic words into groups that have location-based information in common. ### Claim 24 (depends on 23) The apparatus of claim 23, wherein the location-based information includes neighboring cities and neighboring points of interest related to the topic word. ### Claim 25 (depends on 19) 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. ### Claim 26 (depends on 19) The apparatus of claim 19, where the method further comprises filtering the set of sponsored advertisement URLs to remove a URL produced by a known aggregator. ### Claim 27 (depends on 1) The method of claim 1, further comprising: determining that a user has an interest in a first item, wherein the first item is associated with the first word; and recommending a second item to the user, wherein the second item is associated with the second word.