Generalized term frequency scores in information retrieval systems

• US 6,507,839 B1
• Filed: 06/19/2000
• Issued: 01/14/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Ponte, Jay Michael
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US09/596,616
• Time in Patent Office: 939 Days
• Field of Search: 707/1, 707/3, 707/4, 707/6, 707/10, 707/100, 345/327
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/944 Business related
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Disclosed are methods and systems for selecting electronic documents, such as Web pages or sites, from among documents in a collection, based upon the occurrence of selected terms in segments of the documents. The method may be applied where index terms have previously been assigned to the documents. The method may be used to select supercategories of banner advertisements from which to choose an advertisement to display for a user.

Claims

1. A method for selecting documents which may be of interest from among documents in a collection, comprising:

(a) choosing terms to be used in selecting documents which may be of interest,

(b) dividing a plurality of documents D in the collection into S₀ segments,

(c) determining, for the plurality of documents D in the collection, which of the terms chosen to be used in selecting documents are found in each segment S_i of the document D,

(d) calculating, for the plurality of documents D in the collection a generalized term frequency score S_D;

$S_D=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br>{\mathrm{TF}}_{\mathrm{STD}}$

 

where;

S_D is the total score for the document D,

T₀ is the number of terms selected to be used in the search,

S₀ is the number of segments in the document D, and

TF_STD is the score for document D based on the occurrence of term T in segment S_i of document D, and

(e) selecting documents from among the documents in the collection based upon the scores S_D achieved by the documents.

2. The method of claim 1, wherein the documents are Web pages.

3. The method of claim 1, wherein the documents are Web sites.

4. The method of claim 1, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms used in a search query.

5. The method of claim 1, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms used in a search query, with preselected stop terms eliminated.

6. The method of claim 1 wherein additional terms are chosen to be used in selecting documents which may be of interest based upon the terms used in the search query.

7. The method of claim 1, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms in a document identified as having characteristics that are desired in the documents to be selected.

8. The method of claim 1, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms in a document identified as having characteristics that are desired in the documents to be selected, with preselected stop terms eliminated.

9. The method of claim 1, wherein additional terms are chosen to be used in selecting documents based upon the terms which occur in the document identified as having characteristics that are desired in the documents to be selected.

10. The method of claim 1, wherein the terms chosen to be used in selecting documents comprise the terms in a document being accessed by a user.

11. The method of claim 1, wherein the terms chosen to be used in selecting documents comprise the terms in a document being accessed by a user, with preselected stop terms eliminated.

12. The method of claim 1, wherein additional terms are chosen to be used in selecting documents based upon the terms which occur in the document being accessed by the user.

13. The method of claim 1, wherein the documents in the collection are ranked in order of their generalized term frequency scores S_D, and a predetermined number N of documents with the highest scores is selected.

14. The method of claim 1, wherein all documents with generalized term frequency scores S_D above a predetermined cutoff score S are selected.

15. The method of claim 1, wherein, for the plurality of documents D in the collection, a weight W_SD is assigned to each segment S_i of the document, and the generalized term frequency score S_D for a document D is based upon Robertson'"'"'s term frequency score, such that:

$S_D=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{TF}}_{\mathrm{STD}}*{\mathrm{IDF}}_{\mathrm{ST}}$

where;

S_D is the total score for the document D,

T₀ is the number of terms which occur in the collection of terms included in the search,

S₀ is the number of segments in the document D,

TF_STD=Robertson'"'"'s generalized term frequency for Term T in Segment S_i of Document D

16. The method of claim 15, wherein K₁=0.5, K₂=1.5, K₃=0.5, and K₄=1.0.

17. The method of claim 15, wherein the weights W_iD assigned to the i^th segment of the documents in the collection are equal.

18. The method of claim 17, wherein the weights W_SD assigned to the segments of a document D in the collection have the property that $\sum _{}^{}$

Si=1S0

 



WSD=1.

19. The method of claim 17, wherein the weights W_iD are selected specifically for the collection of documents from which documents are to be chosen by carrying out test searches with different weights, and selecting for use the weights which yield the most useful results.

20. The method of claim 1, wherein

(a) additional terms are assigned to each document D in the collection, beyond the terms that occur in the document D, based upon the characteristics of the document D, without regard to the occurrence of the additional terms in the document D, and

(b) the additional terms are placed in a segment S_i of the document D with no other terms.

21. The method of claim 15, wherein

(a) additional terms are assigned to each document D in the collection, beyond the terms that occur in the document D, based upon the characteristics of the document D, without regard to the occurrence of the additional terms in the document D, and

(b) the additional terms are placed in a segment S_i of the document D with no other terms.

22. The method of claim 21, wherein the additional terms are assigned automatically by

(a) creating a search query Q comprised of terms in document D;

(b) applying the search query Q to a collection of documents C₀;

