Use of generalized term frequency scores in information retrieval systems

• US 7,725,424 B1
• Filed: 11/04/2002
• Issued: 05/25/2010
• Est. Priority Date: 03/31/1999
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Ponte, Jay Michael
• Primary Examiner(s): Pardo; Thuy N
• Application Number:
  US10/287,161
• Time in Patent Office: 2,759 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/10, 707/100, 707/7, 707/102, 707/104.1, 709/201, 725/35, 705/3
• US Class Current: 707/715
• 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 presenting banner advertisements to a user who is seeking information about products and/or services, comprising:

(a) defining a collection C₀ of categories of products and/or services,

(b) for a plurality of the categories in the collection C₀ of categories, associating with the category a set of terms which describe the product(s) and/or service(s) associated with the category, and a unique category identifier term,

(c) for a plurality of providers of products and/or services to be utilized, assigning the provider to one or more categories based upon the products and/or services offered by the provider,

(d) assigning a plurality of the categories to supercategories,

(e) for a plurality of the supercategories, associating one or more banner advertisements with the supercategory,

(f) for a plurality of the supercategories, associating with the supercategory the sets of terms which describe the product(s) or service(s) associated with categories assigned to the supercategory, and the category identifier terms which are unique to categories assigned to the supercategory,

(g) in response to a user query Q, comprising terms describing products and/or services of interest to the user, selecting categories, in the collection of categories C₀, which have associated with them a descriptive term for the products and/or services therein which matches a term in the user query,

(h) preparing a new query Q′

comprising the terms in the user query Q, the descriptive terms for the products and/or services associated with the categories selected, and the unique category identifier terms associated with the categories selected,

(i) applying the query Q′

to the collection of supercategories,

(j) selecting the supercategory with the highest score, and

(k) presenting to the user a banner advertisement associated with the supercategory selected.

2. The method of claim 1, wherein the search query Q′

is applied to select a supercategory from among the collection of supercategories by calculating for each supercategory a score S_C based upon the occurrence in the supercategory of terms in the search query Q′

.

3. The method of claim 2, wherein there are approximately 20,000 categories of products and/or services in the collection of categories.

4. The method of claim 3, wherein there are approximately 50 supercategories.

5. The method of claim 2, wherein every category, in the collection of categories C₀, which has associated with it a descriptive term for the products and/or services therein which matches a term in the user query, is presented to the user, and the user is permitted to select from among said categories a category of interest for which a list of the merchants, stores or other sources of product(s) and/or service(s) associated with the category will be presented.

6. The method of claim 5, wherein in response to the user selecting a category from those presented,

(a) a new query Q″

is prepared, comprising the descriptive terms for the product(s) and/or service(s) associated with the category selected, and the unique category identifier term associated with the category selected,

(b) the query Q″

is applied to the collection of supercategories,

(c) the supercategory with the highest score is selected, and

(d) the user is presented with a banner advertisement associated with the supercategory selected.

7. The method of claim 2, wherein the query Q′

is applied to the collection of supercategories by utilizing Robertson'"'"'s term frequency score, such that the score for a supercategory S_C under the query Q′

is determined by;

$S_C=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br><br><br>{\mathrm{TF}}_{\mathrm{TD}}*{\mathrm{IDF}}_T,$

where;

T₀ is the number of terms which occur in the query Q′

_i,

TF_TD is Robertson'"'"'s term frequency for term T in supercategory S_C,

=N_TC/(N_TC K₁ K₂*(L_C/L₀)),

where;

N_TC is the number of times the term T occurs in supercategory S_C,

L_C is the length of supercategory S_C,

L₀ is the average length of a supercategory, and

K₁ and K₂ are constants

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

where;

N is the number of supercategories in the collection

N_T is the number of supercategories containing the term T, and

K₃ and K₄ are constants.

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

9. The method of claim 2, wherein:

(a) categories are assigned to supercategories by a plurality of methods,

(b) supercategories are considered to comprise multiple segments,

(c) segments of supercategories comprise terms and term identifiers associated with categories assigned to the supercategory by a single method,

(d) segments of supercategories are assigned weights W_SC,

(e) terms in a segment are assigned weights W_STC, and

(f) in applying the query Q′

_i to the collection of supercategories a generalized term frequency score is used, such that the score S_C for a supercategory with respect to the query Q′

_i is calculated as follows;

$S_C=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br><br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br><br><br>{\mathrm{TF}}_{\mathrm{STC}}*{\mathrm{IDF}}_{\mathrm{ST}}$

where;

S_C is the total score for the supercategory S_C,

T₀ is the number of terms which occur in the query Q′

_i,

