Method, system, and computer program product for searching for, navigating among, and ranking of documents in a personal web

• US 7,680,812 B2
• Filed: 09/16/2005
• Issued: 03/16/2010
• Est. Priority Date: 09/16/2004
• Status: Expired due to Fees

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Uddin; MD. I
• Application Number:
  US11/227,495
• Publication Number:
  US 20060059144A1
• Time in Patent Office: 1,642 Days
• Field of Search: 707/5, 707/2, 707/3, 707/10, 707/100, 707/102, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method, apparatus, and computer program product for a personal search engine that includes a hybrid web composed of: the similarity web, and directed hyperlinks. Components include a parser (extracting words from documents); a text relevance analyzer; a link analysis method; the similarity web; a similarity analyzer; and hyperlinks. Other components include a navigation window; and FQSs. The combination of all the above may be incorporated into a working personal search engine.

Claims

1. A method for searching electronic material stored in a computing environment using a computer, comprising:

providing a plurality of documents;

determining, using the computer, an undirected, weighted link between at least two of said plurality of documents, based on similarity;

determining, using the computer, a directed, weighted link between at least two of said plurality of documents;

adding said determined undirected, weighted links to said determined directed, weighted links to create a hybrid web having links; and

performing, using the computer, a link analysis algorithm taking the links of said hybrid web as its input, said algorithm including at least one of forward link analysis and backward link analysis, wherein

the output of said algorithm is a set of link analysis scores.

2. The method according to claim 1, wherein said algorithm is eigenvector based.

3. The method according to claim 1, wherein said at least one of forward and backward link analysis comprises using at least one of a non-compound Forward operator and a non-compound Backward operator.

4. The method according to claim 1, wherein said at least one of forward and backward link analysis comprises using at least one of a non-normalized Forward operator and a non-normalized Backward operator.

5. The method of claim 1, further comprising:

scoring each of said at least two documents via at least one of text relevancy analysis and file quality analysis.

6. The method of claim 1, wherein the step of determining a directed, weighted link between at least two of said plurality of documents includes establishing a hyperlink between a first document and a second document, wherein said step of establishing a hyperlink comprises one of:

anchoring said hyperlink in text of one of said first and second documents, linking said first and second document with an unanchored hyperlink, wherein said step of establishing a hyperlink further comprises one of;

entering said hyperlink via an input terminal, and establishing said hyperlink automatically.

7. The method of claim 6, wherein said directed, weighted link may or may not be anchored to text on a pointing or a pointed-to document.

8. The method of claim 6, further comprising:

storing hyperlink information (pointing file, pointed-to file, hyperlink weight, and anchoring text) in a link structure database.

9. The method of claim 1, wherein said at least one of forward link analysis and backward link analysis comprises:

determining an authority-like score for a document using a non-compound, non-normalized Forward operator and not using a Backward operator; and

determining a hub-like score for a document using a non-compound, non-normalized Backward operator and not using a forward operator such that said steps of determining an authority-like score and determining a hub-like score are mathematically decoupled.

10. The method of claim 5, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

11. The method of claim 10, further comprising:

comparing documents pairwise; and

developing a similarity score.

12. The method of claim 11, further comprising:

storing said similarity score in a similarity score database.

13. The method of claim 11, wherein said step of comparing documents pairwise comprises:

counting a number of times N_f(w) that a word w occurs in a document f; and

dividing N_f (w) by a total number of words in the document N_f to develop a profile of document f^nf(w).

14. The method of claim 13, wherein said step of developing a similarity score comprises:

calculating a similarity S(1,2) between a first document and a second document as follows;

15. The method of claim 14, further comprising:

establishing a minimum similarity measure δ

>

0 so that when

16. The method of claim 5, wherein said text relevancy analysis comprises:

scoring a document on the basis of a relevance to a set of keywords.

17. The method of claim 5, wherein said file quality analysis comprises:

assigning a default value to a file quality score.

18. The method of claim 17, further comprising:

automatically or manually adjusting said file quality score.

19. The method of claim 18, wherein said step of adjusting comprises:

determining when a file was last opened or edited; and

assigning a higher file quality score to a file which is opened or edited recently.

20. The method of claim 18, wherein said step of adjusting further comprises:

logging a number of times a file is opened or edited over a period of time; and