(c) selecting the N₀ documents from the collection of documents C₀ which achieve the highest scores upon application of the search query Q; and

(d) selecting I_T terms for automatic assignment from among terms in the N₀ documents based upon the co-occurrence of terms in the N₀ documents with terms in the document D.

23. The method of claim 22, further comprising selecting the I_T terms for automatic assignment by

(a) calculating, for terms T_k which occur in the N₀ documents selected, the co-occurrence C_n (T_j,T_k) of the term T_k with terms T_j in document D:

24. The method of claim 23, wherein W_STD, the weight assigned to term T in segment S_I of document D, is f_D (T_k) for all terms T automatically assigned.

25. The method of claim 24, wherein W_STD, the weight assigned to term T in segment S_i of document D, is 1.0 for all terms T which occur in the document D.

26. The method of claim 23, wherein the search query Q which is applied comprises all of the terms in document D.

27. The method of claim 23, wherein the search query Q which is applied comprises all of the terms in document D with preselected stop terms eliminated.

28. The method of claim 23, wherein the search query Q is applied to select documents from among the documents in the collection C₀ by calculating for each document D in the collection C₀ a score S_D based upon the occurrence in the document D of terms in the search query Q.

29. The method of claim 28, wherein in applying the search query Q to the collection of documents C₀ the total score S_D for a document D in the collection C₀ is $S_D=\sum _{}^{}$

T=1T0

 



TFTD*IDFT

where;

T₀ is the number of terms in the search query Q, and

TF_TD is Robertson'"'"'s term frequency for the Term T in the Document D

30. The method of claim 29, wherein K₁ equals 0.5, K₂ equals 1.5, K₃ equals 0.5, and K₄ equals 1.0.

31. The method of claim 23, wherein the number N₀ of documents chosen by application of the search query Q is predetermined.

32. The method of claim 31, wherein the number N₀ is 50.

33. The method of claim 23, wherein all documents whose scores upon application of the search query Q exceed a given cutoff score are selected.

34. The method of claim 23, wherein co-occurrences are calculated for all terms contained in the N₀ documents selected.

35. The method of claim 23, wherein co-occurrences are calculated for all terms contained in the N₀ documents selected, except that preselected stop terms are eliminated.

36. The method of claim 23, wherein δ

=0.01.

37. The method of claim 23, wherein the number I_T of terms automatically assigned is predetermined.

38. The method of claim 37, wherein the number I_T is 30.

39. The method of claim 23, wherein all terms whose scores f_D (T_k) exceed a given cutoff score are automatically assigned.

40. The method of claim 30, wherein the number N₀ of documents chosen by application of the search query Q is 50, δ

=0.01, and the number I_T is 30.

41. A device for selecting documents which may be of interest from among documents in a collection, comprising:

(a) means for choosing terms to be used in selecting documents which may be of interest,

(b) means for dividing a plurality of documents D in the collection into S₀ segments,

(c) means for determining which of the terms chosen to be used in selecting documents are found in each segment S_i of a plurality of documents D in the collection,

(d) means for calculating a generalized term frequency score S_D for a plurality of documents D in the collection;

$S_D=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br>{\mathrm{TF}}_{\mathrm{STD}}$

 

where;

S_D is the total score for the document D,

T₀ is the number of terms selected to be used in the search,

S₀ is the number of segments in the document D, and

TF_STD is the score for document D based on the occurrence of term T in segment S_i of document D, and

(e) means for selecting documents from among the documents in the collection based upon the scores S_D achieved by the documents.

42. The device of claim 41, wherein the documents are Web pages.

43. The device of claim 41, wherein the documents are Web sites.

44. The device of claim 41, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms used in a search query.

45. The device of claim 41, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms used in a search query, with preselected stop terms eliminated.

46. The device of claim 41, wherein additional terms are chosen to be used in selecting documents which may be of interest based upon the terms used in the search query.

47. The device of claim 41, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms in a document identified as having characteristics that are desired in the documents to be selected.

48. The device of claim 41, wherein the terms chosen to be used in selecting documents which may be of interest comprise the terms in a document identified as having characteristics that are desired in the documents to be selected, with preselected stop terms eliminated.

49. The device of claim 41, wherein additional terms are chosen to be used in selecting documents based upon the terms which occur in the document identified as having characteristics that are desired in the documents to be selected.

50. The device of claim 41, wherein the terms chosen to be used in selecting documents comprise the terms in a document being accessed by a user.

51. The device of claim 41, wherein the terms chosen to be used in selecting documents comprise the terms in a document being accessed by a user, with preselected stop terms eliminated.

52. The device of claim 41, wherein additional terms are chosen to be used in selecting documents based upon the terms which occur in the document being accessed by the user.

53. The device of claim 41, wherein the documents in the collection are ranked in order of their generalized term frequency scores S_D, and a predetermined number N of documents with the highest scores is selected.

