Semi-automatic index term augmentation in document retrieval

• US 7,024,416 B1
• Filed: 10/04/2002
• Issued: 04/04/2006
• 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:
  US10/265,466
• Time in Patent Office: 1,278 Days
• Field of Search: 707/3, 707/4, 707/100, 707/102, 707/5, 707/1, 707/6, 707/10, 707/101, 707/103.Y, 707/104.1, 709/201, 715/810
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Disclosed are methods and systems for indexing or retrieving materials accessible through computer networks.

Claims

1. A processor-implemented method for assigning categories of items to supercategories, comprising:

(a) assigning a subset of the categories in the collection to supercategories manually,

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

(c) calculating a likelihood function L_ik for the category C_i and a category C_k in the collection which has previously been assigned to a 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 a supercategory S_j manually,

(e) assigning the category C_i to a supercategory S_j based on the likelihood functions L_ik that a term occurring in the category C_i also occurs in the category C_k which is assigned to supercategory S_j, and

(f) repeating steps (b)–

(e) for a plurality of other categories in the collection which have not yet been assigned to supercategories and which have not yet been processed.

2. The method of claim 1, wherein the categories correspond to varieties of products or services.

3. The method of claim 2, wherein the items in the categories correspond to merchants, stores or other sources of the category'"'"'s product or service, and the merchants, stores or other sources may be associated with more than one category of products or services.

4. The method of claim 2, wherein the supercategories correspond to groups of categories as to which it is desired to present the same banner advertisement to a user accessing the categories.

5. A processor-implemented method for assigning categories of items to supercategories, comprising:

(a) assigning a subset of the categories in the collection to supercategories manually,

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

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

(d) 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,

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

(f) 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,

(g) repeating steps (c)–

(f) for a plurality of other supercategories S_j,

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

(i) repeating steps (b)–

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

6. The method of claim 5, 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$

(Ci,Ck)=log⁡

(∑

m=1M0⁢

Π

m⁡

(Ci,Ck)/∑

m=1M0⁢

Π

m⁡

(Ci)),

where $\begin{array}{c}\underset{m}{\prod <br><br>}<br><br>\left(C_i,C_k\right)=<br><br>1,\mathrm{if}<br><br><br><br>\mathrm{item}<br><br><br><br>m<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{assigned}<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{category}<br><br><br><br>C_i<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{to}<br><br>\\ <br><br>\mathrm{category}<br><br><br><br>C_k\\ =<br><br>0<br><br><br><br>\mathrm{otherwise}\\ \underset{m}{\prod <br><br>}<br><br>\left(C_i\right)=<br><br>1,\mathrm{if}<br><br><br><br>\mathrm{item}<br><br><br><br>m<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{assigned}<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{category}<br><br><br><br>C_i\\ =<br><br>0<br><br><br><br>\mathrm{otherwise}\end{array}$

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

7. The method of claim 6, wherein the total score T (C_i, S_j) for the category C_i for the supercategory S_j is $T$

(Ci,Sj)=∑

k=1K0⁢

L⁡

(Ci,Ck)/K0,

where

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

8. The method of claim 7, wherein the categories correspond to varieties of products or services.

9. The method of claim 8, wherein the items in the categories correspond to merchants, stores or other sources of the category'"'"'s product or service, and the merchants, stores or other sources may be associated with more than one category of products or services.

10. The method of claim 9, wherein the supercategories correspond to groups of categories as to which it is desired to present the same banner advertisement to a user accessing the categories.

11. The method of claim 10, wherein there are 20,000 categories of products or services.

12. The method of claim 11, wherein there are 2,000 categories of products or services assigned to supercategories manually.

13. The method of claim 12, wherein there are 50 supercategories.

14. A processor-implemented device for assigning categories of items to supercategories, comprising:

(a) means for assigning a subset of the categories in the collection to supercategories manually,

(b) 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,

(c) means for calculating a likelihood function L_ik for the category C_i and a category C_k in the collection which has previously been assigned to a 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 a supercategory S_j manually,

(e) means for assigning the category C_i to a supercategory S_j based on the likelihood functions L_ik that a term occurring in the category C_i also occurs in the category C_k which is assigned to supercategory S_j, and

(f) means for repeating steps (b)–

(e) for a plurality of other categories in the collection which have not yet been assigned to supercategories and which have not yet been processed.

15. The device of claim 14, wherein the categories correspond to varieties of products or services.

16. The device of claim 15, wherein the items in the categories correspond to merchants, stores or other sources of the category'"'"'s product or service, and the merchants, stores or other sources may be associated with more than one category of products or services.

17. The device of claim 15, wherein the supercategories correspond to groups of categories as to which it is desired to present the same banner advertisement to a user accessing the categories.

18. A processor-implemented device for assigning categories of items to supercategories, comprising:

(a) means for assigning a subset of the categories in the collection to supercategories manually,

(b) 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,

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

(d) 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,

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

(f) 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,

(g) means for repeating steps (c)–

(f) for a plurality of other supercategories S_j,

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

(i) means for repeating steps (b)–

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

19. The device of claim 18, 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$

(Ci,Ck)=log⁡

(∑

m=1M0⁢

Π

m⁡

(Ci,Ck)/∑

m=1M0⁢

Π

m⁡

(Ci)),

where $\underset{m}{\prod <br><br>}<br><br>\left(C_i<br><br>C_k\right)=1,<br><br>\mathrm{if}<br><br><br><br>\mathrm{item}<br><br><br><br>m<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{assigned}<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{category}<br><br><br><br>C_i<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{category}<br><br><br><br>C_k$$\begin{array}{cc}\underset{m}{\prod <br><br>}<br><br>\left(C_i\right)=0& \mathrm{otherwise}\\ =1,& \mathrm{if}<br><br><br><br>\mathrm{then}<br><br><br><br>m<br><br><br><br>\mathrm{is}<br><br><br><br>\mathrm{assigned}<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{category}<br><br><br><br>C_i\\ =0& \mathrm{otherwise}\end{array}$

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

20. The device of claim 19, wherein the total score T (C_i, S_j) for the category C_i for the supercategory S_j is $T$

(Ci,Sj)=∑

k=1K0⁢

L⁡

(Ci,Ck)/K0,

where

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

21. The method of claim 20, wherein the categories correspond to varieties of products or services.

22. The device of claim 21, wherein the items in the categories correspond to merchants, stores or other sources of the category'"'"'s product or service, and the merchants, stores or other sources may be associated with more than one category of products or services.

23. The device of claim 22, wherein the supercategories correspond to groups of categories as to which it is desired to present the same banner advertisement to a user accessing the categories.

24. The device of claim 23, wherein there are 20,000 categories of products or services.

25. The device of claim 24, wherein there are 2,000 categories of products or services assigned to supercategories manually.

26. The device of claim 25, wherein there are 50 supercategories.