Efficient computation of ontology affinity matrices

• US 8,554,696 B2
• Filed: 02/10/2010
• Issued: 10/08/2013
• Est. Priority Date: 02/13/2009
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Labrou, Yannis, Jain, Jawahar
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US12/658,531
• Publication Number:
  US 20100211534A1
• Time in Patent Office: 1,336 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri

Abstract

In one embodiment, generating an ontology includes accessing an inverted index comprising a plurality of inverted index lists. An inverted index list may correspond to a term of a language. Each inverted index list may comprise a term identifier of the term and one or more document identifiers indicating one or more documents of a document set in which the term appears. The embodiment also includes generating a term identifier index according to the inverted index. The term identifier index comprises a plurality of sections and each section corresponds to a document. Each section may comprise one or more term identifiers of one or more terms that appear in the document.

Claims

1. A computer-implemented method comprising:

accessing an inverted index comprising a plurality of inverted index lists in a memory of a computer, each inverted index list corresponding to a term, each inverted index list comprising a term identifier of the term and one or more document identifiers indicating one or more documents of a document set in which the term appears;

using a processor of the computer, generating a plurality of ordered pairs from the inverted index, each ordered pair comprising a term identifier and a document identifier of an inverted index list, the ordered pairs being organized primarily based on the document identifiers of the ordered pairs; and

using the processor of the computer, generating a term identifier index according to the inverted index, the term identifier index comprising a plurality of sections, each section corresponding to a document, each section comprising one or more term identifiers of one or more terms that appear in the document, the generating the term identifier index according to the inverted index comprising organizing the term identifiers of the ordered pairs in the sections of the term identifier index, wherein organizing the term identifiers of the ordered pairs comprises;

removing a selected ordered pair from a data structure;

generating a next ordered pair from the inverted index, the next ordered pair comprising a term identifier equivalent to a term identifier of the selected ordered pair; and

placing the next ordered pair into the data structure.

2. The method of claim 1,

the ordered pairs being organized secondarily based on the term identifiers of the ordered pairs.

3. The method of claim 1, the generating the term identifier index according to the inverted index further comprising:

selecting an ordered pair in order from a data structure; and

placing the term identifier of the selected ordered pair into a section of the term identifier index corresponding to a document to organize the term identifiers of the inverted index according to the documents.

4. The method of claim 1, the generating the term identifier index according to the inverted index further comprising:

determining that a selected ordered pair comprises a document identifier that is not equivalent to a document identifier of a previously selected ordered pair comprising a term identifier placed in a first section; and

placing a term identifier of the selected ordered pair in a second section distinct from the first section.

5. The method of claim 1, further comprising:

initializing an ontology affinity matrix comprising a plurality of entries, each entry comprising a count value, each entry corresponding to an affinity of a term pair comprising a first term and a second term; and

incrementing the count value of an entry corresponding to the affinity of a selected term pair for each section of the term identifier index that comprises the term identifiers of the selected term pair.

6. The method of claim 1, further comprising:

generating an ontology affinity matrix comprising a plurality of entries, each entry corresponding to an affinity of a term pair comprising a first term and a second term, each entry comprising a count value indicating a number of times the term pair appears together in a document of the document set; and

dividing each count value of the ontology affinity matrix by one of a group consisting of a number of documents the first term appears in, a number of documents the second term appears in, and the number of documents the first term appears in plus the number of documents the second term appears in.

7. The method of claim 1, further comprising:

generating an ontology affinity matrix comprising a plurality of entries, each entry corresponding to a directional affinity of a term pair comprising a first term and a second term, the directional affinity comprising the probability that the second term appears in a document of the document set given that the first term appears in the document.

8. An apparatus comprising:

a memory operable to;

store an inverted index comprising a plurality of inverted index lists, each inverted index list corresponding to a term, each inverted index list comprising a term identifier of the term and one or more document identifiers indicating one or more documents of a document set in which the term appears; and

a processor operable to execute logic to;

generating a plurality of ordered pairs from the inverted index, each ordered pair comprising a term identifier and a document identifier of an inverted index list, the ordered pairs being organized primarily based on the document identifiers of the ordered pairs; and

generate a term identifier index according to the inverted index, the term identifier index comprising a plurality of sections, each section corresponding to a document, each section comprising one or more term identifiers of one or more terms that appear in the document, the generating the term identifier index according to the inverted index comprising organizing the term identifiers of the ordered pairs in the sections of the term identifier index, wherein organizing the term identifiers of the ordered pairs comprises;

removing a selected ordered pair from a data structure;

generating a next ordered pair from the inverted index, the next ordered pair comprising a term identifier equivalent to a term identifier of the selected ordered pair; and

