Chain understanding in search

• US 10,147,095 B2
• Filed: 04/30/2015
• Issued: 12/04/2018
• Est. Priority Date: 04/30/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Todic, Nikola, Borisyuk, Fedor Vladimirovich, Nebori{hacek over (s)}evic, Nikola, Jandrlic, Andrija, Marsenic, Nemanja, Nevrekar, Siddhika
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US14/701,486
• Publication Number:
  US 20160321345A1
• Time in Patent Office: 1,314 Days
• Field of Search: 707603
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products

Abstract

Methods and systems for generating and storing entity chain information, and for responding to search queries according to the entity chain information is presented. As a service obtains information regarding geographic entities, a plurality of entity records corresponding to each of a plurality of geographic entities is created (or updated) in an entity store. The service then analyzes the plurality of geographic entities (via the entity information in each of the entity records) to identify geographic entities that belong to an entity chain. Information regarding the identified entity chains are then also stored in the entity store.

Claims

1. A computer implemented method for generating entity chain information, the method comprising each of the following as implemented on a computing device including at least a processor, a memory, and a data store:

obtaining entity information regarding a plurality of geographic entities;

storing the obtained entity information of the plurality of geographic entities in an entity record corresponding to the geographic entity in a data store;

analyzing the entity information of the plurality of geographic entities to generate one or more groups of geographic entities wherein the analysis identifies data corresponding to the plurality of geographic entities and establishes one or more groups of geographic entities;

validating the generated one or more groups of geographic entities by determining a similarity score for the geographic entities of a generated group of geographic entities, the similarity score corresponding to the similarity of a geographic entity to the generated group of geographic entities to which it is grouped;

for each geographic entity of a group of geographic entities,

removing a geographic entity from the group of geographic entities where the similarity score for the geographic entity falls below a predetermined threshold of similarity for retaining the geographic entity in a predetermined group of geographic entities; and

identifying an entity chain for each generated group having at least two of the plurality of geographic entities remaining in a respective one of the plurality of geographic entities.

2. The computer implemented method of claim 1, wherein generating one or more groups of geographic entities wherein the analysis identifies data corresponding to the plurality of geographic entities and establishes one or more groups of geographic entities comprises:

determining a grouping similarity score between a first and a second geographic entity;

determining the grouping similarity score between the first and the second geographic entity exceeds a predetermined threshold of similarity for grouping geographic entities into a group; and

including the first geographic entity in a group of geographic entities with the second geographic entity.

3. The computer implemented method of claim 2, wherein determining the grouping similarity score between the first and the second geographic entities comprises:

accessing a plurality of entity attributes corresponding to the first and the second geographic entities from the data store; and

determining the grouping similarity score between the first and the second geographic entities according to the plurality of entity attributes.

4. The computer implemented method of claim 3, wherein the plurality of entity attributes includes any one or more of an entity name, an entity phone number, an entity category, an entity web site, and descriptive n-grams based on the keywords used in the entity'"'"'s web sites of the first and second geographic entities.

5. The computer implemented method of claim 1 further comprising:

determining dominant entity attributes of the generated group of geographic entities; and

wherein determining a similarity score for the geographic entities of a generated group of geographic entities comprises determining similarity score for the geographic entities of a generated group of geographic entities with regard to the dominant entity attributes of the generated group of geographic entities.

6. The computer implemented method of claim 5, wherein the dominant entity attributes of the generated group of geographic entities comprise any one or more of the following:

a dominant entity name, a dominant phone number, and a dominant entity category.

7. The computer implemented method of claim 6, wherein the dominant entity attributes of the generated group of geographic entities further comprises a plurality of dominant entity names, a plurality of dominant phone numbers, or a plurality of dominant entity categories.

8. The computer implemented method of claim 7, wherein the similarity score is an aggregate similarity score, the aggregate similarity score being generated according at least two of the dominant entity attributes of the generated group of geographic entities.

9. The computer implemented method of claim 8, wherein identifying an entity chain for each generated group having at least two of the plurality of geographic entities comprises identifying an entity chain for each generated group having at least two of the plurality of geographic entities upon determining that the generated group having at least two of the plurality of geographic entities includes at least two geographic entities.

10. The computer implemented method of claim 1, wherein identifying an entity chain for the generated group of geographic entities further comprises, for the at least two geographic entities, indicating in an entity record corresponding to a geographic entity in the data store that the geographic entity belongs to the entity chain.

11. A computer implemented method of a search engine for responding to a search query from a computer user, the method comprising each of the following as implemented on a computing device upon which the search engine operates, including at least a processor, and a memory:

providing an entity store, the entity store storing information regarding a plurality of geographic entities, and further comprising information regarding a plurality of entity chains, each entity chain comprising at least two geographic entities;

receiving a search query from a computer user, the search query identifying a query intent for which relevant search results are requested;

determining a set of search results relevant to the query intent of the search query from a content store of the search engine, the set of search results being an ordered set of search results;