assigning a higher file quality score to a file which is opened or edited frequently.

21. The method of claim 5, further comprising:

inputting a keyword into a search interface;

feeding the keyword to a hit list generator; and

outputting a hit list of same hits, accompanied by a corresponding list of text relevance scores.

22. The method of claim 21, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

23. The method of claim 22, wherein said step of outputting a hit list of same hits comprises:

using the keyword to extract said hit list from said inverted index.

24. The method of claim 22, wherein said inverted index includes text extracted from metadata of non-text files.

25. The method of claim 21, said step of calculating an importance score comprising:

calculating an importance score W for each document, wherein

W=a(TR)+b(LA)+c(FQS)

TR=text relevance score from text analysis,

LA=link analysis score,

FQS=file quality score, and

a, b, and c are tuning parameter weights.

26. The method of claim 25, further comprising:

adjusting any of the weights a, b, or c.

27. The method of claim 26, further comprising:

rearranging said hit list into a ranked list.

28. The method of claim 27, further comprising:

truncating said ranked list.

29. The method of claim 28, further comprising:

displaying said ranked list.

30. The method of claim 23, further comprising:

inputting a second keyword into a search interface;

feeding the second keyword to said hit list generator; and

outputting a second hit list of same hits, accompanied by a corresponding second list of text relevance scores.

31. The method of claim 30, wherein said step of outputting a hit list of same hits comprises:

using the second keyword to extract said second hit list from said inverted index.

32. The method of claim 31, further comprising:

forming a subgraph from said second hit list and all links among the documents in said second hit list,

obtaining restricted link analysis scores LA (sub) for each of said documents in said second hit list by performing link analysis on the subgraph, and

said step of calculating an importance score including calculating a second importance score W for each document, wherein

W=a(TR)+b(LA(sub))+c(FQS)

TR=text relevance score from text analysis,

LA (sub) subgraph link analysis score,

FQS=file quality score, and

a, b, and c are tuning parameter weights.

33. The method of claim 32, further comprising:

adjusting any of the weights a, b, or c.

34. The method of claim 33, further comprising:

rearranging said second hit list into a second ranked list.

35. The method of claim 34, further comprising:

truncating said second ranked list.

36. The method of claim 35, further comprising:

displaying said second ranked list.

37. The method of claim 5, further comprising:

navigating between documents scored in said scoring step.

38. The method of claim 37, wherein said step of navigating comprises:

starting at a start file O, said start file O being one of an initial file or a currently open file.

39. The method of claim 38, wherein said step of navigating further comprises:

identifying neighbors B of the start file O, said neighbors B having a similarity score S(O,B) with respect to file O which is greater than a threshold value S_min.

40. The method of claim 39, wherein said similarity score S(O,B) is non-zero.

41. The method of claim 38, wherein said step of identifying neighbors B comprises:

identifying neighbors of the start file O, said neighbors B having at least one of;

a directed link pointing from B to O, and

a directed link pointing from O to B.

42. The method of claim 39, wherein said step of navigating further comprises:

comparing documents pairwise; and

developing a similarity score.

43. The method of claim 42, wherein said step of comparing documents pairwise comprises:

counting a number of times N_f(w) that a word w occurs in a document f; and

dividing N_f(w) by a total number of words in the document N_f to develop a profile of document f^nf(w).

44. The method of claim 43, wherein said step of developing a similarity score comprises:

calculating a similarity S(1,2) between a first document and a second document as follows;

45. The method of claim 44, further comprising:

establishing a minimum similarity measure δ

≦

0 so that when

46. The method of claim 42, further comprising:

storing said similarity score in a similarity score database.

47. The method of claim 46, further comprising:

calculating a similarity navigation score SNW(O,B), where

SNW(O,B)=g·

S(O,B)+h·

LA(B)+m·

FQS(B),

LA(B) is the link analysis score of B, FQS(B) is the file quality score of B, and g, h, and m are tuning parameters.

48. The method of claim 47, further comprising:

ranking similarity-linked files to provide ranked similarity-linked files.

49. The method of claim 48, further comprising:

truncating said ranked similarity-linked files.

50. The method of claim 49, further comprising:

displaying said ranked similarity-linked files.

51. The method of claim 50, further comprising:

jumping to a similarity-linked file.

52. The method of claim 39, further comprising:

