Method for ranking hyperlinked pages using content and connectivity analysis

• US 6,738,678 B1
• Filed: 01/15/1998
• Issued: 05/18/2004
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Henzinger, Monika R., Bharat, Krishna Asur
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US09/007,635
• Time in Patent Office: 2,315 Days
• Field of Search: 700/48, 707/3, 707/5, 707/102, 707/501, 707/1, 707/7, 707/2, 707/4, 707/10, 707/500, 358/402, 358/403
• US Class Current: 700/48
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• 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
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computerized method determines the ranking of documents including information content. The present method uses both content and connectivity analysis. An input set of documents is represented as a neighborhood graph in a memory. In the graph, each node represents one document, and each directed edge connecting a pair of nodes represents a linkage between the pair of documents. The input set of documents represented in the graph is ranked according to the contents of the documents. A subset of documents is selected from the input set of documents if the content ranking of the selected documents is greater than a first predetermined threshold. Nodes representing any documents, other than the selected documents, are deleted from the graph. The selected subset of documents is ranked according the linkage of the documents, and an output set of documents exceeding a second predetermined threshold is selected for presentation to users.

Claims

1. A computerized method for ranking documents including information content, comprising:

representing an input set of documents as a graph of nodes and directed edges in a memory, each node to represent one document, and each directed edge connecting a pair of nodes to represent a linkage between the pair of documents;

ranking the input set of documents represented in the graph according to their contents;

selecting a subset of documents from the input set of documents having a content ranking greater than a first predetermined threshold and deleting nodes in the graph representing all other documents wherein the first predetermined threshold is a median content ranking of the input set of documents;

ranking the selected subset of documents according to their linkage; and

selecting an output set of documents from the subset of documents having a linkage ranking greater than a second predetermined threshold.

2. The method of claim 1 wherein the input set of documents includes a result set of Web pages generated by a Web search engine in response to a user query.

3. The method of claim 2 wherein the input set of documents includes Web pages directly linked to the result set of pages.

4. The method of claim 3 further comprising measuring the similarity of the content of a particular input document to the content of a base set of documents to determine the content ranking of the particular document.

5. The method of claim 4 wherein the similarity is measured according to a vector space model.

6. The method of claim 4 wherein the similarity is measured according to a probabilistic model.

7. The method of claim 4 wherein the base set of documents is the result set of documents.

8. The method of claim 4 wherein the base set of documents is user specified.

9. The method of claim 1 wherein the input set of documents is a result set of Web pages generated by a Web search engine in response to a user query, and the first predetermined threshold is the median content ranking of the result set of Web pages.

10. The method of claim 1 wherein the first predetermined threshold is determined interactively.

11. The method of claim 1 wherein the first predetermined threshold is determined from the slope of a graph plotting the content ranking versus a similarity score.

12. The method of claim 1 wherein the first predetermined threshold is computed as a fraction of a maximum content score of the input set of documents.

13. The method of claim 1 further comprising measuring a weight dependant on the number and direction of edges connecting a particular subset document to determine the linkage ranking of the particular subset document.

14. The method of claim 13 wherein the linkage rankings are normalized.

15. The method of claim 13 further comprising dividing the weight of a particular document by the number of edges connected to the particular document from other documents when the other documents are stored at an identical site.

16. The method of claim 13 further comprising dividing the weight of a particular document by the number of edges connecting the particular document to other documents when the other documents are stored at an identical site.

17. A method for providing an output set of ranked documents, comprising:

representing an input set of documents as a graph of nodes and directed edges in a memory, each node to represent one document, and each directed edge connecting a pair of nodes to represent a linkage between the pair of documents;

ranking the input set of documents represented in the graph according to their contents;

selecting a subset of documents from the input set of documents having a content ranking greater than a first predetermined threshold and deleting nodes in the graph representing all other documents wherein the first predetermined threshold is the median content ranking of the input set of documents;

ranking the selected subset of documents according to their linkage; and

selecting an output set of documents from the subset of documents having a linkage ranking greater than a second predetermined threshold.

