Automatic index term augmentation in document retrieval

• US 6,850,935 B1
• Filed: 06/19/2000
• Issued: 02/01/2005
• 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): Pardo, Thuy N.
• Application Number:
  US09/596,583
• Time in Patent Office: 1,688 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/6, 707/10, 707/501
• 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 automatically assigning index terms to electronic documents such as Web pages or sites in a manner which may be used to facilitate the retrieval of electronic documents of interest. The method involves determining co-occurrences of terms in other documents with the electronic document, and selecting terms as index terms based upon those scores. The method permits the efficient retrieval of electronic documents.

Claims

1. A method for automatically choosing index terms to be associated with a document D, for purposes of facilitating document retrieval processes, comprising:

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

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

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

selecting I_T terms for use as index terms for document D from among terms in the N₀ documents based upon the co-occurrence of terms in the N₀ documents with terms in the document D.

2. The method of claim 1, further comprising selecting the I_T terms for use as index terms for document D 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:

C_n (T_j, T_k)=log₁₀(co_ki(T_j,T_k)+1)*idf(T_k)/log₁₀(N₀), $\mathrm{where}<br><br>\text{;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{co}}_{\mathrm{ki}}<br><br>\left(T_j,T_k\right)=\underset{n=1}{\overset{N_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{tf}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(T_k,n\right)*\mathrm{tf}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(T_j,n\right)$

tf (T_k, n)=number of occurrences of term T_k in document n in the N₀ documents,

tf (T_j, n)=number of occurrences of term T_j in document n in the N₀ documents,

idf (T_k)=the inverted document frequency for the term T_k,

=min (1.0, log₁₀ (N/N_T)/5.0)

N=the number of documents in the collection C₀ over which the query Q was run,

N_T=the number of documents in the collection C₀ over which the query Q was run, which contained the term T_k

(b) calculating, for terms T_k which occur in the N₀ documents selected, the co-occurrencef_D (T_k) of that term T_k with document D;

$f_D<br><br>\left(T_k\right)=\underset{j=1}{\overset{T_0}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(\mathrm{\delta <br><br>}+C_{\mathrm{ni}}<br><br>\left(T_k,T_j\right)\right)}^{\mathrm{idf}<br><br>\left(T_j\right)}$

where

T_j=a term in document D,

T₀=the number of terms in document D,

idf (T_j)=the inverted document frequency for the term T_j,

=min (1.0, log₁₀ (N/N₁)/5.0),

N=the number of documents in the collection C₀ over which the query Q was run,

N_j=the number of documents in the collection C₀ over which the query Q was run, which contained the term T_j and

δ

=a constant; and

(c) selecting I_T terms for use as index terms for document D from among terms in the N₀ documents based upon the scores f_D (T_k) achieved by the terms.

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

4. The method of claim 2, wherein the documents are Web sites.

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

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

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

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

=N_TD/(N_TD+K₁+K₂*(L_D/L_O)),

where;

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L_O is the average length of documents in the collection C₀ to be searched, and

K₁ and K₂ are constants

and IDF_T=log((N+K3)/N_T)/ log (N+K₄)

where;

N is the number of documents in the collection C₀ to be searched

N_T is the number of documents containing the term T in the collection C₀ to be searched,

K₃ and K₄ are constants.

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

10. The method of claim 2, wherein all terms whose scores f_D (T_k) exceed a given cutoff score are selected for use as index terms.

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

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

13. The method of claim 12, wherein the number N₀ is 50.

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

15. The method of claim 2, wherein co-occurrences f_D (T_k) are calculated for all terms contained in the N₀ documents selected.

16. The method of claim 2, wherein co-occurrences f_D (T_k) are calculated for all terms contained in the N₀ documents selected, except that preselected stop terms are eliminated.

17. The method of claim 2, wherein δ

=0.01.

18. The method of claim 2, wherein the number I_T of terms chosen as index terms is predetermined.

19. The method of claim 17, wherein the number I_T is 30.

20. A device for automatically choosing index terms to be associated with a document D, for purposes of facilitating document retrieval processes, comprising:

(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 use as index terms for document D from among terms in the N₀ documents based upon the co-occurrence of terms in the N₀ documents with terms in the document D.

21. The device of claim 20, further comprising means for selecting the I_T terms for use as index terms for document D, which means are comprised of

(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 that term T_k with terms T_j in document D:

C_n (T_j, T_k)=log₁₀(co_ki(T_j,T_k)+1)*idf(T_k)/ log₁₀(N₀), $\mathrm{where}<br><br>\text{;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{co}}_{\mathrm{ki}}<br><br>\left(T_j,T_k\right)=\underset{n=1}{\overset{N_0}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{tf}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(T_k,n\right)*\mathrm{tf}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(T_j,n\right).$

tf (T_k, n)=number of occurrences of term T_k in document n in the N₀ documents,

tf (T_j, n)=number of occurrences of term T_j in document n in the N₀ documents,

idf(T_k)=the inverted document frequency for the term T_k,

=min (1.0, log₁₀ (N/N_T)/5.0)

 

N=the number of documents in the collection C₀ over which the query Q was run,

 

N_T=the number of documents in the collection C₀ over which the query Q was run, which contained the term T_k

(b) means for calculating, for terms T_k which occur in the N₀ documents selected, the co-occurrence f_D (T_k) of that term T_k with document D;

$f_D<br><br>\left(T_k\right)=\underset{j=1}{\overset{T_0}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(\mathrm{\delta <br><br>}+C_{\mathrm{ni}}<br><br>\left(T_k,T_j\right)\right)}^{\mathrm{idf}<br><br>\left(T_j\right)}$

where

T_j=a term in document D,

T₀=the number of terms in document D,

idf(T_j)=the inverted document frequency for the term T_j,

=min (1.0, log₁₀(N/N₁)/5.0),

 

N=the number of documents in the collection C₀ over which the query Q was run,

 

N_J=the number of documents in the collection C₀ over which the query Q was run, which contained the term T_j and

δ

=a constant; and

(c) means for selecting I_T terms for use as index terms for document D from among terms in the N₀ documents based upon the scores f_D (T_k) achieved by the terms.

22. The device of claim 21, wherein the documents are Web pages.

23. The device of claim 21, wherein the documents are Web sites.

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

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

26. The device of claim 21, 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.

27. The device of claim 26, 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,

=N_TD/(N_TD+K₁+K₂*(L_D/L_O)),

where;

N_TD is the number of times the term T occurs in document D,

L_D is the length of document D,

L_O is the average length of documents in the collection C₀ to be searched, and

K₁ and K₂ are constants

and IDF_T=log ((N+K₃)/N_T)/ log (N+K₄)

where;

N is the number of documents in the collection C₀ to be searched

N_T is the number of documents containing the term T in the collection C₀ to be searched,

K₃ and K₄ are constants.

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

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

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

31. The device of claim 30, wherein the number N₀ is 50.

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

33. The device of claim 21, wherein co-occurrences f_D (T_k) are calculated for all terms contained in the N₀ documents selected.

34. The device of claim 21, wherein co-occurrences f_D (T_k) are calculated for all terms contained in the N₀ documents selected, except that preselected stop terms are eliminated.

35. The device of claim 21, wherein δ

=0.01.

36. The device of claim 21, wherein the number I_T of terms chosen as index terms is predetermined.

37. The device of claim 36, wherein the number I_T is 30.

38. The device of claim 21, wherein all terms whose scores f_D (T_k) exceed a given cutoff score are selected for use as index terms.

39. A method for automatically assigning-an-index term to a document D, the method comprising:

selecting one or more index terms from a plurality of index terms;

identifying one or more documents of a plurality of documents to which each of the one or more index terms has been assigned;

comparing, for each of the one or more index terms, each of the identified documents to the document D;

determining a score for each of the one or more index terms based on the comparing; and

assigning the index term associated with the highest score to the document D.

40. The method of claim 39 wherein the comparing includes:

determining a log likelihood ratio between each of the identified documents and the document D.

41. The method of claim 39 wherein the score is a total score based on scores for each of the identified documents.

42. The method of claim 39 wherein the assigning includes:

assigning a predetermined number of the index terms associated with the highest scores to the document D.

43. A device for automatically assigning an index term to a document D, the device comprising:

means for selecting one or more index terms from a plurality of index terms;

means for identifying one or more documents of a plurality of documents to which each of the one or more index terms has been assigned;

means for comparing, for each of the one or more index terms, each of the identified documents to the document D;

means for determining a score for each of the one or more index terms based on the comparing; and

means for assigning the index term associated with the highest score to the document D.

44. The device of claim 43 wherein the means for comparing includes:

means for determining a log likelihood ratio between each of the identified documents and the document D.

45. The device of claim 43 wherein the score is a total score based on scores for each of the identified documents.

46. The device of claim 43 wherein the means for assigning includes:

means for assigning a predetermined number of the index terms associated with the highest scores to the document D.