Relevancy-based database retrieval and display techniques

• US 7,028,026 B1
• Filed: 05/28/2002
• Issued: 04/11/2006
• Est. Priority Date: 05/28/2002
• Status: Expired due to Term

• Current Assignee: IAC Search & Media Incorporated (IAC/InterActiveCorp)
• Original Assignee: Ask Jeeves, Inc. (IAC, Inc.)
• Inventors: Wang, Wei, Yang, Tao, Gerasoulis, Apostolos
• Primary Examiner(s): Gaffin, Jefrey A
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/156,260
• Time in Patent Office: 1,414 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/101, 707/104.1, 707/8, 707/9, 707/10, 707/100, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• 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 retrieve, rank and display data objects retrieved form a database are described. In particular, methods to assign a global ranking value to a data object based on a combination of that object'"'"'s link-based (e.g., vector-space cluster analysis) and text-based (e.g., word frequency) ranks are described. Additional techniques to determine a set of concepts, topics or key words associated with each retrieved data objects are described.

Claims

1. A computer implemented method to rank a plurality of data objects, the method comprising:

identifying a plurality of data objects in response to a result of an initial search of a request received front a user over a network;

assigning a link-based rank value to each of a first portion of the identified data objects, wherein the first portion of the identified data objects is selected based on cluster hierarchy of the plurality of data objects and wherein the clusters are defined based on at least one or common predecessor nodes, common successor nodes, and a combination of the common predecessor and successor nodes;

assigning a text-based rank value to each of a second portion of the identified data objects, wherein the cluster hierarchy includes a plurality of levels, and wherein the second portion of the identified data objects has a different level than the first portion of the identified data objects;

assigning a global rank value to each of a third portion of the identified data objects, the global rank value based on a combination of an object'"'"'s link-based and text-based rank values; and

processing at least a portion of the third portion of identified data objects in accordance with their global rank value.

2. The method of claim 1, wherein the first portion of data objects comprise less than all of the identified plurality of data objects.

3. The method of claim 1, wherein the second portion of identified data objects comprise less than all of the first portion of data objects.

4. The method of claim 1, wherein the third portion comprises less than all of the second portion of data objects.

5. The method of claim 1, wherein the act of identifying a plurality of data objects comprises identifying a plurality of documents.

6. The method of claim 5, wherein the act of identifying a plurality of documents comprises identifying a plurality of web pages.

7. The method of claim 1, wherein the act of identifying a plurality of data objects comprises:

identifying a first plurality of data objects based on a user query;

ranking the first plurality of data objects; and

selecting a subset of the ranked first plurality of data objects for continued evaluation, the selected subset of data objects having a ranking greater than a predetermined threshold, wherein unselected ranked first plurality of data objects is aggregated into a next lower level in the cluster hierarchy.

8. The method of claim 7, wherein the act of identifying a first plurality of data objects comprises identifying data objects comprising words related to the user query.

9. The method of claim 8, wherein the act of identifying words related to the user query include identifying words comprising the query.

10. The method of claim 8, wherein the act of identifying words related to the user query includes identifying one or more words that are semantic equivalents of at least one word comprising the query.

11. The method of claim 7, wherein the act of ranking the first plurality of identified data objects comprises ranking each of the first plurality of identified data objects based on a global link popularity characteristic.

12. The method of claim 1, wherein each of the cluster in the cluster hierarchy is represented by an eigenvector (v_i) whose non-zero elements correspond to data object members of each cluster and is associated with an eigenvalue (λ

_i), wherein i represents a level of each cluster.

13. The method of claim 12, wherein a number of levels in the cluster hierarchy is determined based on a ratio of eigenvalues associated with eigenvectors, such that when a magnitude of the ratio drops below a predetermined threshold, no more eigenvectors are involved.

14. The method of claim 1, wherein the act of assigning a text-based rank value to each of a second portion of data objects comprises assigning a rank value for each of the selected second portion of identified data objects based on a term frequency analysis of text associated with each of the data objects.

15. The method of claim 1, wherein the act of assigning a global rank value to each of a third portion of data objects comprises assigning a global rank value that is a linear combination of an object'"'"'s link-based and text-based ranking values.

16. The method of claim 1, wherein the act of processing comprises displaying identifiers for at least some of the third portion of data objects to a user in accordance with their global rank value.

17. The method of claim 16, wherein the act of assigning a global rank value is performed at run-time and in response to a user query.

18. A machine-readable medium for storing instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

identifying a plurality of data objects in response to a result of an initial search of a request received from a user over a network;

assigning a link-based rank value to each of a first portion of the identified data objects, wherein the first portion of the identified data objects is selected based on cluster hierarchy of the plurality of data objects and wherein the clusters are defined based on at least one of common predecessor nodes, common successor nodes, and a combination of the common predecessor and successor nodes;

assigning a text-based rank value to each of a second portion of the identified data objects, wherein the cluster hierarchy includes a plurality of levels, and wherein the second portion of the identified data objects has a different level than the first portion of the identified data objects;

assigning a global rank value to each of a third portion of the identified data objects, the global rank value based on a combination of an object'"'"'s link-based and text-based rank values; and

processing at least a portion of the third portion of identified data objects in accordance with their global rank value.

19. 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

identifying a plurality of data objects in response to a result of an initial search of a request received from a user over a network,

assigning a link-based rank value to each of a first portion of the identified data objects, wherein the first portion of the identified data objects is selected based on cluster hierarchy of the plurality of data objects and wherein the clusters are defined based on at least one of common predecessor nodes, common successor nodes, and a combination of the common predecessor and successor nodes,

assigning a text-based rank value to each of a second portion of the identified data objects, wherein the cluster hierarchy includes a plurality of levels, and wherein the second portion of the identified data objects has a different level than the first portion of the identified data objects,

assigning a global rank value to each of a third portion of the identified data objects, the global rank value based on a combination of an object'"'"'s link-based and text-based rank values, and

processing at least a portion of the third portion of identified data objects in accordance with their global rank value.