Mention-Synchronous Entity Tracking: System and Method for Chaining Mentions

• US 20080243888A1
• Filed: 05/05/2008
• Published: 10/02/2008
• Est. Priority Date: 04/27/2004
• Status: Active Grant

• Current Assignee: Abraham Ittycheriah, Hongyan Jing, Nandakishore Kambhatla, Salim E. Roukos, Xiaoqiang Luo
• Original Assignee: Abraham Ittycheriah, Hongyan Jing, Nandakishore Kambhatla, Salim E. Roukos, Xiaoqiang Luo
• Inventors: Kambhatla, Nandakishore, Roukos, Salim E., Jing, Hongyan, Ittycheriah, Abraham, Luo, Xiaoqiang
• Granted Patent: US 8,620,961 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A Bell Tree data structure is provided to model the process of chaining the mentions, from one or more documents, into entities, tracking the entire process; where the data structure is used in an entity tracking process that produces multiple results ranked by a product of probability scores.

Claims

1. A computer readable medium embodying instructions executable by a processor to perform a method for entity tracking, comprising:

inputting a document comprising a plurality of entities;

creating a data structure based on the document comprising a tree structure indicative of chaining a plurality of mentions to at least one entity found in the document; and

searching the tree structure for a plurality of results in response to a query.

2. The computer readable medium as defined in claim 1, wherein:

the tree structure is a Bell Tree structure, wherein a Bell Tree structure comprises;

a plurality of layers, each layer being associated with a mention to be chained into a plurality of entities;

each layer of said plurality of layers having a set of nodes; and

each node of the set of nodes having at least one partial entity and representing a unique result.

3. The computer readable medium as in claim 2 wherein each node of the set of nodes has an associated score.

4. The computer readable medium as defined in claim 2 wherein:

the plurality of layers has a root layer and a remainder of layers;

the mention associated with the root layer is a first mention;

the set of nodes of the root layer is a single node; and

said single node, representing a first result, includes a partial entity resultant from said first mention.

5. The computer readable medium as defined in claim 4 wherein:

each other layer of the remainder of layers has an immediately preceding layer with a preceding set of nodes;

each other layer has a another set of nodes with a number of nodes created by linking the associated mention to each partial entity in the preceding set of nodes; and

the remainder of nodes of said other set of nodes is created by starting a new partial entity with the associated mention and associating the new partial entity with each result represented in the preceding set of nodes,

whereby all results that are possible when said associated mention is added to the Bell Tree are represented.

6. The computer readable medium as defined in claim 2 wherein:

the plurality of layers has a last leaf layer;

said leaf layer has a set of nodes where each node is a leaf;

said leaf has at least one entity; and

each leaf represents each of all possible results from chaining the plurality of mentions.

7. The computer readable medium as defined in claim 4 wherein each node representing each different possible result has an associated score.

8. The computer readable medium as defined in claim 5 wherein each node representing each different possible result has an associated score.

9. The computer readable medium as defined in claim 6 wherein each leaf representing each different possible result has an associated score.