inputting keywords,

obtaining a hit list for said keywords, and

restricting the neighbors to be displayed to those neighbors which are found on the hit list.

53. The method of claim 52, further comprising:

forming a subgraph from said hit list and all links among the documents in said hit list,

obtaining restricted link analysis scores LA (sub) for each of said documents by performing link analysis on said subgraph, and

ranking the neighbors according to the subgraph similarity neighbor score

SNW(sub)(O,B)=g·

S(O,B)+h·

LA(sub)(B)+m·

FQS(B),

where g, h, and m are tuning parameters.

54. The method of claim 53, further comprising:

ranking similarity-linked files to provide ranked similarity-linked files.

55. The method of claim 54, further comprising:

truncating said ranked similarity-linked files.

56. The method of claim 55, further comprising:

displaying said ranked similarity-linked files.

57. The method of claim 56, further comprising:

jumping to a similarity-linked file.

58. The method of claim 41, further comprising:

establishing a hyperlink between a first document and a second document, wherein said step of establishing a hyperlink comprises one of;

anchoring said hyperlink in text of one of said first and second documents, and

linking said first and second document with an unanchored hyperlink, wherein

said step of establishing a hyperlink further comprises one of;

entering said hyperlink via an input terminal, and

establishing said hyperlink automatically.

59. The method of claim 58, wherein said directed, weighted link may or may not be anchored to text on a pointing or a pointed-to document.

60. The method of claim 58, further comprising:

storing hyperlink information (pointing file, pointed-to file, hyperlink weight, and anchoring text) in a link structure database.

61. The method of claim 60, further comprising:

identifying a hyperlink neighborhood of a start file O, said hyperlink neighborhood being composed of at least one of;

all files B having directed links pointing to O, and

all files B which are pointed to by O.

62. The method of claim 61, wherein a hyperlink neighbor score (HNW) is calculated for each file in said hyperlink neighborhood, according to the following formula:

HNW=d(HLW)+e(LA)+f(FQS),

where HLW=a hyperlink weight, LA is a link analysis score for the neighbor, FQS equals a file quality score for the neighbor, and d, e, and f are tuning parameters.

63. The method of claim 62, further comprising:

ranking said hyperlink neighborhood according to a corresponding hyperlink neighbor score.

64. The method of claim 63, further comprising:

truncating said hyperlink neighborhood.

65. The method of claim 64, further comprising:

displaying said hyperlink neighborhood.

66. The method of claim 65, further comprising:

jumping to a file within said hyperlink neighborhood.

67. The method of claim 61, further comprising:

inputting a keyword,

obtaining a hit list for said keyword, and

restricting neighbors to be displayed to those neighbors which are found on the hit list.

68. The method of claim 67, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

69. The method of claim 68, wherein said step of obtaining a hit list comprises:

using the keyword to extract said hit list from said inverted index.

70. The method of claim 68, wherein said inverted index includes text extracted from metadata of non-text files.

71. The method of claim 69, further comprising:

forming a subgraph from said second hit list and all links among the documents in said second hit list,

obtaining restricted link analysis scores LA (sub) for each of said documents in said second hit list by performing link analysis on the subgraph, and

ranking the neighbors according to the subgraph hyperlink neighbor score

HNW(sub)=d(HLW)+e(LA(sub))+f(FQS),

where HLW =a hyperlink weight, and d, e, and f are tuning parameters.

72. The method of claim 71, further comprising:

ranking said hyperlink neighborhood according to a corresponding subgraph hyperlink neighbor score.

73. The method of claim 72, further comprising:

truncating said hyperlink neighborhood.

74. The method of claim 73, further comprising:

displaying said hyperlink neighborhood.

75. The method of claim 74, further comprising:

jumping to a file within said hyperlink neighborhood.

76. The method of claim 21, further comprising:

searching shared-access files of one or more defined groups co-hosted in a common environment;

searching files which are stored on a network;

searching files of an enterprise; and

searching physical objects.

77. The method of claim 37, wherein said step of navigating comprises:

navigating among shared-access files of one or more defined groups co-hosted in a common environment;

navigating among files which are stored on a network;

navigating among files of an enterprise; and

navigating among physical objects.

78. The method of claim 76 or claim 77, wherein accessing said shared-access files of one or more defined groups comprises:

