Category generalization for search queries

• US 8,983,956 B1
• Filed: 03/15/2013
• Issued: 03/17/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Murphy, Bruce Winston, Perrow, Michael Steven, Lu, Yifei, Carattini, Kendra Jay
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US13/839,953
• Time in Patent Office: 732 Days
• Field of Search: 707/708, 707/731, 707/736, 707/763, 707/771, 707/803
• US Class Current: 707/736
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0261 based on user location

Abstract

A system and computer-implemented method are provided for associating categories with business names for generalizing search queries, the method including identifying one or more businesses within a first geographic region, determining a business name and one or more categories for each of the one or more businesses, generating one or more name components for each of the one or more businesses from the name of the business, generating one or more name component groups from the name components of the one or more businesses, each name component group including one or more identical name components, determining for each name component group, if the one or more name components within the name component group are associated with businesses that share one or more common categories and associating the one or more common categories with the name component of the name component group.

Claims

1. A computer-implemented method for associating categories with business names for generalizing search queries, the method comprising:

identifying, using one or more computing devices, one or more businesses within a first geographic region;

determining, using the one or more computing devices, a business name and one or more categories associated with each of the one or more businesses;

generating, using the one or more computing devices, one or more name components for each of the one or more businesses, each name component comprising a subset of the business name of the business;

generating, using the one or more computing devices, one or more name component groups from the name components of the one or more businesses, wherein each name component group comprises one or more identical name components;

determining, using the one or more computing devices, for each name component group, if the one or more name components within the name component group are associated with businesses that share one or more common categories; and

associating, using the one or more computing devices, the one or more common categories with the name component of the name component group, when the one or more name components within the name component group share one or more common categories.

2. The method of claim 1, further comprising:

discarding the one or more name components of the name component group if the one or more name components within the name component group do not share one or more common categories.

3. The method of claim 1, wherein generating the one or more name components comprises generating all proper pre-fixes of the business name.

4. The method of claim 1, wherein generating the one or more name components comprises generating all proper post-fixes of the business name.

5. The method of claim 1, wherein the one or more name components comprises the business name.

6. The method of claim 1, wherein generating the one or more name component groups comprises:

determining if a name component group represented by the name component exists;

generating a name component group represented by the name component if the a name component group represented by the name component does not exist; and

adding the name component to the name component group represented by the name component.

7. The method of claim 1, further comprising:

associating each of one or more name components of a business with the one or more categories associated with the business.

8. The method of claim 1, wherein the determining if all name components within the name component group share one or more common categories comprises:

determining if a name component group includes more than one name component;

identifying the one or more categories for the name component as the one or more common categories if the name component group does not include more than one component;

comparing one or more categories associated with each of the name components to the one or more categories associated with other name components of the name component group if the name component group includes more than one name component.

9. The method of claim 8, the comparing further comprising:

determining if each name component of the name component group is associated with at least one category;

determining if all of the one or more components are associated with the same one or more categories if each name component is associated with at least one category;

identifying the one or more categories as one or more common categories for the name component group if all of the one or more components are associated with the same one or more categories;

identifying one or more related categories for each of the one or more categories of the one or more name components of the name component group if each name component of the name component group is associated with at least one category;

determining if all of the one or more components are associated with the same one or more categories if each name component is associated with at least one category; and

identifying the one or more categories as one or more common categories.

10. The method of claim 8, wherein the one or more common categories comprise one of a category associated with a name component of the one or more name components or a parent category of a category associated with a name component of the one or more name components of a name component group.

11. The method of claim 1, wherein generating one or more name component groups from the name components of the one or more businesses comprises:

determining that a first name component of the name component group is associated with a business with low prominence and discarding the name component from the name component group.

12. The method of claim 1, further comprising:

receiving a listing of businesses, each business having a business location, name and one or more categories associated with the business;

generating one or more geographic regions including the first geographic region, each geographic region comprising a portion of the entire area including the location of the businesses of the listing; and

associating each business with one of the one or more geographic regions, when the business location is determined to be within the one of the one or more geographic regions.

13. The method of claim 1, further comprising:

receiving an indication of a search query from a user containing one or more search terms or phrases;

identifying the location of the user;

determining a geographic region containing the location of the user;

determining a set of name components associated with businesses within the geographic region;

comparing the one or more search terms or phrases to the set of name components;

finding at least a first name component matching at least one of the one or more search terms or phrases;

identifying one or more categories associated with the first name component; and

providing the one or more categories for inclusion within the query.

15. The system of claim 12, the operations further comprising:

for each generated name component group;

determining if the name component group includes only one name component;

generating a mapping of the name component and the one or more categories associated with the name component if the name component group includes only one name component.

16. The system of claim 12, the operations further comprising:

for each generated name component group;

determining if the name component group includes more than one name component;

identifying the one or more categories associated with each name component of the name component group;

comparing the one or more categories associated with each of the name components of the name component group to one another to determine if the name components include at least one common category; and

generating a mapping of the at least one common category and the name component represented by the name component group.

17. The system of claim 12, the operations further comprising:

wherein the one or more categories associated with each of the one or more businesses is a node in a hierarchical tree of increasingly generalized categories, and wherein each of the one or more common categories comprise one of a category associated with a name component of the one or more name components or a parent category of a category associated with a name component of the one or more name components of the name component group.

14. A system for associating categories with business names for generalizing search queries, the system comprising:

one or more processors; and

a machine-readable medium comprising instructions stored therein, which when executed by the processors, cause the processors to perform operations comprising;

identifying a first geographic region, the first geographic region being defined as a defined area including a set of locations;

identifying one or more businesses having a location of the set of locations;

determining a business name and one or more categories associated with each of the one or more businesses;

generating one or more name components based on the business name for each of the one or more businesses, the one or more name components comprising one or more of the business name, proper pre-fixes of the business name and proper post-fixes of the business name;

associating the one or more categories for each of the one or business with the one or more name components for the business;

for each name component of each of the one or more businesses;

determining if a name component group represented by the name component exists;

generating a name component group represented by the name component group if the name component group does not exist; and

adding the name component to the name component group represented by the name component.

18. A machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

determining a business name and one or more categories associated with each of one or more businesses;

generating one or more name components based on the business name for each of the one or more businesses, each name component of a business comprising one of the business name or a component of the business name;

associating the one or more categories for each of the one or businesses with the one or more name components for the business;

determining if a name component of a business of the one or more businesses is similar to at least another name component of another business of the one or more businesses;

mapping the one or more categories of the name component of the one or more name components that is not similar to at least another name component of the one or more name components with the one or more categories associated with the name component;

determining if the name component and one or more other components of the one or more name components that are similar to the name component share one or more common categories, if a name component of the one or more name components is similar to at least another name component of the one or more name components; and

mapping the name component to the one or more common categories if the name component and one or more other components of the one or more name components that are similar to the name component share one or more common categories.

19. The machine-readable medium of claim 18, the operations further comprising:

discarding the name component if the name component and one or more other components of the one or more name components that are similar to the name component do not share one or more common categories.

20. The machine-readable medium of claim 18, determining if the name component and one or more other components of the one or more name components that are similar to the name component share one or more common categories comprises:

determining a set of categories for each of name component and the one or more name components that are similar to the name component, the set of categories including the one or more categories associated with the name component and one or more categories that are related to the one or more categories associated with the name components;

comparing the categories with the set of categories for the name component and the one or more name components that are similar to the name component.