Categorizing objects, such as documents and/or clusters, with respect to a taxonomy and data structures derived from such categorization

• US 8,918,395 B2
• Filed: 06/20/2012
• Issued: 12/23/2014
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gehrking, David, Law, Ching, Maxwell, Andrew
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US13/528,197
• Publication Number:
  US 20120259856A1
• Time in Patent Office: 916 Days
• Field of Search: 707/730, 707/738, 707/739, 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A Website may be automatically categorized by (a) accepting Website information, (b) determining a set of scored clusters (e.g., semantic, term co-occurrence, etc.) for the Website using the Website information, and (c) determining at least one category (e.g., a vertical category) of a predefined taxonomy using at least some of the set of clusters.

Claims

1. A computer-implemented method to associate a semantic cluster with one or more categories of a predefined taxonomy, the method comprising:

a) accepting, by a computer system including at least one computer, a plurality of semantic clusters of re-occurring terms within a document, and having a frequency based on the reoccurrence of the term;

b) identifying, by the computer system based on the accepted clusters of re-occurring terms within the document, one or more concepts for the document, each concept identifying different re-occurring terms having identical meanings;

c) scoring, by the computer system, the identified one or more concepts, the score of each of the one or more concepts weighted by cluster frequency of each of the re-occurring terms identified by said concept;

d) identifying, by the computer system, a set of one or more categories using at least some of the one or more scored concepts to look up one or more categories in a concept-category index, wherein a category corresponds to a node of the predefined taxonomy, which defines a structured set of categories; and

e) associating, by the computer system, at least some of the one or more categories with the semantic cluster.

2. The computer-implemented method of claim 1 wherein the semantic cluster is a term co-occurrence cluster in which terms that tend to co-occur in at least one of (A) search sessions on search engine, or (B) documents available on the World Wide Web, are grouped together under a semantic cluster.

3. The computer-implemented method of claim 1 wherein the semantic cluster includes terms that tend to co-occur in a search session on a search engine.

4. The computer-implemented method of claim 1 wherein the semantic cluster includes terms that tend to co-occur in documents available on the World Wide Web.

5. The computer-implemented method of claim 1 wherein the act of associating at least some of the one or more categories with the semantic cluster includes generating and storing an index entry which maps the semantic cluster to each of the at least some of the one or more categories.

6. The computer-implemented method of claim 1 wherein categories of the predefined taxonomy correspond to at least one of (A) related products that are likely to be found in Website content, (B) related services that are likely to be found in Website content, (C) related industries that are likely to be found in Website content, and (D) related topics that are likely to be found in Website content.

12. The method of claim 1, wherein identifying a set of one or more categories using at least some of the one or more scored concepts to look up one or more categories in a concept-category index further comprises determining a score for each of the set of one or more categories based on a sum of values including (1) an intra-category cluster score of the category, and (2) intra-category cluster scores of categories that are descendants of the category in the hierarchical taxonomy.

13. The method of claim 1, wherein identifying a set of one or more scored concepts using the accepted cluster to look up one or more concepts in a cluster-concept index further comprises comparing a score of each of the one or more scored concepts to a threshold and identifying the set of one or more scored concepts with scores above the threshold.

7. A computer-implemented method to associate a property with one or more categories of a predefined taxonomy, the method comprising:

a) accepting, by a computer system including at least one computer, information about the property;

b) identifying, by the computer system, a set of one or more scored semantic clusters using the accepted property information, wherein each of the one or more scored semantic clusters comprise a re-occurring term within (A) a search session on a search engine, or (B) a document available on the World Wide Web, at a frequency based on the reoccurrence;

c) identifying, by the computer system based on the identified scored semantic clusters of re-occurring terms within the search session or document, one or more concepts for the property, each concept identifying different re-occurring terms having identical meanings;

d) scoring, by the computer system, the identified one or more concepts, the score of each of the one or more concepts weighted by cluster frequency of each of the re-occurring terms identified by said concept;

e) identifying, by the computer system, a set of one or more categories according to the scores of the one or more concepts; and

f) associating, by the computer system, at least some of the one or more categories with the property.

8. The computer-implemented method of claim 7 wherein the property is a Webpage.

9. The computer-implemented method of claim 7 wherein the property is a Website including a plurality of Webpages.

10. The computer-implemented method of claim 7 wherein the act of associating at least some of the one or more categories with the property includes generating and storing an index entry which maps property information to each of the at least some of the one or more categories.

11. The computer-implemented method of claim 7 wherein categories of the predefined taxonomy correspond to at least one of (A) related products that are likely to be found in Website content, (B) related services that are likely to be found in Website content, (C) related industries that are likely to be found in Website content, (D) related topics that are likely to be found in Website content, and (E) related content formats that are likely to be found in Website content.