Automatic generation of ontologies using word affinities

• US 8,171,029 B2
• Filed: 10/01/2008
• Issued: 05/01/2012
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Marvit, David L., Jain, Jawahar, Stergiou, Stergios, Labrou, Yannis
• Primary Examiner(s): Le, Hung
• Application Number:
  US12/242,950
• Publication Number:
  US 20090094262A1
• Time in Patent Office: 1,308 Days
• Field of Search: None
• US Class Current: 707/740
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

In one embodiment, generating an ontology includes accessing an inverted index that comprises inverted index lists for words of a language. An inverted index list corresponding to a word indicates pages that include the word. A word pair comprises a first word and a second word. A first inverted index list and a second inverted index list are searched, where the first inverted index list corresponds to the first word and the second inverted index list corresponds to the second word. An affinity between the first word and the second word is calculated according to the first inverted index list and the second inverted index list. The affinity describes a quantitative relationship between the first word and the second word. The affinity is recorded in an affinity matrix, and the affinity matrix is reported.

Claims

1. A method comprising:

accessing an inverted index stored in a tangible storage medium, the inverted index comprising a plurality of inverted index lists for a plurality of words of a language, an inverted index list corresponding to a word indicating one or more pages that include the word, each of the plurality of inverted index lists stored by representing the inverted index list by a Boolean function and generating a binary decision diagram corresponding to the Boolean function;

for each word pair of the plurality of words, the word pair comprising a first word and a second word;

searching a first inverted index list and a second inverted index list, the first inverted index list corresponding to the first word, the second inverted index list corresponding to the second word;

calculating an affinity between the first word and the second word according to the first inverted index list and the second inverted index list, the affinity describing a quantitative relationship between the first word and the second word; and

recording the affinity in an affinity matrix; and

reporting the affinity matrix.

2. The method of claim 1, the calculating the affinity between the first word and the second word further comprising calculating a basic affinity between the first word and the second word by:

establishing a number of conjunction pages indicating the number of pages comprising the first word and the second word;

establishing a number of disjunction pages indicating the number of pages comprising either the first word or the second word; and

dividing the number of conjunction pages by the number of disjunction pages.

3. The method of claim 1, the calculating the affinity between the first word and the second word further comprising calculating a directional affinity of the first word given the second word by:

establishing a number of conjunction pages indicating the number of pages comprising the first word and the second word;

establishing a number of first word pages indicating the number of pages comprising the first word; and

dividing the number of conjunction pages by the number of first word pages.

4. The method of claim 1, the calculating the affinity between the first word and the second word further comprising calculating an average affinity of the first word by:

for each word pair of the plurality of words, calculating a directional affinity between the words of the each word pair to yield a plurality of directional affinities; and

calculating an average of the directional affinities.

5. The method of claim 1, the calculating the affinity between the first word and the second word further comprising calculating a differential affinity of the first word with respect to the second word by:

calculating a directional affinity of the first word to the second word;

calculating an average affinity of the second word; and

subtracting the average affinity of the second word from the directional affinity of the first word to the second word.

6. The method of claim 1, further comprising storing an inverted index list of the plurality of inverted index lists by:

representing the inverted index list by a Boolean function by performing the following for each element of the inverted index list;

expressing the each element as a binary value comprising a plurality of bit values;

representing each bit value with a variable of the Boolean function;

constructing a minterm from the each element; and

constructing the Boolean function by Oring the minterms; and

generating a binary decision diagram corresponding to the Boolean function.

7. The method of claim 1, further comprising storing an inverted index list of the plurality of inverted index lists by:

representing an inverted index list by a Boolean function by performing the following for each element of the inverted index list;

expressing the each element as a 2^k base value comprising a plurality of base-2^k digits; and

encoding each base-2^k digit to yield an encoded base-2^k digit comprising a plurality of bit values;

representing each bit value with a variable of the Boolean function; and

generating a binary decision diagram corresponding to the Boolean function.

8. The method of claim 1, further comprising storing an inverted index list of the plurality of inverted index lists by:

representing the inverted index list by a Boolean function; and

generating a binary decision diagram corresponding to the Boolean function by;

establishing a plurality of nodes of the binary decision diagram; and

determining a node structure for each node.

9. The method of claim 1, the searching the first inverted index list and the second inverted index list further comprising:

traversing a first binary decision diagram representing the first inverted index list; and

traversing a second binary decision diagram representing the second inverted index list.

10. The method of claim 1, the searching the first inverted index list and the second inverted index list further comprising searching a first binary decision diagram and a second binary decision diagram, the first binary decision diagram representing the first inverted index list, the second binary decision diagram representing the second inverted index list, by repeating the following until the end of either the first inverted index list or the second inverted index list is reached:

establishing a current element of a current inverted index list comprising either the first inverted index list or the second inverted index list;

retrieving a next greater element from the other inverted index list;

comparing the next greater element and the current element; and

recording a common element if the next greater element matches the current element.

11. One or more non-transitory computer-readable media encoding software that, when executed, is operable to:

