CHAIN UNDERSTANDING IN SEARCH

• US 20160321345A1
• Filed: 04/30/2015
• Published: 11/03/2016
• 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: Borisyuk, Fedor Vladimirovich, Neborisevic, Nikola, Jandrlic, Andrija, Marsenic, Nemanja, Todic, Nikola, Nevrekar, Siddhika
• Granted Patent: US 10,147,095 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

identifying entity data from the entity information corresponding to each of the plurality of geographic entities and storing the identified entity data of each geographic entity of the plurality of geographic entities in an entity record corresponding the geographic entity in a data store;

generating one or more groups of geographic entities from the plurality of entity records corresponding to geographic entities in the data store;

for each of the generated one or more groups of geographic entities;

determining a retaining similarity score for each of the geographic entities of a generated group of geographic entities, the retaining 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 retaining 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

establishing an entity chain in the data store for the generated group of geographic entities comprising to the geographic entities remaining in the generated group of geographic entities.

2. The computer-implemented method of claim 1, wherein generating one or more groups of geographic entities from the plurality of entity records corresponding to geographic entities in the data 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.

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 each of 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 retaining similarity score for each of the geographic entities of a generated group of geographic entities comprises determining retaining similarity score for each of 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 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 retaining similarity score is an aggregate retaining similarity score, the aggregate retaining 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 establishing an entity chain in the data store for the generated group of geographic entities comprises establishing an entity chain in the data store for the generated group of geographic entities upon determining that the generated group of geographic entities includes at least two geographic entities.

10. The computer-implemented method of claim 1, wherein establishing an entity chain in the data store for the generated group of geographic entities further comprises, for each of 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 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;

identifying geographic data from the entity information corresponding to each of the plurality of geographic entities and store the identified entity data of each geographic entity of the plurality of geographic entities in an entity record corresponding the geographic entity in the entity store;

generating one or more groups of geographic entities from the plurality of entity records corresponding to geographic entities in the entity store;

for each of the generated one or more groups of geographic entities;

determining a retaining similarity score for each of the geographic entities of a generated group of geographic entities, the retaining 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 retaining 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

establishing an entity chain in the entity store for the generated group of geographic entities comprising to the geographic entities remaining in the generated group 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 each of the geographic entities of a generated group of geographic entities comprises determining retaining similarity score for each of 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 each of 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 data regarding a plurality of geographic entities and stores entity records for each of the plurality of geographic entities in an entity store, each entity record comprising data regarding the geographic entity;

an entity chain identification component, wherein the entity chain identification component generates 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 generating 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 in the entity store; and

for each of the generated one or more groups of geographic entities;

determine a retaining similarity score for each of the geographic entities of a generated group of geographic entities, the retaining 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;

remove a geographic entity from the group of geographic entities where the retaining 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

establish an entity chain in the entity store for the generated group of geographic entities comprising to the geographic entities remaining in the generated group 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.