Method for identifying related pages in a hyperlinked database

• US 6,665,837 B1
• Filed: 08/10/1998
• Issued: 12/16/2003
• Est. Priority Date: 08/10/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Dean, Jeffrey, Henzinger, Monika R., Broder, Andrei Z.
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US09/131,473
• Time in Patent Office: 1,954 Days
• Field of Search: 707/2, 707/4, 707/5, 707/102, 707/513, 707/501, 715/501.1, 715/513
• US Class Current: 715/234
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method is described for identifying related pages among a plurality of pages in a linked database such as the World Wide Web. An initial page is selected from the plurality of pages. Pages linked to the initial page are represented as a graph in a memory. The pages represented in the graph are scored on content, and a set of pages is selected, the selected set of pages having scores greater than a first predetermined threshold. The selected set of pages is scored on connectivity, and a subset of the set of pages that have scores greater than a second predetermined threshold are selected as related pages.

Claims

1. A method for identifying pages related to an initial page, comprising:

identifying a plurality of pages linked to the initial page;

representing the plurality of pages as a graph of nodes;

scoring the plurality of pages on connectivity of said plurality of pages to the initial page to generate a connectivity score for each of said plurality of pages;

removing from the graph of nodes pages with an undue influence on the scoring of other pages in the plurality of pages, wherein a page has the undue influence on the scoring of other pages in the plurality of pages, when said page has a score greater than a predetermined fraction of a total connectivity score, said total connectivity score computed by summing connectivity scores of the plurality of pages;

re-scoring remaining pages represented in the graph of nodes; and

selecting a subset of the remaining pages represented in the graph of nodes that have connectivity scores greater than a first predetermined threshold as the pages related to the initial page.

2. The method of claim 1 wherein the initial page is selected by specifying an address of the page.

3. The method of claim 1 wherein the initial page is selected by a user interface.

4. The method of claim 1 wherein the connectivity of the plurality of pages are scored on content by measuring the similarity of the plurality of pages to a topic.

5. The method of claim 4 wherein the topic is extracted from the initial page.

6. The method of claim 4 wherein the topic is extracted from the plurality of pages represented in the graph.

7. The method of claim 1 wherein any of the plurality of pages that are linked in any direction to the initial page are represented in the graph.

8. The method of claim 7 wherein the plurality of pages represented in the graph are linked to the initial page by a predetermined number of links.

9. The method of claim 7 wherein each page represented in the graph depends on a path from each page to the initial page, the path including the length of the path and the direction of edges on the path.

10. The method of claim 7 wherein the plurality of pages represented in the graph as nodes are linked to the node representing the initial page by a number of edges that is determined dynamically.

11. The method of claim 1 performed in a client computer.

12. The method of claim 1 performed in a server computer.

13. The method of claim 1, wherein the predetermined fraction of the total connectivity score is equal to ninety-five percent of the total connectivity score.

14. The method of claim 1, wherein the step of identifying a plurality of pages linked to the initial page comprises identifying a plurality of pages linked to the initial page by not more than a defined number of links, wherein when said defined number of links is set to two, a page is linked to said initial page only if said page is reachable from said initial page by going one link backwards, said page is reachable from said initial page by going one link forwards, said page is reachable from said initial page by going one link backwards followed by one link forwards, or said page is reachable from said initial page by going one link forward followed by one link backwards.

15. A method for identifying pages related to an initial page, comprising:

identifying a plurality of pages linked to the initial page;

representing the plurality of pages as a graph of nodes;

scoring the plurality of pages on connectivity of said plurality of pages to the initial page to generate a connectivity score for each of said plurality of pages;

removing from the graph of nodes pages with an undue influence on the scoring of other pages in the plurality of pages, wherein a page has the undue influence on the scoring of other pages in the plurality of pages when said page has a score greater than each score of all other pages in the plurality of pages and said score is at least three times greater than a next highest score of another page in said plurality of pages;

re-scoring remaining pages represented in the graph of nodes; and

selecting a subset of the remaining pages represented in the graph of nodes that have connectivity scores greater than a first predetermined threshold as the pages related to the initial page.

16. The method of claim 15 wherein the initial page is selected by specifying an address of the page.

17. The method of claim 15 wherein the initial page is selected by a user interface.

18. The method of claim 15 wherein the connectivity of the plurality of pages are scored on content by measuring the similarity of the plurality of pages to a topic.

19. The method of claim 18 wherein the topic is extracted from the initial page.

20. The method of claim 18 wherein the topic is extracted from the plurality of pages represented in the graph.

21. The method of claim 15 wherein any of the plurality of pages that are linked in any direction to the initial page are represented in the graph.

22. The method of claim 21 wherein the plurality of pages represented in the graph are linked to the initial page by a predetermined number of links.

23. The method of claim 21 wherein each page represented in the graph depends on a pat from each page to the initial page, the path including the length of the path and the direction of edges on the path.

24. The method of claim 21 wherein the plurality of pages represented in the graph as nodes are linked to the node representing the initial page by a number of edges that is determined dynamically.

25. The method of claim 15 performed in a client computer.

26. The method of claim 15 performed in a server computer.