determining whether the query intent of the search query is directed to a geographic entity, and upon determining that the query intent of the search query is directed to a geographic entity;

determining whether the geographic entity is part of an entity chain according to information from the entity store, and upon determining that the geographic entity is part of an entity chain;

obtaining information regarding the entity chain of which the geographic entity is a part; and

reordering the set of search results according to the obtained information regarding the entity chain;

generating a search results page according to the reordered set of search results; and

returning the generated search results page in response to the search query.

12. The computer implemented method of claim 11, wherein providing an entity store comprises:

obtaining entity information regarding a plurality of geographic entities;

storing the identified entity data of the plurality of geographic entities in an entity record corresponding to the geographic entity in the entity store;

analyzing the entity information of the entity records of the plurality of geographic entities to generate one or more groups of geographic entities wherein the analysis identifies data corresponding of the plurality of geographic entities and establishes one or more groups of geographic entities;

validating the generated one or more groups of geographic entities by

determining a similarity score for each of the geographic entities of a generated group of geographic entities, the similarity score corresponding to the similarity of a geographic entity the generated group of geographic entities to which it is grouped;

for each geographic entity of a group of geographic entities,

removing a geographic entity from the group of geographic entities where the similarity score for the geographic entity falls below a predetermined threshold of similarity for retaining the geographic entity in the predetermined group of geographic entities; and

identifying an entity chain for each generated group having at least two of the plurality of geographic entities remaining in a respective one of the plurality of geographic entities.

13. The computer implemented method of claim 12, wherein generating one or more groups of entity entities from the plurality of entity records corresponding to geographic entities in the entity store comprises:

determining a grouping similarity score between a first and a second geographic entity;

determining the grouping similarity score between the first and the second geographic entity exceeds a predetermined threshold of similarity for grouping geographic entities into a group; and

including the first geographic entity in a group of geographic entities with the second geographic entity.

14. The computer implemented method of claim 13, wherein determining the grouping similarity score between the first and the second geographic entities comprises:

accessing a plurality of entity attributes corresponding to each of the first and the second geographic entities from the entity store; and

determining the grouping similarity score between the first and the second geographic entities according to the plurality of entity attributes.

15. The computer implemented method of claim 14 further comprising:

determining dominant entity attributes of the generated group of geographic entities; and

wherein determining a retaining similarity score for the geographic entities of a generated group of geographic entities comprises determining retaining similarity score for the geographic entities of a generated group of geographic entities with regard to the dominant entity attributes of the generated group of geographic entities.

16. The computer implemented method of claim 15, wherein establishing an entity chain in the entity store for the generated group of geographic entities comprises establishing an entity chain in the entity store for the generated group of geographic entities upon determining that the generated group of geographic entities includes at least two geographic entities.

17. The computer implemented method of claim 16, wherein establishing an entity chain in the entity store for the generated group of geographic entities further comprises, for the at least two geographic entities, indicating in an entity record corresponding to a geographic entity in the entity store that the geographic entity belongs to the entity chain.

18. A computer system hosting a search engine for responding to a search query, the system comprising a processor and a memory, wherein the processor executes instructions stored in the memory as part of or in conjunction with additional components to respond to a search query, the additional components comprising:

a data acquisition component, wherein the data acquisition component obtains entity information regarding a plurality of geographic entities and stores the entity information for the plurality of geographic entities in an entity store as entity records;

an entity chain identification component, wherein the entity chain identification component identifies and stores entity chain information in the entity store;

a search results component, wherein the search results component is configured to obtain search results from a content store and the entity store when the query topic of the search query is directed to a geographic entity; and

a search results page generator, wherein the search results page generator generates a search results page according to the search results obtained from the search results component in response to the search engine receiving a search query.

19. The computer system of claim 18, wherein in identifying entity chain information and storing the identified entity chain information in the entity store, the entity chain identification component is configured to:

generate one or more groups of geographic entities from the plurality of entity records corresponding to the plurality of geographic entities; and

validating the generated one or more groups of geographic entities by;

determining a similarity score for the geographic entities of a generated group of geographic entities, the similarity score corresponding to the similarity of a geographic entity the generated group of geographic entities to which it is grouped;

for each geographic entity of a group of geographic entities,

removing a geographic entity from the group of geographic entities where the similarity score for the geographic entity falls below a predetermined threshold of similarity for retaining the geographic entity in the predetermined group of geographic entities; and

identifying an entity chain for each generated group having at least two of the plurality of geographic entities remaining in a respective one of the plurality of geographic entities.

20. The computer system of claim 18, wherein in generating one or more groups of geographic entities from the plurality of entity records corresponding to the plurality of geographic entities in the entity store the entity chain identification component is further configured to:

determine a grouping similarity score between a first and a second geographic entity;

determine the grouping similarity score between the first and the second geographic entity exceeds a predetermined threshold of similarity for grouping geographic entities into a group; and

include the first geographic entity in a group of geographic entities with the second geographic entity.