Method and system for filtering of information entities

• US 6,996,572 B1
• Filed: 10/08/1997
• Issued: 02/07/2006
• Est. Priority Date: 10/08/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dom, Byron Edward, Rajagopalan, Sridhar, Raghavan, Prabhakar, Gibson, David Andrew, Chakrabarti, Soumen, Kleinberg, Jon Michael
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US08/947,221
• Time in Patent Office: 3,044 Days
• Field of Search: 707/5, 707/100, 707/101, 707/501, 707/102, 715/501.1, 705/27, 907 1- 5, 907/100, 907/101, 907/102, 907/104.1
• US Class Current: 715/205
• 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/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and method are provided for eliciting interesting structure from a collection of entities or resources with explicit and/or implicit, static and/or dynamic relations, called “affinities,” between them. Interesting structure includes (1) notions of quality, authority, or definitiveness of information, (2) notions of relevance to a user'"'"'s information need, (3) notions of similarity among the plurality of resources retrieved from a universe of resources by a query process, and (4) notions of similarity among the usages of resources by different users/servers. Similarities between entities are computed, based on similarities between the affinity values for the entities. That is, where the affinitiy values for two entities resemble each other, the two entities have a high degree of similarity. Using the similarities, the entities are ranked, clustered, etc., based on a significance derived from the similarities. The ranking, clustering, etc., makes up the interesting structure which is sought.

Claims

1. A method for eliciting information, useful to a user, from first and second collections of entities or resources with explicit and/or implicit, static and/or dynamic relations therebetween, the method comprising the acts of:

obtaining the first collection of entities and the second collection of entities, hyperlinks being established between at least some of the entities;

obtaining affinity values, including, for each given one of the entities, a respective affinity value for the given entity and each respective one of the other entities of the collection, whereby at least one affinity value depends at least in part on at least one hyperlink;

initializing significance values for each of the entities;

iteratively calculating updated significance values for each entity, based on the affinities and on the significance values prior to the iterative update, until a predetermined condition is reached; and

obtaining the useful information based on the significance values after the final iteration of the act of iteratively calculating.

2. A method as recited in claim 1, wherein the step of obtaining affinity values includes obtaining, for each one of the given entities in the first collection, a respective affinity value for the given entity and each respective one of the entities in the second collection.

3. A method as recited in claim 1, wherein the step of obtaining first and second sets of entities includes obtaining a single set of entities as both the first set and the second set.

4. A method as recited in claim 3, wherein the step of obtaining affinity values includes obtaining, for each one of the given entities in the single set of entities, a respective affinity value for the given entity and each respective other one of the entities in the single set.

5. A method as recited in claim 1, wherein the step of obtaining affinity values includes the steps of:

obtaining a set of raw affinity values; and

deriving a set of derived affinity values from the raw affinity values.

6. A method as recited in claim 5, wherein the step of deriving derived affinity values includes using one of:

a sum operation,

an average operation,

a min operation,

a max operation, and

a linear combination.

7. A method as recited in claim 1, wherein:

the method further includes the step of computing similarity values between the entities based on the affinity values; and

the step of iteratively calculating updated significance values includes iteratively calculating updated significance values based on the affinities and on the significance values.

8. A method as recited in claim 7, further comprising the step of iteratively calculating a updated principal affinity component value for each entity of interest based on the affinities and similarities.

9. A method as recited in claim 8, wherein:

the step of computing similarity values includes computing a similarity matrix; and

the step of iteratively calculating a updated principal affinity component value includes calculating a non-principal eigenvector of the similarity matrix.

10. A method as recited in claim 8, wherein the step of obtaining the useful information includes obtaining the useful information based on the updated principal affinity component values.

11. A method as recited in claim 10, wherein the step of obtaining the useful information based on the updated principal affinity component values includes obtaining a cluster.

12. A computerized method for eliciting information, useful to a user, from first and second collections of entities or resources with explicit and/or implicit, static and/or dynamic relations therebetween, the method comprising the acts of:

obtaining the first collection of entities and the second collection of entities;

obtaining affinity values, including, for each given one of the entities, a respective affinity value for the given entity and each respective one of the other entities of the collection, the affinity values not being constrained to be symmetric;

initializing significance values for each of the entities;

iteratively calculating updated significance values for each entity, based on the affinities and on the significance values prior to the iterative update, until a predetermined condition is reached; and

obtaining the useful information based on the significance values after the final iteration of the act of iteratively calculating.