Systems and methods for identifying hierarchical relationships

• US 8,984,006 B2
• Filed: 11/07/2012
• Issued: 03/17/2015
• Est. Priority Date: 11/08/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yu, Chai, Yixin, Chu, Fang, Fu, Ting, Choi, Sean Wonjoon, Lai, Guangda, Fang, Liu, Liu, Li, Li, Ruohao
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US13/670,819
• Publication Number:
  US 20130117253A1
• Time in Patent Office: 860 Days
• Field of Search: 707/625, 707/649, 707/655, 707/672, 707/673, 707/688, 707/690, 707/696, 707/703, 707/778, 707/802, 707/829, 707/956, 707/999.008, 707/999.201, 707/999.1, 707/999.106
• US Class Current: 707/778
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

Embodiments include a computer-implemented method that includes identifying a candidate parent entity having one or more characteristics indicative of the entity having a parent hierarchical relationship to another entity of an entity set, identifying a candidate child entity set including entities of the entity set that each have one or more characteristics indicative of the entity having a child hierarchical relationship to the candidate parent entity, comparing characteristics of the candidate parent entity to characteristics of an entity of the candidate child entity set to determine whether a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set, determining that a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set, and updating a hierarchical index to reflect the hierarchical relationship between the candidate parent entity and the entity of the candidate child entity set.

Claims

1. A computer-implemented method comprising:

identifying, by one or more processors, a candidate parent entity from an entity set, wherein the entity set comprises a plurality of entities, and wherein the candidate parent entity comprises an entity identified as having one or more characteristics indicative of the entity having a parent hierarchical relationship to another entity of the entity set;

identifying, by the one or more processors, a candidate child entity set from the entity set, wherein the candidate child entity set comprises entities of the entity set that are each identified as having one or more characteristics indicative of the entity having a child hierarchical relationship to the candidate parent entity; and

for each entity of the candidate child entity set;

comparing, by the one or more processor, characteristics of the candidate parent entity to characteristics of the entity of the candidate child entity set to determine whether a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set; and

in response to determining that a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set, updating, by the one or more processors, a hierarchical index to reflect the hierarchical relationship between the candidate parent entity and the entity of the candidate child entity set.

2. The method of claim 1, wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a classification corresponding to a parent entity.

3. The method of claim 1, further comprising identifying a classification hierarchical relationship specifying a parent classification and a child classification, wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a classification corresponding to the parent classification, and wherein identifying a candidate child entity set comprises identifying entities of the entity set having a classification corresponding to the child classification.

4. The method of claim 1, wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a geometry corresponding to a parent entity.

5. The method of claim 1, wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a polygon geometry.

6. The method of claim 1, wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a descriptor including one or more keywords corresponding to a parent entity.

7. The method of claim 1, further comprising:

identifying a classification hierarchical relationship specifying a parent classification and a child classification;

identifying one or more keywords associated with the parent classification; and

identifying one or more keywords associated with the child classification,

wherein identifying a candidate parent entity comprises identifying an entity of the entity set having a descriptor comprising at least one of the one or more keywords associated with the parent classification, and wherein identifying a candidate child entity set comprises identifying entities of the entity set having a descriptor comprising at least one of the one or more keywords associated with the child classification.

8. The method of claim 7, wherein identifying one or more keywords associated with the parent classification comprises:

identifying a set of seed keywords associated with the parent classification;

identifying a seed entity set comprising entities having descriptors that comprise one or more of the seed keywords associated with the parent classification; and

assessing descriptors of the entities of the seed entity set to identify an expanded set of keywords, wherein the one or more keywords associated with the parent classification comprise the seed keywords and the expanded set of keywords.

9. The method of claim 7, wherein identifying one or more keywords associated with the child classification comprises:

identifying a set of seed keywords associated with the child classification;

identifying a seed entity set comprising entities having descriptors that comprise one or more of the seed keywords associated with the child classification; and

assessing descriptors of the entities of the seed entity set to identify an expanded set of keywords, wherein the one or more keywords associated with the child classification comprise the seed keywords and the expanded set of keywords.

10. The method of claim 1, wherein identifying a candidate child entity set comprises identifying entities of the entity set having an address that includes a descriptor of the candidate parent entity.

11. The method of claim 1, wherein identifying a candidate child entity set comprises identifying entities of the entity set having a location that is within a threshold distance of the candidate parent entity.

12. The method of claim 1, wherein identifying a candidate child entity set comprises identifying entities of the entity set having a location that is within a geographic area associated with the candidate parent entity.

13. The method of claim 1, wherein identifying a candidate child entity set comprises identifying entities of the entity set having a physical address that is the same or similar to the address of the candidate parent entity.

14. The method of claim 1, wherein comparing characteristics of the candidate parent entity to characteristics of the entity to determine whether a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set comprises:

scoring the candidate parent entity and the entity of the candidate child entity set via application of a plurality of scoring criteria to attributes of the candidate parent entity and attributes of the entity of the candidate child entity set, each of the scoring criteria associated with a score that is assigned to an entity that satisfies the scoring criteria;

