Topic identification and use thereof in information retrieval systems

• US 7,340,466 B2
• Filed: 02/26/2002
• Issued: 03/04/2008
• Est. Priority Date: 02/26/2002
• Status: Active Grant

• Current Assignee: DataCloud Technologies, LLC (IP Investments Group LLC)
• Original Assignee: Kang Jo Mgmt LLC (Intellectual Ventures LLC)
• Inventors: Odom, Paul S., Kotlar, Dennis, Akileswar, Subramanian, Childers, Robie
• Primary Examiner(s): Breene; John
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US10/086,026
• Publication Number:
  US 20030167252A1
• Time in Patent Office: 2,198 Days
• Field of Search: 707 1- 10, 707/102, 707/100, 715512-514, 715/500, 715/531, 715532-533, 345/700, 345/764, 706/12, 706/45, 704 1- 10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A technique to determine topics associated with, or classifications for, a data corpus uses an initial domain-specific word list to identify word combinations (one or more words) that appear in the data corpus significantly more often than expected. Word combinations so identified are selected as topics and associated with a user-specified level of granularity. For example, topics may be associated with each table entry, each image, each sentence, each paragraph, or an entire file. Topics may be used to guide information retrieval and/or the display of topic classifications during user query operations.

Claims

1. A method to identify topics in a data corpus having a plurality of segments, comprising:

determining a segment-level actual usage value for one or more word combinations, wherein a word combination includes two or more substantially contiguous words, wherein two words are substantially contiguous if they are separated by zero words or words selected from a predetermined list of words;

computing a segment-level expected usage value for each of the one or more word combinations in accordance with S(w_i)xS(w_j) x . . . x S(w_m)/N<sup>m−

1</sup> where “

m”

represents the number of words in the word combination, “

N”

represents the number of segments in the data corpus, and S(w) represents the number of unique segments in the data corpus that word w_i of the word combination is in;

designating a word combination as a topic if the segment level actual usage value of the word combination is greater than the segment-level expected usage value of the word combination; and

storing the topic on a computer readable storage medium.

2. The method of claim 1, wherein each of the plurality of segments comprises a portion of a document.

3. The method of claim 2, wherein the portion of a document comprises a paragraph.

4. The method of claim 2, wherein the portion of a document comprises a heading.

5. The method of claim 2, wherein the portion of a document comprises the entire document.

6. The method of claim 1, wherein the predetermined list of words comprises STOP words.

7. The method of claim 1, wherein at least one word in each of the one or more word combinations is selected from a second predetermined list of words.

8. The method of claim 7, wherein the second predetermined list of words comprise a list of domain specific words.

9. The method of claim 1, wherein the act of determining a segment-level actual usage value for a word combination comprises determining the number of segments in the data corpus the word combination is in.

10. The method of claim 1, wherein the act of designating a word combination as a topic, comprises designating a word combination as a topic if the segment-level actual usage value of the word combination is greater than approximately twice the segment-level expected usage value of the word combination.

19. A method to display a list of topics associated with data items stored in a database, comprising:

identifying a result set based on an initial user query, the result set identifying a plurality of stored data items;

identifying those topics associated with the stored data items identified in the result set, wherein said topics are identified by a method as in claim 1;

selecting for display a topic associated with the most identified stored data items;

selecting for display another topic, said another topic associated with the most identified stored data items not associated with a previously identified display topic, wherein this step is repeated until all identified stored items in the result set have been accounted for; and

displaying the selected display topics.

20. The method of claim 19, wherein the act of identifying a result set comprises:

identifying an initial result set, the initial result set identifying a first plurality of stored data items; and

selectively identifying a subset of the initial result set as the result set.

21. The method of claim 20, wherein the act of selectively identifying comprises randomly selecting a specified portion of the initial result set.

22. The method of claim 21, wherein the act of randomly selecting comprises randomly selecting approximately one percent of the initial result set.

23. The method of claim 19, wherein the act of identifying those topics associated with the stored data items identified in the result set, comprises generating a list of unique topics associated with the identified stored data items.

24. The method of claim 23, further comprising, removing from the generated list those topics that are associated with more than a specified fraction of the identified stored data items.

25. The method of claim 24, wherein the act of removing comprises removing from the generated list those topics that are associated with more than approximately eighty-percent (80%) of the identified stored data items.

26. The method of claim 19, further comprising, displaying a selected number of stored data item identifiers.

27. The method of claim 26, wherein the act of displaying a selected number of stored data item identifiers, comprises displaying a hyperlink.

