Retrieval and display of data objects using a cross-group ranking metric

• US 7,330,849 B2
• Filed: 10/13/2005
• Issued: 02/12/2008
• Est. Priority Date: 05/28/2002
• Status: Expired due to Fees

• Current Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Original Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Inventors: Wang, Wei, Seo, Hyun-Ju, Gerasoulis, Apostolos
• Primary Examiner(s): Breene; John
• Assistant Examiner(s): To; Baoquoc N.
• Application Number:
  US11/250,341
• Publication Number:
  US 20060036591A1
• Time in Patent Office: 852 Days
• Field of Search: 707/3, 707/10, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Techniques to assign a ranking value to objects in a database such as a collection of cross referencing documents, the World-Wide Web or a hyperlinked database are described. The ranking value assigned to a given data object represents a cross-cluster strength metric and is a function of the object'"'"'s importance across all groups or clusters in which the object is classified. The cross-cluster strength metric may be particularly beneficial in enhancing the performance of web-based search engines because it emphasizes the importance of objects that appear in multiple groups while de-emphasizing the importance of objects that, while highly linked within one or a few groups, are relatively unlinked to objects in other groups.

Claims

1. A computer implemented method, comprising:

partitioning data objects of a search result in response to a search query into a plurality of clusters according to a predetermined algorithm, each data object having one or more keywords of the search query, and each data object being a member of one or more of the plurality of clusters;

assigning a first data object of each cluster in which the first data object is a member an object-value, the object-value representing a first relationship between the first data object and a remainder of data objects of each cluster in which the first data object is a member;

assigning each of the plurality of clusters in which the first data object is a member a cluster-value representing a second relationship between each cluster and a remainder of the plurality of clusters in which the first data object is a member;

determining a strength score for the first data object based on the object-value of the first data object of each cluster and the cluster-value of each cluster in which the first data object is a member; and

presenting the first data object in an order based on the strength score of the first data object with respect to strength scores of other data objects of the search result.

2. The method of claim 1, further comprising for each cluster in which the first data object is a member, determining a weighting factor associated with each cluster in which the first data object is a member, wherein the strength score for the first data object is determined further based on a weighting factor associated with each cluster in which the first data object is a member.

3. The method of claim 2, wherein the weighting factor represents an amount of importance attributed to cross-cluster memberships of the first data object among clusters in which the first data object is a member.

4. The method of claim 2, further comprising:

for each cluster in which the first data object is a member, determining a correlation between an object-value of the first data object within the respective cluster and a cluster-value of the respective cluster; and

summing correlations determined based on an object-value and a cluster-value of substantially all clusters in which the first data object is a member to determine the strength score for the first data object.

5. The method of claim 4, further comprising scaling a cluster-value based on a weighting factor associated with the respective cluster in determining a correlation based on a cluster-value and an object-value.

6. The method of claim 1, wherein the first relationship represents an importance of the first data object relative to other data objects within a cluster.

7. The method of claim 1, wherein the second relationship represents an importance of a cluster relative to other clusters in which the first data object is a member.

8. The method of claim 1, further comprising partitioning the plurality of clusters based on at least one common predecessor node associated with the data objects.

9. The method of claim 8, further comprising defining the plurality of clusters in terms of eigenvectors in which each data object within each eigenvector is assigned an object-value, wherein an eigenvalue of each eigenvector represents a cluster-value of the associated cluster.

10. The method of claim 9, wherein an object-value assigned to a data object represents a weighted importance of an authority of the respective data object across all clusters.

11. The method of claim 1, further comprising partitioning the plurality of clusters based on at least one common successor node associated with the data objects.

12. The method of claim 11, further comprising defining the plurality of clusters in terms of eigenvectors in which each data object within each eigenvector is assigned an object-value, wherein an eigenvalue of each eigenvector represents a cluster-value of the associated cluster.

13. The method of claim 12, wherein an object-value assigned to a data object represents a weighted importance of an authority of successor objects of the respective data object across all clusters.

14. The method of claim 1, further comprising partitioning the plurality of clusters based on a total number of common predecessor nodes and common successor nodes associated with the data objects.

15. The method of claim 14, further comprising:

assigning an object-value to each data object of each cluster based on a number of times the respective data object has been retrieved within the respective cluster in a predetermined period of time; and

assigning a cluster-value to each cluster based on a number of data objects present in the respective cluster relative to a total number of data objects of the plurality of clusters.

16. The method of claim 14, wherein an object-value assigned to a data object represents a weighted popularity of the respective data object across all clusters.

17. A machine-readable storage medium having instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

partitioning data objects of a search result in response to a search query into a plurality of clusters according to a predetermined algorithm, each data object having one or more keywords of the search query, and each data object being a member of one or more of the plurality of clusters;

assigning a first data object of each cluster in which the first data object is a member an object-value, the object-value representing a first relationship between the first data object and a remainder of data objects of each cluster in which the first data object is a member;

assigning each of the plurality of clusters in which the first data object is a member a cluster-value representing a second relationship between each cluster and a remainder of the plurality of clusters in which the first data object is a member;

determining a strength score for the first data object based on the object-value of the first data object of each cluster and the cluster-value of each cluster in which the first data object is a member; and

presenting the first data object in an order based on the strength score of the first data object with respect to strength scores of other data objects of the search result.

18. A data processing system, comprising:

a processor; and

a memory coupled to the processor for storing instructions, when executed from

the memory, cause the processor to perform operations including;

data objects of a search result in response to a search query into a plurality of clusters according to a predetermined algorithm, each data object having one or more keywords of the search query, and each data object being a member of one or more of the plurality of clusters,

assigning a first data object of each cluster in which the first data object is a member an object-value, the object-value representing a first relationship between the first data object and a remainder of data objects of each cluster in which the first data object is a member,

assigning each of the plurality of clusters in which the first data object is a member a cluster-value representing a second relationship between each cluster and a remainder of the plurality of clusters in which the first data object is a member,

determining a strength score for the first data object based on the object-value of the first data object of each cluster and the cluster-value of each cluster in which the first data object is a member, and

presenting the first data object in an order based on the strength score of the first data object with respect to strength scores of other data objects of the search result.