access an inverted index stored in a tangible storage medium, the inverted index comprising a plurality of inverted index lists for a plurality of words of a language, an inverted index list corresponding to a word indicating one or more pages that include the word, each of the plurality of inverted index lists stored by representing the inverted index list by a Boolean function and generating a binary decision diagram corresponding to the Boolean function;

for each word pair of the plurality of words, the word pair comprising a first word and a second word;

search a first inverted index list and a second inverted index list, the first inverted index list corresponding to the first word, the second inverted index list corresponding to the second word;

calculate an affinity between the first word and the second word according to the first inverted index list and the second inverted index list, the affinity describing a quantitative relationship between the first word and the second word; and

record the affinity in an affinity matrix; and

report the affinity matrix.

12. The non-transitory computer-readable media of claim 11, the software further operable to calculate the affinity between the first word and the second word by calculating a basic affinity between the first word and the second word by:

establishing a number of conjunction pages indicating the number of pages comprising the first word and the second word;

establishing a number of disjunction pages indicating the number of pages comprising either the first word or the second word; and

dividing the number of conjunction pages by the number of disjunction pages.

13. The non-transitory computer-readable media of claim 11, the software further operable to calculate the affinity between the first word and the second word by calculating a directional affinity of the first word given the second word by:

establishing a number of conjunction pages indicating the number of pages comprising the first word and the second word;

establishing a number of first word pages indicating the number of pages comprising the first word; and

dividing the number of conjunction pages by the number of first word pages.

14. The non-transitory computer-readable media of claim 11, the software further operable to calculate the affinity between the first word and the second word by calculating an average affinity of the first word by:

for each word of the plurality of words, calculating a directional affinity between the words of the each word pair to yield a plurality of directional affinities; and

calculating an average of the directional affinities.

15. The non-transitory computer-readable media of claim 11, the software further operable to calculate the affinity between the first word and the second word by calculating a differential affinity of the first word with respect to the second word by:

calculating a directional affinity of the first word to the second word;

calculating an average affinity of the second word; and

subtracting the average affinity of the second word from the directional affinity of the first word to the second word.

16. The non-transitory computer-readable media of claim 11, the software further operable to store an inverted index list of the plurality of inverted index lists by:

representing the inverted index list by a Boolean function by performing the following for each element of the inverted index list;

expressing the each element as a binary value comprising a plurality of bit values;

representing each bit value with a variable of the Boolean function;

constructing a minterm from the each element; and

constructing the Boolean function by Oring the minterms; and

generating a binary decision diagram corresponding to the Boolean function.

17. The non-transitory computer-readable media of claim 11, the software further operable to store an inverted index list of the plurality of inverted index lists by:

representing an inverted index list by a Boolean function by performing the following for each element of the inverted index list;

expressing the each element as a 2-to-the-power-k base value comprising a plurality of base-2-to-the-power-k digits; and

encoding each base-2-to-the-power-k digit to yield an encoded base-2-to-the-power-k digit comprising a plurality of bit values;

representing each bit value with a variable of the Boolean function; and

generating a binary decision diagram corresponding to the Boolean function.

18. The non-transitory computer-readable media of claim 11, the software further operable to store an inverted index list of the plurality of inverted index lists by:

representing the inverted index list by a Boolean function; and

generating a binary decision diagram corresponding to the Boolean function by;

establishing a plurality of nodes of the binary decision diagram; and

determining a node structure for each node.

19. The non-transitory computer-readable media of claim 11, the software further operable to search the first inverted index list and the second inverted index list by:

traversing a first binary decision diagram representing the first inverted index list; and

traversing a second binary decision diagram representing the second inverted index list.

20. The non-transitory computer-readable media of claim 11, the software further operable to search the first inverted index list and the second inverted index list further comprising searching a first binary decision diagram and a second binary decision diagram, the first binary decision diagram representing the first inverted index list, the second binary decision diagram representing the second inverted index list, by repeating the following until the end of either the first inverted index list or the second inverted index list is reached:

establish a current element of a current inverted index list comprising either the first inverted index list or the second inverted index list;

retrieve a next greater element from the other inverted index list;

compare the next greater element and the current element; and

record a common element if the next greater element matches the current element.

21. A system comprising:

means for accessing an inverted index stored in a tangible storage medium, the inverted index comprising a plurality of inverted index lists for a plurality of words of a language, an inverted index list corresponding to a word indicating one or more pages that include the word, each of the plurality of inverted index lists stored by representing the inverted index list by a Boolean function and generating a binary decision diagram corresponding to the Boolean function;

means for, for each word pair of the plurality of words, the word pair comprising a first word and a second word;

searching a first inverted index list and a second inverted index list, the first inverted index list corresponding to the first word, the second inverted index list corresponding to the second word;

calculating an affinity between the first word and the second word according to the first inverted index list and the second inverted index list, the affinity describing a quantitative relationship between the first word and the second word; and

recording the affinity in an affinity matrix; and

means for reporting the affinity matrix.