Method and Apparatus for Constructing a Link Structure Between Documents

• US 20080222138A1
• Filed: 07/04/2006
• Published: 09/11/2008
• Est. Priority Date: 07/29/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Shixia, Zhang, Li, Yang, Li Ping
• Granted Patent: US 7,895,195 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• 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-7. -7. (canceled)

8. 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 D documents of the T documents such that D is less than or equal to T, performing a loop consisting of no more than M iterations, M being a predefined maximum number of iterations, M being at least 2, each iteration of the loop comprising the steps of;

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

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

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

c) 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;

d) 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 a), b), c), and d).

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

10. The method of claim 8, wherein N is at least 2, and wherein step d) ascertains in a first iteration of the loop that the condition is not satisfied.

11. The method of claim 8, wherein D is less than T.

12. The method of claim 8, wherein D is equal to T.

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

14. The method 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.

15. The method of claim 8, wherein the measure of the difference between G0 and G1 is a magnitude of the difference between the total number of distinct links in G0 and the total number of distinct links in G1.

16. The method of claim 8, wherein step b) 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.

17. The method of claim 8,

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

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.

18. A computer system comprising a computer program that includes 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 D documents of the T documents such that D is less than or equal to T, performing a loop consisting of no more than M iterations, M being a predefined maximum number of iterations, M being at least 2, each iteration of the loop comprising the steps of;

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

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

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

c) 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;

d) 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 a), b), c), and d).

19. The computer system of claim 18, wherein step d) ascertains in a first iteration of the loop that the condition is satisfied.

20. The computer system of claim 18, wherein N is at least 2, and wherein step d) ascertains in a first iteration of the loop that the condition is not satisfied.

21. The computer system of claim 18, wherein D is less than T.

22. The computer system of claim 18, wherein D is equal to T.

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

24. The computer system of claim 18, 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.

25. The computer system of claim 18, wherein the measure of the difference between G0 and G1 is a magnitude of the difference between the total number of distinct links in G0 and the total number of distinct links in G1.

26. The computer system of claim 18, wherein step b) 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.

27. The computer system of claim 18,

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

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.