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

• US 20060059144A1
• Filed: 09/16/2005
• Published: 03/16/2006
• Est. Priority Date: 09/16/2004
• Status: Active Grant

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth
• Granted Patent: US 7,680,812 B2
• Time in Patent Office: Days
• 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, comprising:

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

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

calculating a weight each of said at least two documents.

2. The method of claim 1, further comprising:

scoring each of said at least two documents via at least one of

link analysis,

text relevancy analysis, and

file quality analysis.

3. The method of claim 2, wherein said link analysis is based on a hybrid web, said hybrid web consisting of two kinds of links between documents, that is,

directed links, and

undirected links.

4. The method of claim 3, 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,

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.

5. The method of claim 4, wherein said directed, weight link may or may not be anchored to text on a pointing or a pointed-to document.

6. The method of claim 4, further comprising:

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

7. The method of claim 3, further comprising:

performing at least one of forward and backward link analysis.

8. The method of claim 3, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

9. The method of claim 8, further comprising:

comparing documents pairwise; and

developing a similarity score.

10. The method of claim 9, further comprising:

storing said similarity score in a similarity score database.

11. The method of claim 9, 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 n_f(w).

12. The method of claim 11, 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;

$S<br><br>\left(1,2\right)=K<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{w}{\sum <br><br>}<br><br>\sqrt{n_1<br><br>\left(w\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>n_2<br><br>\left(w\right)}$

where K is a tuning parameter.

13. The method of claim 12, further comprising:

establishing a minimum similarity measure δ

>

0 so that when

$\begin{array}{cc}K<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{w}{\sum <br><br>}<br><br>\sqrt{n_1<br><br>\left(w\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>n_2<br><br>\left(w\right)}<<br><br>\mathrm{\delta <br><br>},& S<br><br>\left(1,2\right)=\mathrm{\delta <br><br>}.\end{array}$

14. The method of claim 2, wherein said text analysis comprises:

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

15. The method of claim 2, wherein said file quality analysis comprises:

assigning a default value to a file quality score.

16. The method of claim 15, further comprising:

automatically or manually adjusting said file quality score.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

19. The method of claim 2, 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.

20. The method of claim 19, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

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

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

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

23. The method of claim 21, further comprising:

calculating a weight 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 parameters.

24. The method of claim 23, further comprising:

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

25. The method of claim 24, further comprising:

rearranging said hit list into a ranked list.

26. The method of claim 25, further comprising:

truncating said ranked list.

27. The method of claim 26, further comprising:

displaying said ranked list.

28. The method of claim 21, 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.

29. The method of claim 28, 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.

30. The method of claim 29, 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

calculating a second weight 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 parameters.

31. The method of claim 30, further comprising:

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

32. The method of claim 31, further comprising:

rearranging said second hit list into a second ranked list.

33. The method of claim 32, further comprising:

truncating said second ranked list.

34. The method of claim 33, further comprising:

displaying said second ranked list.

35. The method of claim 2, further comprising:

navigating between documents scored in said scoring step.

36. The method of claim 35, 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.

37. The method of claim 36, 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.

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

39. The method of claim 36, 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.

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

comparing documents pairwise; and

developing a similarity score.

41. The method of claim 40, 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 n_f(w).

42. The method of claim 41, 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;

$S<br><br>\left(1,2\right)=K<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{w}{\sum <br><br>}<br><br>\sqrt{n_1<br><br>\left(w\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>n_2<br><br>\left(w\right)}.$

43. The method of claim 42, further comprising:

establishing a minimum similarity measure δ

>

0 so that when

$\begin{array}{cc}K<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{w}{\sum <br><br>}<br><br>\sqrt{n_1<br><br>\left(w\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>n_2<br><br>\left(w\right)}<<br><br>\mathrm{\delta <br><br>},& S<br><br>\left(1,2\right)=\mathrm{\delta <br><br>}.\end{array}$

44. The method of claim 40, further comprising:

storing said similarity score in a similarity score database.

45. The method of claim 44, further comprising:

calculating a similarity navigation weight 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.

46. The method of claim 45, further comprising:

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

47. The method of claim 46, further comprising:

truncating said ranked similarity-linked files.

48. The method of claim 47, further comprising:

displaying said ranked similarity-linked files.

49. The method of claim 48, further comprising:

jumping to a similarity-linked file.

50. The method of claim 37, 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.

51. The method of claim 50, 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 weight

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

S(O,B)+h·

LA(sub)(B)+m·

FQS(B).

52. The method of claim 51, further comprising:

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

53. The method of claim 52, further comprising:

truncating said ranked similarity-linked files.

54. The method of claim 53, further comprising:

displaying said ranked similarity-linked files.

55. The method of claim 54, further comprising:

jumping to a similarity-linked file.

56. The method of claim 39, 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.

57. The method of claim 56, wherein said directed, weight link may or may not be anchored to text on a pointing or a pointed-to document.

58. The method of claim 56, further comprising:

storing hyperlink information (pointing file, pointed-to file, hyperlink weight,

and anchoring text) in a link structure database.

59. The method of claim 58, 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.

60. The method of claim 59, wherein a hyperlink neighbor weight (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.

61. The method of claim 60, further comprising:

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

62. The method of claim 61, further comprising:

truncating said hyperlink neighborhood.

63. The method of claim 62, further comprising:

displaying said hyperlink neighborhood.

64. The method of claim 63, further comprising:

jumping to a file within said hyperlink neighborhood.

65. The method of claim 59, 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.

66. The method of claim 65, further comprising:

crawling a file system;

scanning text of files within said file system; and

building an inverted index.

67. The method of claim 66, wherein said step of obtaining a hit list comprises:

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

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

69. The method of claim 67, 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 weight

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

70. The method of claim 69, further comprising:

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

71. The method of claim 70, further comprising:

truncating said hyperlink neighborhood.

72. The method of claim 71, further comprising:

displaying said hyperlink neighborhood.

73. The method of claim 72, further comprising:

jumping to a file within said hyperlink neighborhood.

74. The method of claim 19, 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.

75. The method of claim 35, 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.

76. The method of claim 74 or claim 75, wherein said step of searching or navigating over 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

77. The method of claim 76, 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.

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

averaging a plurality of file quality scores.

79. The method of claim 77, further comprising:

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

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

81. The method of claim 80, further comprising:

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

82. The method of claim 80, 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.

83. The method of claim 80, further comprising:

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

84. A computer program product comprising a computer readable medium including instructions for searching electronic material stored in a computing environment, said instructions comprising instructions for:

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

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

calculating a weight each of said at least two documents.

85. The computer program product of claim 84, further comprising instructions for:

scoring each of said at least two documents via at least one of

link analysis,

text relevancy analysis, and

file quality analysis.

86. The computer program product of claim 85, wherein said link analysis is based on a hybrid web, said hybrid web consisting of two kinds of links between documents, that is,

directed links, and

undirected links.

87. The computer program product of claim 85, wherein said text analysis comprises:

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

88. The computer program product of claim 85, wherein said file quality analysis comprises:

assigning a default value to a file quality score.

89. The computer program product of claim 85, further comprising instructions for:

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.

90. The computer program product of claim 85, further comprising instructions for:

navigating between documents scored in said scoring step.

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

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

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

means for calculating a weight each of said at least two documents.

92. The search device of claim 91, further comprising instructions for:

means for scoring each of said at least two documents via at least one of

link analysis,

text relevancy analysis, and

file quality analysis.

93. The search device of claim 92, wherein said link analysis is based on a hybrid web, said hybrid web consisting of two kinds of links between documents, that is,

directed links, and

undirected links.

94. The search device of claim 92, wherein said text analysis comprises:

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

95. The search device of claim 92, wherein said file quality analysis comprises:

means for assigning a default value to a file quality score.

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

means for inputting a keyword into a search interface;

means for feeding the keyword to a hit list generator; and

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

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

means for navigating between documents scored in said scoring step.