18. The method of claim 17 wherein the input set of documents includes a result set of Web pages generated by a Web search engine in response to a user query.

19. The method of claim 18 wherein the input set of documents includes Web pages directly linked to the result set of pages.

20. The method of claim 19 further comprising measuring the similarity of the content of a particular input document to the content of a base set of documents to determine the content ranking of the particular document.

21. The method of claim 20 wherein the similarity is measured according to a vector space model.

22. The method of claim 20 wherein the similarity is measured according to a probabilistic mode.

23. The method of claim 20 wherein the base set of documents is the result set of documents.

24. The method of claim 20 wherein the base set of documents is user specified.

25. The method of claim 17 wherein the input set of documents is a result set of Web pages generated by a Web search engine in response to a user query, and the first predetermined threshold is the median content ranking of the result set of Web pages.

26. The method of claim 17 wherein the first predetermined threshold is determined interactively.

27. The method of claim 17 wherein the first predetermined threshold is determined from the slope of a graph plotting the content ranking versus a similarity score.

28. The method of claim 17 wherein the first predetermined threshold is computed as a fraction of a maximum content score of the input set of documents.

29. The method of claim 17 further comprising measuring a weight dependant on the number and direction of edges connecting a particular subset document to determine the linkage ranking of the particular subset document.

30. The method of claim 29 wherein the linkage rankings are normalized.

31. The method of claim 29 further comprising dividing the weight of a particular document by the number of edges connected to the particular document from other documents when the other documents are stored at an identical site.

32. The method of claim 29 further comprising dividing the weight of a particular document by the number of edges connecting the particular document to other documents when the other documents are stored at an identical site.

33. A Web search engine that provides an output set of ranked documents, comprising:

a graphing module that represents an input set of documents as a graph of nodes and directed edges in a memory, each node to represent one document, and each directed edge connecting a pair of nodes to represent a linkage between the pair of documents;

a content ranking module that ranks the input set of documents represented in the graph according to their contents;

a content selection module that selects a subset of documents from the input set of documents having a content ranking greater than a first predetermined threshold and deleting nodes in the graph representing all other documents wherein the first predetermined threshold is the median content ranking of the input set of documents;

a linkage ranking module that ranks the selected subset of documents according to their linkage; and

a linkage selection module that selects an output set of documents from the subset of documents having a linkage ranking greater than a second predetermined threshold.

34. The search engine of claim 33 wherein the input set of documents includes a result set of Web pages generated by the Web search engine in response to a user query.

35. The search engine of claim 34 wherein the input set of documents includes Web pages directly linked to the result set of pages.

36. The search engine of claim 35 further comprising a content measurement module that measures the similarity of the content of a particular input document to the content of a base set of documents to determine the content ranking of the particular document.

37. The method of claim 36 wherein the similarity is measured according to a vector space model.

38. The method of claim 36 wherein the similarity is measured according to a probabilistic mode.

39. The method of claim 36 wherein the base set of documents is the result set of documents.

40. The method of claim 36 wherein the base set of documents is user specified.

41. The method of claim 33 wherein the input set of documents is a result set of Web pages generated by the Web search engine in response to a user query, and the first predetermined threshold is the median content ranking of the result set of Web pages.

42. The method of claim 33 wherein the first predetermined threshold is determined interactively.

43. The method of claim 33 wherein the first predetermined threshold is determined from the slope of a graph plotting the content ranking versus a similarity score.

44. The method of claim 33 wherein the first predetermined threshold is computed as a fraction of a maximum content core of the input set of documents.

45. The method of claim 33 further comprising measuring a weight dependant on the number and direction of edges connecting a particular subset document to determine the linkage ranking of the particular subset document.

46. The method of claim 45 wherein the linkage rankings are normalized.

47. The method of claim 45 further comprising dividing the weight of a particular document by the number of edges connected to the particular document from other documents when the other documents are stored at an identical site.

48. The method of claim 45 further comprising dividing the weight of a particular document by the number of edges connecting the particular document to other documents when the other documents are stored at an identical site.