determining a first score comprising a sum of scores assigned to the candidate parent entity;

determining a second score comprising a sum of scores assigned to the entity of the candidate child entity set;

determining that the first score is greater than the second score; and

in response to determining that the first score is greater than the second score, determining that the candidate parent entity is a parent of the entity of the candidate child entity set.

15. The method of claim 14, wherein the plurality of scoring criteria comprises at least one of the following:

an entity having an entity identifier that is contained in an address of the other entity such that, in response to determining that the candidate parent entity has an entity identifier that is contained in an address of the entity of the candidate child entity set, a score corresponding to the scoring criteria is assigned to the candidate parent entity or, in response to determining that the entity of the candidate child entity set has an entity identifier that is contained in an address of the candidate parent entity, the score corresponding to the scoring criteria is assigned to the entity of the candidate child entity set;

an entity having an entity identifier that is contained in an entity identifier of the other entity such that, in response to determining that the candidate parent entity has an entity identifier that is contained in an entity identifier of the entity of the candidate child entity set, a score corresponding to the scoring criteria is assigned to the candidate parent entity or, in response to determining that the entity of the candidate child entity set has an entity identifier that is contained in an entity identifier of the candidate parent entity, the score corresponding to the scoring criteria is assigned to the entity of the candidate child entity set;

an entity associated with the highest number of impressions such that, in response to determining that the candidate parent entity is associated with a greater number of impressions than the entity of the candidate child entity set is associated with, a score corresponding to the scoring criteria is assigned to the candidate parent entity or, in response to determining that the entity of the candidate child entity set is associated with a greater number of impressions than the candidate parent entity is associated with, a score corresponding to the scoring criteria is assigned to the entity of the candidate child entity set; and

an entity comprising an entity identifier comprising keywords associated with a parent entity such that, in response to determining that the candidate parent entity has an entity identifier comprising a keyword associated with a parent entity, a score corresponding to the scoring criteria is assigned to the candidate parent entity or, in response to determining that the entity of the candidate child entity set has an entity identifier comprising a keyword associated with a parent entity, a score corresponding to the scoring criteria is assigned to the entity of the candidate child entity set.

16. The method of claim 1 further comprising:

receiving a search query;

processing the search query to identify a set of search results;

comparing the set of search results to the hierarchical index to determine whether the set of search results comprises a parent search result corresponding to a parent entity;

determining that the set of search results comprises a parent search result corresponding to a parent entity;

in response to determining that the set of search results comprises a parent search result corresponding to a parent entity, identifying a set of child search results comprising one or more child search results that correspond to one or more entities that are children of the parent entity; and

providing a hierarchical search results list for display, the hierarchical search results list comprising;

a first listing of search results corresponding to the set of search results; and

a second listing of search results corresponding to the set of child search results, the second listing configured to be displayed in hierarchical relation to a displayed search result corresponding to the parent search result of the set of search results.

17. The method of claim 1, wherein the entity set comprises entities corresponding to an indexed listing of entities generated based on crawling of Internet websites.

18. The method of claim 1, wherein the entity set comprises entities corresponding to places having a geographic location associated therewith.

19. A non-transitory computer readable storage medium having computer-executable program instructions stored thereon that are executable by a computer to cause the following:

identifying a candidate parent entity from an entity set, wherein the entity set comprises a plurality of entities, and wherein the candidate parent entity comprises an entity having one or more characteristics indicative of the entity having a parent hierarchical relationship to another entity of the entity set;

identifying a candidate child entity set from the entity set, wherein the candidate child entity set comprises entities of the entity set that are each identified as having one or more characteristics indicative of the entity having a child hierarchical relationship to the candidate parent entity; and

for each entity of the candidate child entity set;

comparing characteristics of the candidate parent entity to characteristics of the entity of the candidate child entity set to determine whether a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set; and

in response to determining that a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set, updating a hierarchical index to reflect the hierarchical relationship between the candidate parent entity and the entity of the candidate child entity set.

20. A system comprising:

one or more memories storing instructions; and

one or more processors coupled to the one or more memories and executing the instructions stored thereon in order to perform the following steps;

identifying a candidate parent entity from an entity set, wherein the entity set comprises a plurality of entities, and wherein the candidate parent entity comprises an entity having one or more characteristics indicative of the entity having a parent hierarchical relationship to another entity of the entity set;

identifying a candidate child entity set from the entity set, the candidate child entity set comprises entities of the entity set that are identified as having one or more characteristics indicative of the entity having a child hierarchical relationship to the candidate parent entity; and

for each entity of the candidate child entity set;

comparing characteristics of the candidate parent entity to characteristics of the entity of the candidate child entity set to determine whether a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set; and

in response to determining that a hierarchical relationship exists between the candidate parent entity and the entity of the candidate child entity set, updating a hierarchical index to reflect the hierarchical relationship between the candidate parent entity and the entity of the candidate child entity set.