Method and framework to support indexing and searching taxonomies in large scale full text indexes

• US 8,600,997 B2
• Filed: 09/30/2005
• Issued: 12/03/2013
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eiron, Nadav, Meredith, Daniel N., Meyer, Joerg, Pieper, Jan H., Tomkins, Andrew S.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US11/241,687
• Publication Number:
  US 20070078880A1
• Time in Patent Office: 2,986 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/367 Ontology

Abstract

A system and method of indexing a plurality of entities located in a taxonomy, the entities comprising sets of terms, comprises receiving terms in an index structure; building a posting list for an entity with respect to the locations of the set of terms defining the entity and data associated with the respective terms; and indexing a name of a group comprising the entities within this group at the location of the entities with the data of the group comprising the name of the respective entity at each location. The building of the posting list comprises storing the location of the term and data associated with the term in an entry in the posting list for the term. The method comprises indexing aliases of the name of the group comprising the term, and using an inverted list index to associate data with each occurrence of an index term.

Claims

1. A method of indexing entities, located in a taxonomy, said method comprising:

retrieving said entities from documents, each of said entities being indexed by an entity alias and belonging to a group located by said taxonomy and indexed by a group name;

building posting lists for all occurrences of each of said entities, each said posting list of the posting lists for all occurrences of said entities comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field, including a set of terms and data corresponding to said occurrence of said entity;

building a posting list for said group of said all occurrences of each of said entities, said posting list for said group comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field comprising an entity alias corresponding to said occurrence for said entity;

indexing, by said group name, said posting list for said group; and

outputting said posting list for said group in response to a query using said group name.

2. The method of claim 1, further comprising using an inverted list index to associate data with each occurrence of each of said entities.

3. The method of claim 2, further comprising searching said inverted list index to allow statistical aggregation of associated data across a set of document hits, wherein said statistical aggregation indicates which individual entities exist in a document set.

4. A non-transitory program storage device readable by computer, tangibly embodying a program of instructions executable by said computer to perform a method of indexing entities, located in a taxonomy, said method comprising:

retrieving said entities from documents, each of said entities being indexed by an entity alias and belonging to a group located by said taxonomy and indexed by a group name;

building posting lists for all occurrences of each of said entities, each said posting list of the posting lists for all occurrences of each of said entities comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field, including a set of terms and data corresponding to said occurrence of said entity;

building a posting list for said group of said all occurrences of each of said entities, said posting list for said group comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field comprising an entity alias corresponding to said occurrence for said entity;

indexing, by said group name, said posting list for said group; and

outputting said posting list for said group in response to a query using said group name.

5. The non-transitory program storage device of claim 4, wherein said method further comprises using an inverted list index to associate data with each occurrence of each of said entities.

6. The non-transitory program storage device of claim 5, wherein said method further comprises searching said inverted list index to allow statistical aggregation of associated data across a set of document hits, wherein said statistical aggregation indicates which individual entities exist in a document set.

7. A system of indexing entities, located in a taxonomy, said system comprising:

a memory storing an index structure configured to retrieve said entities from documents, each of said entities being indexed by an entity alias and belonging to a group located by said taxonomy and indexed by a group name; and

a processor configured to;

build posting lists for all occurrences of each of said entities, each said posting list of the posting lists for all occurrences of each of said entities comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field, including a set of terms and data corresponding to said occurrence of said entity;

build a posting list for said group of said all occurrences of each of said entities, said posting list for said group comprising a first data field, including a location in said documents for an occurrence of an entity of said entities, and a second data field comprising an entity alias corresponding to said occurrence for said entity;

index, by said group name, said posting list for said group; and

output said posting list for said group in response to a query using said group name.

8. The system of claim 7, further comprising an inverted list index structure configured to associate data with each occurrence of each of said entities.

9. The system of claim 8, further comprising a query mechanism configured to search said inverted list index structure to allow statistical aggregation of associated data across a set of document hits, wherein said statistical aggregation indicates which individual entities exist in a document set.