connecting a first subgraph of said one or more defined groups with a second subgraph of said one or more defined groups.

79. The method of claim 78, further comprising:

establishing hyperlinks which point from a selected file; and

modifying a file quality score of the selected file, wherein

said steps of establishing and modifying are restricted to a user with write permission for the selected file.

80. The method of claim 79, wherein said step of modifying a file quality score comprises:

averaging a plurality of file quality scores.

81. The method of claim 79, further comprising:

modifying said file quality score by any user having file read permission.

82. The method of claim 79 wherein said user is a member of at least two groups each with distinct read and write privileges.

83. The method of claim 82, further comprising:

performing link analysis of a graph that encompasses all documents available to said at least two groups.

84. The method of claim 82, further comprising:

performing link analysis of a subgraph that encompasses all documents available to a first of said at least two groups under a corresponding first read permission; and

performing link analysis of a subgraph that encompasses all documents available to a second of said at least two groups under a corresponding second read permission.

85. The method of claim 82, further comprising:

performing link analysis of a subgraph that encompasses all documents available to a user.

86. A tangible computer readable storage medium having stored thereon a program that when executed performs a method of searching electronic material stored in a computing environment, said method comprising:

providing a plurality of documents;

determining an undirected, weighted link between at least two of said plurality of documents, based on similarity;

determining a directed, weighted link between at least two of said plurality of documents;

adding said determined undirected, weighted links to said determined directed, weighted links to create a hybrid web having links; and

performing a link analysis algorithm taking the links of said hybrid web as its input, said algorithm including at least one of forward link analysis and backward link analysis, wherein

the output of said algorithm is a set of link analysis scores.

87. The tangible computer readable storage medium according to claim 86, wherein said algorithm is eigenvector based.

88. The tangible computer readable storage medium according to claim 86, wherein said at least one of forward and backward link analysis comprises using at least one of a non-compound Forward operator and a non-compound Backward operator.

89. The tangible computer readable storage medium according to claim 86, wherein said at least one of forward and backward link analysis comprises using at least one of a non-normalized Forward operator and a non-normalized backward operator.

90. The tangible computer readable storage medium of claim 86, further comprising instructions for:

scoring each of said at least two documents via at least one of text relevancy analysis and file quality analysis.

91. The tangible computer readable storage medium of claim 86, wherein the instructions for determining a directed, weighted link between at least two of said plurality of documents includes instructions for establishing a hyperlink between a first document and a second document, wherein said instructions for establishing a hyperlink comprises instructions for one of:

anchoring said hyperlink in text of one of said first and second documents,

linking said first and second document with an unanchored hyperlink, wherein

said instructions for establishing a hyperlink further comprises instructions for one of;

entering said hyperlink via an input terminal, and

establishing said hyperlink automatically.

92. A search device configured to search electronic material stored in a computing environment, comprising:

means for providing a plurality of documents;

means for determining an undirected, weighted link between at least two of said plurality of documents, based on similarity;

means for determining a directed, weighted link between at least two of said plurality of documents;

means for adding said determined undirected, weighted links to said determined directed, weighted links to create a hybrid web having links; and

means for performing a link analysis algorithm taking the links of said hybrid web as its input, said algorithm including at least one of forward link analysis and backward link analysis, wherein

the output of said algorithm is a set of link analysis scores.

93. The search device according to claim 92, wherein said algorithm is eigenvector based.

94. The search device according to claim 92, wherein said at least one of forward and backward link analysis comprises using at least one of a non-compound Forward operator and a non-compound Backward operator.

95. The search device according to claim 92, wherein said at least one of forward and backward link analysis comprises using at least one of a non-normalized Forward operator and a non-normalized Backward operator.

96. The search device of claim 92, further comprising:

means for scoring each of said at least two documents via at least one of text relevancy analysis and file quality analysis.

97. The search device of claim 92, wherein the means for determining a directed, weighted link between at least two of said plurality of documents includes means for establishing a hyperlink between a first document and a second document, wherein said means for establishing a hyperlink comprises one of:

means for anchoring said hyperlink in text of one of said first and second documents,

means for linking said first and second document with an unanchored hyperlink, wherein

said means for establishing a hyperlink further comprises one of;

means for entering said hyperlink via an input terminal, and

means for establishing said hyperlink automatically.