Method and apparatus for constructing a link structure between documents

• US 7,895,195 B2
• Filed: 07/04/2006
• Issued: 02/22/2011
• Est. Priority Date: 07/29/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Shixia, Yang, Li Ping, Zhang, Li
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Mamillapalli; Pavan
• Application Number:
  US11/996,108
• Publication Number:
  US 20080222138A1
• Time in Patent Office: 1,694 Days
• Field of Search: 707/736, 707/723, 707/726, 707/999.005
• US Class Current: 707/723
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A method and computer system for constructing a link structure for T documents. An initial link structure G0 between the T documents is generated. For each document d of D documents of the T documents, a loop of no more than M iterations is performed. In each iteration: a search engine is used to generate a ranking order of T′ documents consisting of the T documents except document d; the initial link structure G0 is modified according to the ranking order to generate a modified link structure G; if a condition is satisfied then the loop is exited and the modified link structure G1 is outputted, otherwise G0 is set equal to G1 and a next iteration of the loop is performed. The condition is that a measure of a difference between G0 and G1 is less than a specified threshold or the M iterations were performed.

Claims

1. A method for constructing a link structure for T documents, said method comprising:

a computer generating an initial link structure G0 comprising a plurality of initial links between the T documents, each document of the T documents comprising at least one query, each query comprising at least one keyword, said T at least 2;

for each document d of the T documents, said computer performing a loop consisting of no more than M iterations, M being a predefined maximum number of iterations, M being greater than 2, each iteration of the loop comprising the steps of;

i) using a search engine to generate a ranking order of T′

documents that consist of all documents of the T documents except document d;

ii) modifying the initial link structure G0 in accordance with the ranking order to generate a modified link structure G1;

iii) ascertaining whether a condition is satisfied, said condition being that a measure of a difference between G0 and G1 is less than a specified threshold or said M iterations have been performed;

iv) if said ascertaining ascertains that the condition is satisfied then exiting the loop followed by outputting the modified link structure G1, otherwise setting G0 equal to G1 followed by performing a next iteration of the loop comprising steps i), ii), Hi), and iv);

wherein M iterations have been performed resulting in generation of M modified link structures G1 in step ii);

wherein after M iterations have been performed and said exiting the loop has been performed, the method further comprises said computer determining and outputting a final link structure G;

wherein the final link structure G comprises each node that is commonly comprised by the M modified link structures; and

wherein the final link structure G comprises each edge that is commonly comprised by at least a predefined fraction of the M modified link structures.

2. The method of claim 1, wherein step iv) ascertains in a first iteration of the loop that the condition is satisfied.

3. The method of claim 1, wherein step iv) ascertains in a first iteration of the loop that the condition is not satisfied.

4. The method of claim 1, wherein each document of the T documents is a non-HTML document.

5. The method of claim 1, wherein pre-existing links between documents of the T documents existed prior to said generating the initial link structure G0, and wherein said generating the initial link structure G0 comprises including the pre-existing links in the initial link structure G0.

6. The method of claim 1, wherein the measure of the difference between G0 and G1 is a total number of different links between G1 and G0.

7. The method of claim 1, wherein step ii) comprises:

said computer selecting the first N documents ranked highest in the ranking order, such that a remaining T′

-N documents are ranked below the first N documents in the ranking order, wherein N is less than T′

;

said computer maintaining or creating a link from document d to each document of the first N documents; and

said computer deleting the links from document d to the remaining T′

-N documents.

8. A computer system comprising a computer program stored on a non-transitory storage medium, said computer program including instructions configured to be executed on the computer system to perform a method for constructing a link structure for T documents, said method comprising:

generating an initial link structure G0 comprising a plurality of initial links between the T documents, each document of the T documents comprising at least one query, each query comprising at least one keyword, said T at least 2;

for each document d of the T documents, performing a loop consisting of no more than M iterations, M being a predefined maximum number of iterations, M being greater than 2, each iteration of the loop comprising the steps of;

i) using a search engine to generate a ranking order of T′

documents that consist of all documents of the T documents except document d;

ii) modifying the initial link structure G0 in accordance with the ranking order to generate a modified link structure G1;

iii) ascertaining whether a condition is satisfied, said condition being that a measure of a difference between G0 and G1 is less than a specified threshold or said M iterations have been performed;

iv) if said ascertaining ascertains that the condition is satisfied then exiting the loop followed by outputting the modified link structure G1, otherwise setting G0 equal to G1 followed by performing a next iteration of the loop comprising steps i), ii), iii), and iv);

wherein M iterations have been performed resulting in generation of M modified link structures G1 in step ii);

wherein after M iterations have been performed and said exiting the loop has been performed, the method further comprises determining and outputting a final link structure G;

wherein the final link structure G comprises each node that is commonly comprised by the M modified link structures; and

wherein the final link structure G comprises each edge that is commonly comprised by at least a predefined fraction of the M modified link structures.

9. The computer system of claim 8, wherein step iv) ascertains in a first iteration of the loop that the condition is satisfied.

10. The computer system of claim 8, wherein step iv) ascertains in a first iteration of the loop that the condition is not satisfied.

11. The computer system of claim 8, wherein each document of the T documents is a non-HTML document.

12. The computer system of claim 8, wherein pre-existing links between documents of the T documents existed prior to said generating the initial link structure G0, and wherein said generating the initial link structure G0 comprises including the pre-existing links in the initial link structure G0.

13. The computer system of claim 8, wherein the measure of the difference between G0 and G1 is a total number of different links between G1 and G0.

14. The computer system of claim 8, wherein step ii) comprises:

selecting the first N documents ranked highest in the ranking order, such that a remaining T′

-N documents are ranked below the first N documents in the ranking order, wherein N is less than T′

;

maintaining or creating a link from document d to each document of the first N documents; and

deleting the links from document d to the remaining T′

-N documents.