placing the next ordered pair into the data structure.

9. The apparatus of claim 8,

the ordered pairs being organized secondarily based on the term identifiers of the ordered pairs.

10. The apparatus of claim 8, the generating the term identifier index according to the inverted index further comprising:

selecting an ordered pair in order from a data structure; and

placing the term identifier of the selected ordered pair into a section of the term identifier index corresponding to a document to organize the term identifiers of the inverted index according to the documents.

11. The apparatus of claim 8, the generating the term identifier index according to the inverted index further comprising:

determining that a selected ordered pair comprises a document identifier that is not equivalent to a document identifier of a previously selected ordered pair comprising a term identifier placed in a first section; and

placing a term identifier of the selected ordered pair in a second section distinct from the first section.

12. The apparatus of claim 8, the processor further operable to:

initialize an ontology affinity matrix comprising a plurality of entries, each entry comprising a count value, each entry corresponding to an affinity of a term pair comprising a first term and a second term; and

increment the count value of an entry corresponding to the affinity of a selected term pair for each section of the term identifier index that comprises the term identifiers of the selected term pair.

13. The apparatus of claim 8, the processor further operable to:

generate an ontology affinity matrix comprising a plurality of entries, each entry corresponding to an affinity of a term pair comprising a first term and a second term, each entry comprising a count value indicating a number of times the term pair appears together in a document of the document set; and

divide each count value of the ontology affinity matrix by one of a group consisting of a number of documents the first term appears in, a number of documents the second term appears in, and the number of documents the first term appears in plus the number of documents the second term appears in.

14. The apparatus of claim 8, the processor further operable to:

generate an ontology affinity matrix comprising a plurality of entries, each entry corresponding to a directional affinity of a term pair comprising a first term and a second term, the directional affinity comprising the probability that the second term appears in a document of the document set given that the first term appears in the document.

15. A non-transitory, tangible computer-readable medium having computer-executable code, when executed by a computer operable to:

access an inverted index comprising a plurality of inverted index lists, each inverted index list corresponding to a term, each inverted index list comprising a term identifier of the term and one or more document identifiers indicating one or more documents of a document set in which the term appears;

generating a plurality of ordered pairs from the inverted index, each ordered pair comprising a term identifier and a document identifier of an inverted index list, the ordered pairs being organized primarily based on the document identifiers of the ordered pairs; and

generate a term identifier index according to the inverted index, the term identifier index comprising a plurality of sections, each section corresponding to a document, each section comprising one or more term identifiers of one or more terms that appear in the document, the generating the term identifier index according to the inverted index comprising organizing the term identifiers of the ordered pairs in the sections of the term identifier index, wherein organizing the term identifiers of the ordered pairs comprises;

removing a selected ordered pair from a data structure;

generating a next ordered pair from the inverted index, the next ordered pair comprising a term identifier equivalent to a term identifier of the selected ordered pair; and

placing the next ordered pair into the data structure.

16. The medium of claim 15,

the ordered pairs being organized secondarily based on the term identifiers of the ordered pairs.

17. The medium of claim 15, the generating the term identifier index according to the inverted index further comprising:

selecting an ordered pair in order from a data structure; and

placing the term identifier of the selected ordered pair into a section of the term identifier index corresponding to a document to organize the term identifiers of the inverted index according to the documents.

18. The medium of claim 15, the generating the term identifier index according to the inverted index further comprising:

determining that a selected ordered pair comprises a document identifier that is not equivalent to a document identifier of a previously selected ordered pair comprising a term identifier placed in a first section; and

placing a term identifier of the selected ordered pair in a second section distinct from the first section.

19. The medium of claim 15, further operable to:

initialize an ontology affinity matrix comprising a plurality of entries, each entry comprising a count value, each entry corresponding to an affinity of a term pair comprising a first term and a second term; and

increment the count value of an entry corresponding to the affinity of a selected term pair for each section of the term identifier index that comprises the term identifiers of the selected term pair.

20. The medium of claim 15, further operable to:

generate an ontology affinity matrix comprising a plurality of entries, each entry corresponding to an affinity of a term pair comprising a first term and a second term, each entry comprising a count value indicating a number of times the term pair appears together in a document of the document set; and

divide each count value of the ontology affinity matrix by one of a group consisting of a number of documents the first term appears in, a number of documents the second term appears in, and the number of documents the first term appears in plus the number of documents the second term appears in.

21. The medium of claim 15, further operable to:

generate an ontology affinity matrix comprising a plurality of entries, each entry corresponding to a directional affinity of a term pair comprising a first term and a second term, the directional affinity comprising the probability that the second term appears in a document of the document set given that the first term appears in the document.