28. The method of claim 19, wherein the act of selecting for display another topic, comprises determining when the number of data items not associated with a previously identified display topic is less than a specified value and, when this is true:

generating a list of unique individual words from the topics not yet selected for display,

selecting for display a unique word from the list of unique individual words associated with the most identified stored data items; and

selecting for display another unique word from the list of unique individual words, said another unique word associated with the most identified stored data items not associated with a previously identified display topic and unique word, wherein this step is repeated until all identified stored items in the result set have been accounted for.

29. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to display a list of topics associated with data items stored in a database, the instructions causing the programmable control device to:

identify a result set based on an initial user query, the result set identifying a plurality of stored data items;

identify those topics associated with the stored data items identified in the result set, wherein said topics are identified by a method as in claim 1;

select for display a topic associated with the most identified stored data items;

select for display another topic, said another topic associated with the most identified stored data items not associated with a previously identified display topic, wherein this step is repeated until all identified stored items in the result set have been accounted for; and

display the selected display topics.

30. The program storage device of claim 29, wherein the instructions to identify a result set comprise instructions to:

identify an initial result set, the initial result set identifying a first plurality of stored data items; and

selectively identify a subset of the initial result set as the result set.

31. The program storage device of claim 30, wherein the instructions to selectively identify comprise instructions to randomly select a specified portion of the initial result set.

32. The program storage device of claim 31, wherein the instructions to randomly select comprise instructions to randomly select approximately one-percent of the initial result set.

33. The program storage device of claim 29, wherein the instructions to identify those topics associated with the stored data items identified in the result set, comprise instructions to generate a list of unique topics associated with the identified stored data items.

34. The program storage device of claim 33, further comprising instructions to remove from the generated list those topics that are associated with more than a specified fraction of the identified stored data items.

35. The program storage device of claim 34, wherein the instructions to remove comprise instructions to remove from the generated list those topics that are associated with more than approximately eighty-percent (80%) of the identified stored data items.

36. The program storage device of claim 29, further comprising instructions to display a selected number of stored data item identifiers.

37. The program storage device of claim 36, wherein the instructions to display a selected number of stored data item identifiers, comprise instructions to display a hyperlink.

38. The program storage device of claim 29, wherein the instructions to select for display another topic, comprise instructions to determine when the number of data items not associated with a previously identified display topic is less than a specified value and, when this is true:

generate a list of unique individual words from the topics not yet selected for display,

select for display a unique word from the list of unique individual words associated with the most identified stored data items; and

select for display another unique word from the list of unique individual words, said another unique word associated with the most identified stored data items not associated with a previously identified display topic and unique word, wherein these instructions are repeated until all identified stored items in the result set have been accounted for.

11. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to identify topics in a data corpus having a plurality of segments, the instructions causing the programmable control device to:

determine a segment-level actual usage value for one or more word combinations, wherein a word combination includes two or more substantially contiguous words, wherein two words are substantially contiguous if they are separated by zero words or words selected from a predetermined list of words;

compute a segment-level expected usage value for each of the one or more word combinations in accordance with S(w_i)xS(w_j) x . . . x S(w_m)/N<sup>m−

1</sup> where “

m”

represents the number of words in the word combination,“

N”

represents the number of segments in the data corpus, and S(w) represents the number of unique segments in the data corpus that word w_i of the word combination is in; and

designate a word combination as a topic if the segment level actual usage value of the word combination is greater than the segment-level expected usage value of the word combination.

12. The program storage device of claim 11, wherein the instructions for identifying topics in segments comprise instructions to identify topics in a portion of a document.

13. The program storage device of claim 12, wherein the instructions to identify topics in a portion of a document comprise instructions to identify topics in a paragraph.

14. The program storage device of claim 12, wherein the instructions to identify topics in a portion of a document comprise instructions to identify topics in an entire document.

15. The program storage device of claim 11, wherein the instructions to designate a word combination as a topic comprise instructions to designate a word combination as a topic only if at least one of the designated words is selected from a second predetermined list of words.

16. The program storage device of claim 15, wherein the instructions to designate words from the second predetermined list of words comprise instructions to select words from a domain specific word list.

17. The program storage device of claim 11, wherein the instructions to determine a segment-level actual usage value for a word combination comprise instructions to determine the number of segments in the data corpus the word combination is in.

18. The program storage device of claim 11, wherein the instructions to designate a word combination as a topic, comprise instructions to designate a word combination as a topic if the segment-level actual usage value of the word combination is greater than approximately twice the segment-level expected usage value of the word combination.