S₀ is the number of segments in the supercategory S_C,

TF_STC=Robertson'"'"'s generalized term frequency score for Term T in Segment S_i of supercategory S_C

=G_STC/(G_STC K₁ K₂*W_SC*(H_SC/H_SO)

where;

G_STC=the generalized term count for Term T in Segment S_i of supercategory S_C,

=W_SC*W_STC*N_STC,

where;

W_SC is the weight assigned to segment S_i of the supercategories,

W_STC is the weight assigned to term T in segment S_i of supercategory S_C, and

N_STC is the number of times the term T occurs in segment S_i of supercategory S_C,

H_SC=the generalized length of segment S_i of supercategory S_C,

$H_{\mathrm{SC}}=\underset{T=1}{\overset{L_{\mathrm{SC}}}{\sum <br><br>}}<br><br><br><br>W_{\mathrm{STC}}*N_{\mathrm{STC}}$

where;

L_SC is the number of different terms in segment S_i of supercategory S_C,

H_SO=the generalized average length of segment S_i of the supercategories,

$H_{\mathrm{SO}}=\underset{C=1}{\overset{C_0}{\sum <br><br>}}<br><br><br><br>\left(W_{\mathrm{SC}}*H_{\mathrm{SC}}\right)/\underset{C=1}{\overset{C_0}{\sum <br><br>}}<br><br><br><br>W_{\mathrm{SC}},$

where;

C₀ is the number of supercategories

and

K₁ and K₂ are constants

and IDF_ST=the generalized inverted document frequency for term T,

IDF_St=log((C₀ K₃)/C_ST)log(C₀ K₄)

where;

C₀ is the number of supercategories

C_ST is the number of supercategories containing the term T in the segment S_i,

and

K₃ and K₄ are constants.

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

11. The method of claim 9, wherein a subset of the categories are assigned to supercategories manually, while the remainder are assigned utilizing an automatic or semi-automatic index term augmentation technique based upon the co-occurrence of terms between the manually-assigned categories and the categories being automatically or semi-automatically assigned.

12. The method of claim 11, further comprising assigning the remainder of the terms not manually assigned to supercategories by

(a) selecting a category C_i from among the categories in the collection not yet assigned to supercategories which has not yet been processed,

(b) selecting a supercategory S_j from among the set of supercategories,

(c) calculating a likelihood function for the category C_i and a category C_k in the collection which has previously been assigned to the supercategory S_j manually, which likelihood function is based upon the likelihood that a term occurring in the category C_i also occurs in the category C_k

(d) repeating step (c) for a plurality of other categories C_k in the collection which have previously been assigned to the supercategory S_j manually,

(e) calculating a total score for the category C_i for the supercategory S_j which total score is based upon the likelihood functions for the category C_i and the categories C_k in the collection which have previously been assigned to the supercategory S_j manually,

(f) repeating steps (b)-(e) for a plurality of other supercategories S_j,

(g) assigning category C_i to the supercategory for which the total score calculated for the category C_i is the highest, and

(h) repeating steps (a)-(g) for a plurality of other categories in the collection which have not yet been assigned to supercategories and which have not yet been processed.

13. The method of claim 12, wherein the likelihood function for the category C_i and a category C_k in the collection which has previously been assigned to the supercategory S_j manually, is the log likelihood ratio L(C_i, C_k) for the category C_i and the category C_k,

$L$

( C i , C k ) = log ⁡

( ∑

m = 1 M 0 ⁢

⁢

∏

m ⁢

( C i , C k ) / ∑

m = 1 M 0 ⁢

⁢

∏

m ⁢

( C i ) ) ,

where

π

_m(C_i, C_k)=1, if item m is assigned to category C_i and to category C_k

=0 otherwise

π

_m(C_i)=1, if item m is assigned to category C_i

=0 otherwise

M₀=the number of items which are assigned to the category C_i.

14. The method of claim 13, wherein the total score T (C₁, S_j) for the category C_i for the supercategory S_j is

$T$

( C i , S j ) = ∑

k = 1 K 0 ⁢

⁢

L ⁡

( C i , C k ) / K 0 ,

where

K₀=the number of categories in the collection assigned to supercategory S_j manually.

15. The method of claim 14, wherein there are approximately 20,000 categories.

16. The method of claim 15, wherein there are approximately 50 supercategories.

17. The method of claim 16, wherein a portion of the approximately 20,000 categories is manually assigned to supercategories.

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

19. The method of claim 18, wherein the weight W_SC assigned to the segment of a supercategory which comprises terms and term identifiers associated with the categories assigned to the supercategory manually is 1.0, and the weight W_SC assigned to the segment of a supercategory which comprises terms and term identifiers associated with the categories assigned to the supercategory semi-automatically is 0.4.

20. A device for presenting banner advertisements to a user who is seeking information about products and/or services, comprising:

(a) means for defining a collection C₀ of categories of products and/or services,

(b) means for associating, for a plurality of the categories in the collection C₀ of categories, the category with a set of terms which describe the product(s) and/or service(s) associated with the category, and a unique category identifier term,

(c) means for assigning, for a plurality of providers of products and/or services to be utilized, the provider to one or more categories based upon the products and/or services offered by the provider,

(d) means for assigning a plurality of the categories to supercategories,

(e) means for associating, for a plurality of supercategories, one or more banner advertisements with the supercategory,

(f) means for associating, for a plurality of the supercategories, the supercategory with the sets of terms which describe the product(s) or service(s) associated with categories assigned to the supercategory, and the category identifier terms which are unique to categories assigned to the supercategory,

(g) means for selecting, in response to a user query Q′

, comprising terms describing products and/or services of interest to the user, categories, in the collection of categories C₀, which has associated with them a descriptive term for the products and/or services therein which matches a term in the user query,

(h) means for preparing a new query Q′

, comprising the terms in the user query Q, the descriptive terms for the products and/or services associated with the categories selected, and the unique category identifier terms associated with the categories selected,

(i) means for applying the query Q′

to the collection of supercategories,

(j) means for selecting the supercategory with the highest score, and

(k) means for presenting to the user a banner advertisement associated with the supercategory selected.

21. The device of claim 20, wherein the search query Q is applied to select a supercategory from among the collection of supercategories by calculating for each supercategory a score S_C based upon the occurrence in the supercategory of terms in the search query Q′

.

22. The device of claim 21, wherein there are approximately 20,000 categories of products and/or services in the collection of categories.

23. The device of claim 22, wherein there are approximately 50 supercategories.

24. The device of claim 21, wherein every category, in the collection of categories C₀, which has associated with it a descriptive term for the products and/or services therein which matches a term in the user query, is presented to the user, and the user is permitted to select from among said categories a category of interest for which a list of the merchants, stores or other sources of product(s) and/or service(s) associated with the category will be presented.

25. The device of claim 24, further comprising,

(a) means for preparing, in response to the user selecting a category from those presented, a new query Q″

, comprising the descriptive terms for the product(s) and/or service(s) associated with the category selected, and the unique category identifier term associated with the category selected,

(b) means for applying the query Q″

to the collection of supercategories,

(c) means for selecting the supercategory with the highest score, and

(d) means for presenting the user with a banner advertisement associated with the supercategory selected.

26. The device of claim 21, wherein the query Q′

is applied to the collection of supercategories by utilizing Robertson'"'"'s term frequency score, such that the score for a supercategory S_C under the query Q′

is determined by;

$S_C=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br><br><br>{\mathrm{TF}}_{\mathrm{TD}}*{\mathrm{IDF}}_T,$

where;

T₀ is the number of terms which occur in the query Q′

_i,

TF_TD is Robertson'"'"'s term frequency for term T in supercategory S_C,

=N_TC/(N_TC K₁ K₂*(L_C/L₀)),

where;

N_TC is the number of times the term T occurs in supercategory S_C,

L_C is the length of supercategory S_C,

L₀ is the average length of a supercategory, and

K₁ and K₂ are constants

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

where;

N is the number of supercategories in the collection

N_T is the number of supercategories containing the term T, and

K₃ and K₄ are constants.

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

28. The device of claim 21, further comprising:

(a) means for assigning categories to supercategories by a plurality of methods,

(b) means for considering supercategories to comprise multiple segments,

(c) means for causing segments of supercategories to comprise terms and term identifiers associated with categories assigned to the supercategory by a single method

(d) means for assigning segments of supercategories weights W_SC,

(e) means for assigning terms in a segment weights W_STC, and

(f) means for using a generalized term frequency score in applying the query Q′

_i to the collection of supercategories, such that the score S_C for a supercategory with respect to the query Q′

_i is calculated as follows;

$S_C=\underset{T=1}{\overset{T_0}{\sum <br><br>}}<br><br><br><br>\underset{S_i=1}{\overset{S_0}{\sum <br><br>}}<br><br><br><br>{\mathrm{TF}}_{\mathrm{STC}}*{\mathrm{IDF}}_{\mathrm{ST}}$

where;

S_C is the total score for the supercategory S_C,

T₀ is the number of terms which occur in the query Q′

_i,

S₀ is the number of segments in the supercategory S_C,

TF_STC=Robertson'"'"'s generalized term frequency score for Term T in Segment S_i of supercategory S_C

=G_STC/(G_STC K₁ K₂*W_SC*(H_SC/H_SO),

where;

G_STC=the generalized term count for Term T in Segment S_i of supercategory S_C,

=W_SC*W_STC*N_STC,

where;

W_SC is the weight assigned to segment S_i of the supercategories,

W_STC is the weight assigned to term T in segment S_i of supercategory S_C, and

N_STC is the number of times the term T occurs in segment S_i of supercategory S_C,

H_SC=the generalized length of segment S_i of supercategory S_C,

$H_{\mathrm{SC}}=\underset{T=1}{\overset{L_{\mathrm{SC}}}{\sum <br><br>}}<br><br><br><br>W_{\mathrm{STC}}*N_{\mathrm{STC}}$

where;

L_SC is the number of different terms in segment S_i of supercategory S_C,

H_SO=the generalized average length of segment S_i of the supercategories,

$H_{\mathrm{SO}}=\underset{C=1}{\overset{C_0}{\sum <br><br>}}<br><br><br><br>\left(W_{\mathrm{SC}}*H_{\mathrm{SC}}\right)/\underset{C=1}{\overset{C_0}{\sum <br><br>}}<br><br><br><br>W_{\mathrm{SC}},$

where;

C₀ is the number of supercategories

and

K₁ and K₂ are constants

and IDF_ST=the generalized inverted document frequency for term T,

IDF_ST=log((C₀ K₃)/C_ST)/log(C₀ K₄)

where;

C₀ is the number of supercategories

C_ST is the number of supercategories containing the term T in the segment S_i,

and

K₃ and K₄ are constants.

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

30. The device of claim 28, further comprising means for assigning certain of the categories to supercategories manually, and means for assigning the remainder utilizing an automatic or semi-automatic index term augmentation technique based upon the co-occurrence of terms between the manually-assigned categories and the categories being automatically or semi-automatically assigned.

31. The device of claim 30, wherein the means for assigning the remainder of the terms not manually assigned to supercategories further comprises

(a) means for selecting a category C_i from among the categories in the collection not yet assigned to supercategories which has not yet been processed,

(b) means for selecting a supercategory S_j from among the set of supercategories,

(c) means for calculating a likelihood function for the category C_i and a category C_k in the collection which has previously been assigned to the supercategory S_j manually, which likelihood function is based upon the likelihood that a term occurring in the category C_i also occurs in the category C_k

(d) means for repeating step (c) for a plurality of other categories C_k in the collection which have previously been assigned to the supercategory S_j manually,

(e) means for calculating a total score for the category C_i for the supercategory S_j, which total score is based upon the likelihood functions for the category C_i and the categories C_k in the collection which have previously been assigned to the supercategory S_j manually,

(f) means for repeating steps (b)-(e) for a plurality of other supercategories S_j,

(g) means for assigning category C_i to the supercategory for which the total score calculated for the category C_i is the highest, and

(h) means for repeating steps (a)-(g) for a plurality of other categories in the collection which have not yet been assigned to supercategories and which have not yet been processed.

32. The device of claim 31, wherein the likelihood function for the category C_i and a category C_k in the collection which has previously been assigned to the supercategory S_j manually, is the log likelihood ratio L(C_j, C_k) for the category C_i and the category C_k,

$L$

( C i , C k ) = log ⁡

( ∑

m = 1 M 0 ⁢

⁢

∏

m ⁢

( C i , C k ) / ∑

m = 1 M 0 ⁢

⁢

∏

m ⁢

( C i ) ) ,

where

π

_m(C_i, C_k)=1, if item m is assigned to category C_i and to category C_k

=0 otherwise

π

_m(C_i)=1, if item m is assigned to category C_i

=0 otherwise

M₀ the number of items which are assigned to the category C_i.

33. The device of claim 32, wherein the total score T (C_i, S_j) for the category C_i for the supercategory S_j is

$T$

( C i , S j ) = ∑

k = 1 K 0 ⁢

⁢

L ⁡

( C i , C k ) / K 0 ,

where

K₀=the number of categories in the collection assigned to supercategory S_j manually.

34. The device of claim 33, wherein there are approximately 20,000 categories.

35. The device of claim 34, wherein there are approximately 50 supercategories.

36. The device of claim 35, wherein some of the 20,000 categories are manually assigned to supercategories.

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

38. The device of claim 37, wherein the weight W_SC assigned to the segment of a supercategory which comprises terms and term identifiers associated with the categories assigned to the supercategory manually is 1.0, and the weight W_SC assigned to the segment of a supercategory which comprises terms and term identifiers associated with the categories assigned to the supercategory semi-automatically is 0.4.