Reinforced clustering of multi-type data objects for search term suggestion

• US 7,689,585 B2
• Filed: 04/15/2004
• Issued: 03/30/2010
• Est. Priority Date: 04/15/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Najm, Tarek, Li, Li, Zhang, Benyu, Li, Ying, Zeng, Hua-Jun
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): SANDERS, AARON J
• Application Number:
  US10/826,159
• Publication Number:
  US 20050234972A1
• Time in Patent Office: 2,175 Days
• Field of Search: 707/103.R
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Systems and methods for related term suggestion are described. In one aspect, relationships among respective ones of two or more multi-type data objects are identified. The respective ones of the multi-type data objects include at least one object of a first type and at least one object of a second type that is different from the first type. The multi-type data objects are iteratively clustered in view of respective ones of the relationships to generate reinforced clusters.

Claims

1. A computer-implemented method performed by a computing device that has one or more processors to execute instructions, the method comprising:

identifying relationships between multi-type data objects that include at least one object of a first type and at least one object of a second type different from the first type, the relationships being at least one of intra-layer relationships or inter-layer relationships among the multi-type data objects;

iteratively clustering the multi-type data objects based on the relationships to generate reinforced clusters;

generating a list of suggested search terms associated with a bid term using the reinforced clusters, the search terms generated in response to receiving the bid term from a user;

transmitting, via a network interface, the list of suggested search terms to a user; and

mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following;

2. The method of claim 1, wherein the inter-layer relationships include at least one of content related information, user interest in an associated topic, and user interest in an associated Web page.

3. The method of claim 1, wherein the intra-layer relationships include at least one of query refinement, recommended Web page, and relationship between respective users.

4. The method of claim 1, wherein each of the multi-type data objects are related to at least one of a selected Web page type and a user information type.

5. The method of claim 1, wherein the intra-layer relationships include a first weighting scheme and the intra-layer relationships include a second weighting scheme different than the first weighting scheme to indicate importance to associated objects of the multi-type data objects.

6. The method of claim 1, wherein the identifying and the iteratively clustering are performed for the suggested searched terms.

7. The method of claim 1, wherein the iteratively clustering comprises propagating clustering results of a first iteration to all related data objects of the multi-type data objects, at least two of the related data objects being of heterogeneous data type, the propagating being used to enhance clustering of respective ones of the multi-type data objects in a second iteration of reinforced clustering operations.

8. The method of claim 1, wherein the iteratively clustering comprises determining a similarity between individual ones of the multi-type data objects, the similarity being a function of at least one of inter-object and intra-object content similarity and similarities between the inter-layer relationships and the intra-layer relationships.

9. The method of claim 1, wherein the iteratively clustering comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

10. The method of claim 1, wherein the method further comprises mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types.

11. The method of claim 1, further comprising:

comparing the bid term with a feature space of objects in the reinforced clusters to identify the suggested search terms.

12. A computer-readable storage medium comprising computer-executable instructions executable by a processor for:

identifying at least one of intra-layer and inter-layer relationships among multi-type data objects, wherein the multi-type data objects comprise at least one object of a first type and at least one object of a second type different from the first type;

iteratively clustering the multi-type data objects by at least one of the relationships to generate reinforced clusters;

generating a list of suggested search terms associated with a bid term using the reinforced clusters, the suggested search terms generated in response to receiving the bid term from a user; and

mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following;

13. The computer-readable storage medium of claim 12, wherein the inter-layer relationships comprise at least one of content related information, user interest in an associated topic, and user interest in an associated Web page.

14. The computer-readable storage medium of claim 12, wherein the intra-layer relationships comprise at least one of query refinement, recommended Web page, and relationship between respective users.

15. The computer-readable storage medium of claim 12, wherein each of the multi-type data objects are related to at least one of a search query data object type, a selected Web page type, and a user information type.

16. The computer-readable storage medium of claim 12, wherein The at least one of the identified relationships are weighted to indicate an importance to associated objects of the multi-type data objects.

17. The computer-readable storage medium of claim 12, wherein the identifying and the iteratively clustering are performed for the suggested search term.

18. The computer-readable storage medium of claim 12, wherein the iteratively clustering comprises propagating clustering results of a first iteration to all related data objects of the multi-type data objects, at least two of the related data objects being of heterogeneous data type, the propagating being used to enhance clustering of respective ones of the multi-type data objects in a second iteration of reinforced clustering operations.

19. The computer-readable storage medium of claim 12, wherein the iteratively clustering comprises determining a similarity between individual ones of the multi-type data objects, the similarity being a function of at least on of object content similarity and similarities between at least one of the identified relationships.

20. The computer-readable storage medium of claim 12, wherein the iteratively clustering comprises merging related ones of the multi-type data objects to reduce feature space dimensionality of the related ones.

21. The computer-readable storage medium of claim 12, wherein the instructions further comprise instructions for mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types.

22. The computer-readable storage medium of claim 12, wherein the instructions further comprise:

comparing the bid term with a feature space of objects in the reinforced clusters to identify the suggested search terms.