54. The device of claim 41, wherein all documents with generalized term frequency scores S_D above a predetermined cutoff score S are selected.

55. The device of claim 41, further comprising means for assigning a weight W_SD to each segment S_i of a plurality of documents D in the collection, wherein the generalized term frequency score S_D for a document D is based upon Robertson'"'"'s term frequency score, such that:

$S_D=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{TF}}_{\mathrm{STD}}*{\mathrm{IDF}}_{\mathrm{ST}}$

where;

S_D is the total score for the document D,

T₀ is the number of terms which occur in the collection of terms included in the search,

S₀ is the number of segments in the document D,

TF_STD=Robertson'"'"'s generalized term frequency for Term T in Segment S_i of Document D

56. The device of claim 55, wherein K₁=0.5, K₂=1.5, K₃=0.5, and K₄=1.0.

57. The device of claim 55, wherein the weights W_iD assigned to the i^th segment of the documents in the collection are equal.

58. The device of claim 57, wherein the weights W_SD assigned to the segments of a document D in the collection have the property that $\sum _{}^{}$

Si=1S0

 



WSD=1.

59. The device of claim 57, wherein the weights W_iD are selected specifically for the collection of documents from which documents are to be chosen by carrying out test searches with different weights, and selecting for use the weights which yield the most useful results.

60. The device of claim 41, further comprising

(a) means for assigning additional terms to each document D in the collection, beyond the terms that occur in the document D, based upon the characteristics of the document D, without regard to the occurrence of the additional terms in the document D, and

(b) means for placing the additional terms in a segment S_i of the document D with no other terms.

61. The device of claim 55, further comprising

(a) means for assigning additional terms to each document D in the collection, beyond the terms that occur in the document D, based upon the characteristics of the document D, without regard to the occurrence of the additional terms in the document D, and

(b) means for placing the additional terms in a segment S_i of the document D with no other terms.

62. The device of claim 61, wherein the means for assigning additional terms comprise:

(a) means for creating a search query Q comprised of terms in document D;

(b) means for applying the search query Q to a collection of documents C₀;

(c) means for selecting the N₀ documents from the collection of documents C₀ which achieve the highest scores upon application of the search query Q; and

(d) means for selecting I_T terms for automatic assignment from among terms in the N₀ documents based upon the co-occurrence of the terms in the N₀ documents with the terms in the document D.

63. The device of claim 62, wherein the means for selecting the I_T terms for automatic assignment further comprise

(a) means for calculating, for terms T_k which occur in the N₀ documents selected, the co-occurrence C_n (T_j,T_k) of the term T_k with terms T_j in document D:

64. The device of claim 63, wherein W_STD, the weight assigned to term T in segment S_I of document D, is f_D (T_n) for all terms T chosen to be index terms.

65. The device of claim 64, wherein W_STD, the weight assigned to term T in segment S_i of document D, is 1.0 for all terms T which occur in the document D.

66. The device of claim 63, wherein the search query Q which is applied comprises all of the terms in document D.

67. The device of claim 63, wherein the search query Q which is applied comprises all of the terms in document D with preselected stop terms eliminated.

68. The device of claim 63, wherein the search query Q is applied to select documents from among the documents in the collection C₀ by calculating for each document D in the collection C₀ a score S_D based upon the occurrence in the document D of terms in the search query Q.

69. The device of claim 68, wherein in applying the search query Q to the collection of documents C₀ the total score S_D for a.document D in the collection C₀ is $S_D=\sum _{}^{}$

T=1T0

TFTD*IDFT

where;

T₀ is the number of terms in the search query Q, and

TF_TD is Robertson'"'"'s term frequency for the Term T in the Document D

70. The device of claim 69, wherein K₁ equals 0.5, K₂ equals 1.5, K₃ equals 0.5, and K₄ equals 1.0.

71. The device of claim 63, wherein the number N₀ of documents chosen by application of the search query Q is predetermined.

72. The device of claim 71, wherein the number N₀ is 50.

73. The device of claim 63, wherein all documents whose scores upon application of the search query Q exceed a given cutoff score are selected.

74. The device of claim 63, wherein co-occurrences are calculated for all terms contained in the N₀ documents selected.

75. The device of claim 63, wherein co-occurrences are calculated for all terms contained in the N₀ documents selected, except that preselected stop terms are eliminated.

76. The device of claim 63, wherein δ

=0.01.

77. The device of claim 63, wherein the number I_T of terms automatically assigned is predetermined.

78. The device of claim 77, wherein the number I_T is 30.

79. The device of claim 63, wherein all terms whose scores f_D (T_k) exceed a given cutoff score are automatically assigned.

80. The device of claim 70, wherein the number N₀ of documents chosen by application of the search query Q is 50, δ

=0.01, and the number I_T is 30.