SEARCHING HETEROGENEOUS INTERRELATED ENTITIES

• US 20080215565A1
• Filed: 09/11/2007
• Published: 09/04/2008
• Est. Priority Date: 03/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Ning, Chen, Zheng, Wang, Xuanhui, Sun, Jian-Tao, Wang, Jian
• Granted Patent: US 7,849,104 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Systems and methods for searching heterogeneous interrelated entities for a heterogeneous entities search query are disclosed herein. A user may enter the heterogeneous entities search query. The search retrieves and returns multiple types of heterogeneous entities. The retrieved heterogeneous interrelated entities are searched in a unified matrix that represents relationships between one or more heterogeneous entities. The retrieved heterogeneous interrelated entities may have one or more entity types. The set of retrieved interrelated entities may also be ranked based on the similarity between each entity and the search query. Feedback may also be incorporated into the system to improve search accuracy.

Claims

1. A method for searching heterogeneous interrelated entities comprising:

receiving a heterogeneous interrelated entities search query;

searching for a set of heterogeneous interrelated entities having a plurality of entity types in a unified space in response to the search query, wherein the unified space is based on relationships between multiple heterogeneous entities; and

presenting the set of heterogeneous interrelated entities as results of the search.

2. The method of claim 1, wherein the searching further comprises:

retrieving the results of the search from the unified space based on the heterogeneous entities search query, wherein the heterogeneous entities search query comprises one or more heterogeneous entities of which one or more entities have different entity types.

3. The method of claim 1, further comprising representing the multiple heterogeneous entities having a plurality of entity types in the unified space.

4. The method of claim 3, wherein representing the multiple heterogeneous entities having a plurality of entity types in the unified space comprises:

constructing a multiple-type graph for one or more heterogeneous entity types;

extracting co-occurrence matrices from the multiple-type graph, the extracting based on interactions between pairs of entity types;

forming one or more entity vectors for each heterogeneous entity based on the co-occurrence matrices; and

concatenating the entity vectors of the heterogeneous entities to form a unified matrix, wherein the unified matrix represents the unified space.

5. The method of claim 4, wherein constructing the multiple-type graph for one or more heterogeneous entity types comprises:

identifying a set of vertices corresponding to a set of entity types; and

identifying a set of edges corresponding to a set of interaction relationships between the entity types.

6. The method of claim 4, wherein an importance value is associated with the co-occurrence matrices of the entity vectors of the unified matrix for one or more heterogeneous entities to form a weighted matrix.

7. The method of claim 4, wherein each entity vector corresponds to a heterogeneous entity with a specific entity type.

8. The method of claim 4, wherein the concatenating comprises representing an entry in the unified matrix by an identity matrix when the heterogeneous entity co-occurs with itself.

9. The method of claim 1, further comprising ranking the results of the search, the ranking comprising:

determining entity vectors for the set of heterogeneous interrelated entities corresponding to the results of the search based on the unified space, wherein the entity vectors are based on the relationships between multiple heterogeneous entities;

calculating a query vector for the heterogeneous interrelated entities search query;

computing a similarity score for each pair of the query vector and the entity vector for each entity of the set of heterogeneous interrelated entities, the similarity score computation based on the dot product of the query vector and the entity vector; and

ranking the results of the search based on the similarity score.

10. The method of claim 9, wherein the ranking classifies the results of the search based on the entity type.

11. The method of claim 1, further comprising utilizing feedback from the search, the utilizing feedback comprising

identifying a set of semantically related entities based on the heterogeneous entities search query;

evaluating an expanded query vector based on the search query, the set of semantically related entities and weighting factors, wherein the weighing factor is based on the type of the heterogeneous entity; and

using the expanded query for searching refined entities.

12. A computing-based device comprising:

a memory;

one or more processors operatively coupled to the memory;

a search module configured to;

receive a heterogeneous entities search query;

search for a set of heterogeneous interrelated entities having one or more entity types in a unified space based on the heterogeneous entities search query, wherein the unified space is based on the interactions between heterogeneous entities; and

present the set of heterogeneous interrelated entities as results of the search.

13. The computing-based device as recited in claim 12, wherein the search module is further configured to:

construct a multiple-type graph for a plurality of heterogeneous entity types;

derive co-occurrence matrices from the multiple-type graph based on the relationships between entity types;

represent each heterogeneous entity as one or more entity vectors, wherein each entity vector is based on the co-occurrence matrices for the entities; and

combine the entity vectors of the heterogeneous entities to form a unified matrix, wherein the unified matrix represents the unified space.

14. The computing-based device as recited in claim 12, further comprising a ranking module configured to:

extract entity vectors for each entity of the set of heterogeneous interrelated entities based on the unified space, wherein the entity vectors are based on the relationships between multiple heterogeneous entities;

compute a search query vector for the heterogeneous entities search query;

generate pairs of search query vector with each entity of the set of heterogeneous interrelated entities;

calculate a similarity score for each pair, wherein the similarity score is based on the dot product of the vectors; and

rank the set of heterogeneous interrelated entities based on the similarity score.

15. The computing-based device as recited in claim 12, further comprising a feedback module configured to:

retrieve semantically related entities from the unified matrix based on the heterogeneous entities search query;

determine an expanded query based on the semantically related entities, the heterogeneous entities search query, and a set of weighting factors, wherein the weighting factors are based on the heterogeneous entities; and

retrieve heterogeneous interrelated entities from the unified matrix based on the expanded search query.

16. A computer readable medium having a set of computer readable instructions that, when executed, perform acts comprising:

receiving a heterogeneous entities search query;

retrieving a set of heterogeneous interrelated entities with one or more entity types in a unified space for the heterogeneous entities search query, wherein the unified space is based on interactions between multiple heterogeneous interrelated entities; and

displaying the set of heterogeneous interrelated entities.

17. The computer readable medium as recited in claim 16, further comprising representing a plurality of heterogeneous entities in the unified space, wherein the representing comprises:

constructing a multiple-type graph with a plurality of entity types, wherein vertices of the graph are based on the entity types and edges of the graph are based on interactions between entity types;

obtaining co-occurrence matrices from the multiple-type graph based on the interactions between the heterogeneous entities types;

generating one or more entity vectors for each heterogeneous entity based on the co-occurrence matrices corresponding to the heterogeneous entity; and

combining the plurality of entity vectors of the one or more heterogeneous entities to create a unified matrix, wherein the unified matrix represents the unified space.

18. The computer readable medium as recited in claim 17, further comprising:

evaluating a search query vector for the heterogeneous entities search query;

determining entity vectors for the set of heterogeneous interrelated entities based on the unified space, wherein the entity vectors are based on the relationships between multiple heterogeneous entities;

computing a similarity score for each pair of the search query vector and the entity vector for one or more entities; and

ranking the set of heterogeneous interrelated entities based on the similarity score.

19. The computer readable medium as recited in claim 18, wherein ranking the set of heterogeneous interrelated entities based on the similarity score further comprises categorizing the set of heterogeneous interrelated entities as lists based on the entity types.

20. The computer readable medium as recited in claim 17, further comprising:

recognizing a set of semantically related entities based on the heterogeneous entities search query;

calculating an expanded search query based on the set of semantically related entities, the heterogeneous entities search query and a set of weighting factors, wherein the weighting factors are based on the entities; and

searching heterogeneous interrelated entities based on the expanded search query.