27. The method of claim 15, wherein the step of identifying a plurality of pages linked to the initial page comprises identifying a plurality of pages linked to the initial page by not more than a defined number of links, wherein when said defined number of links is set to two, a page is linked to said initial page only if said page is reachable from said initial page by going one link backwards, said page is reachable from said initial page by going one link forwards, said page is reachable from said initial page by going one link backwards followed by one link forwards, or said page is reachable from said initial page by going one link forward followed by one link backwards.

28. A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for identifying pages related to an initial page, said computer process comprising:

identifying a plurality of pages linked to the initial page;

representing the plurality of pages as a graph of nodes;

scoring the plurality of pages on connectivity of said plurality of pages to the initial page to generate a connectivity score for each of said plurality of pages;

removing from the graph of nodes pages with an undue influence on the scoring of other pages in the plurality of pages, wherein a page has the undue influence on the scoring of other pages in the plurality of pages, when said page has a score greater than a predetermined fraction of a total connectivity score, said total connectivity score computed by sung connectivity scores of the plurality of pages;

re-scoring remaining pages represented in the graph of nodes; and

selecting a subset of the remaining pages represented in the graph of nodes that have connectivity scores greater than a first predetermined threshold as the pages related to the initial page.

29. The computer program product of claim 28 wherein the computer process selects the initial page by specifying an address of the page.

30. The computer program product of claim 28 wherein the computer process selects the initial page by receiving input from a user interface.

31. The computer program product of claim 28 wherein the computer process scores connectivity of the plurality of pages on content by measuring the similarity of the plurality of pages to a topic.

32. The computer program product of claim 31 wherein the computer process extracts the topic from the initial page.

33. The computer program product of claim 31 wherein the computer process extracts the topic from the plurality of pages represented in the graph.

34. The computer program product of claim 28 wherein the computer process represents the plurality of pages that are linked in any direction to the initial page in the graph.

35. The computer program product of claim 34 wherein the computer process links the plurality of pages represented in the graph to the initial page by a predetermined number of links.

36. The computer program product of claim 34 wherein each page represented in the graph depends on a path from each page to the initial page, the path including the length of the path and the direction of edges on the path.

37. The computer program product of claim 34 wherein the computer process links the plurality of pages represented in the graph as nodes to the node representing the initial page by a number of edges that is determined dynamically.

38. The computer program product of claim 28 wherein the computer process is performed in a client computer.

39. The computer program product of claim 28 wherein the computer process is performed in a server computer.

40. The computer program product of claim 28, wherein the first predetermined threshold is equal to ninety-five percent of the total connectivity score.

41. The computer program product of claim 28, wherein the computer process step of identifying a plurality of pages linked to the initial page comprises identifying a plurality of pages linked to the initial page by not more than a defined number of links, wherein when said defined number of links is set to two, a page is linked to said initial page only if said page is reachable from said initial page by going one link backwards, said page is reachable from said initial page by going one link forwards, said page is reachable from said initial page by going one link backwards followed by one link forwards, or said page is reachable from said initial page by going one link forward followed by one link backwards.

42. A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for identifying pages related to an initial page, said computer process comprising:

identifying a plurality of pages linked to the initial page;

representing the plurality of pages as a graph of nodes;

scoring the plurality of pages on connectivity of said plurality of pages to the initial page to generate a connectivity score for each of said plurality of pages;

removing from the graph of nodes pages with an undue influence on the scoring of other pages in the plurality of pages, wherein a page has the undue influence on the scoring of other pages in the plurality of pages when said page has a score greater than each score of all other pages in the plurality of pages and said score is at least three times greater than a next highest score of another page in said plurality of pages;

re-scoring remaining pages represented in the graph of nodes; and

selecting a subset of the remaining pages represented in the graph of nodes that have connectivity scores greater than a first predetermined threshold as the pages related to the initial page.

43. The computer program product of claim 42 wherein the computer process selects the initial page by specifying an address of the page.

44. The computer program product of claim 42 wherein the computer process selects the initial page by receiving input from a user interface.

45. The computer program product of claim 42 wherein the computer process scores connectivity of the plurality of pages on content by measuring the similarity of the plurality of pages to a topic.

46. The computer program product of claim 45 wherein the computer process extracts the topic from the initial page.

47. The computer program product of claim 45 wherein the computer process extracts the topic from the plurality of pages represented in the graph.

48. The computer program product of claim 42 wherein the computer process represents the plurality of pages that are linked in any direction to the initial page in the graph.

49. The computer program product of claim 48 wherein the computer process links the plurality of pages represented in the graph to the initial page by a predetermined number of links.

50. The computer program product of claim 48 wherein each page represented in the graph depends on a path from each page to the initial page, the path including the length of the path and the direction of edges on the path.

51. The computer program product of claim 48 wherein the computer process links the plurality of pages represented in the graph as nodes to the node representing the initial page by a number of edges that is determined dynamically.

52. The computer program product of claim 42 wherein the computer process is performed in a client computer.

53. The computer program product of claim 42 wherein the computer process is performed in a server computer.

54. The computer program product of claim 42, wherein the computer process step of identifying a plurality of pages linked to the initial page comprises identifying a plurality of pages linked to the initial page by not more than a defined number of links, wherein when said defined number of links is set to two, a page is linked to said initial page only if said page is reachable from said initial page by going one link backwards, said page is reachable from said initial page by going one link forwards, said page is reachable from said initial page by going one link backwards followed by one link forwards, or said page is reachable from said initial page by going one link forward followed by one link backwards.