Mention-synchronous entity tracking: system and method for chaining mentions

• US 8,620,961 B2
• Filed: 05/05/2008
• Issued: 12/31/2013
• Est. Priority Date: 04/27/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ittycheriah, Abraham, Jing, Hongyan, Kambhatla, Nandakishore, Luo, Xiaoqiang, Roukos, Salim E.
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Wong, Huen
• Application Number:
  US12/115,321
• Publication Number:
  US 20080243888A1
• Time in Patent Office: 2,066 Days
• Field of Search: 707/797
• US Class Current: 707/797
• 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 data storage device readable by a machine embodying instructions executable by a processor to perform a method for entity tracking, comprising:

inputting a document comprising references to a plurality of objects;

creating a data structure based on the document comprising a tree structure comprising nodes corresponding to different entity outcomes, wherein each entity is a collection of mentions that refer to a same object, the nodes having respective scores indicative of respective different entity outcomes, wherein each mention is all instance of a reference to one of the plurality of objects within the document and chaining the plurality of mentions includes linking the mentions together as either part of a same entity or different entities; and

searching the tree structure for at least one of the nodes in response to an entity tracking query, wherein searching comprises selecting the at least one of the nodes having a score greater than a threshold as a response to the entity tracking query, wherein a selected node indicates at least one of the plurality of objects,

each node having at least one partial entity and representing a unique result;

wherein the created data structure includes probability information representing the combined probability of;

a first mention of the plurality of mentions is part of a same entity as a second mention of the plurality of mentions;

a third mention of the plurality of mentions is part of the same entity as the first and second mentions, given that the first mention and the second mention are part of the same entity;

the third mention is part of the same entity as the first mention but not the second mention, given that the first mention is not part of the same entity as the second mention; and

the third mention is part of the same entity as the second mention but not the first mention, given that the first mention is not part of the same entity as the second mention.

2. The data storage device as defined in claim 1, wherein:

the tree structure is a Bell Tree structure comprising;

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

each layer of said plurality of layers having at least one node.

3. The data storage device 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 root layer includes a single node; and

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

4. The data storage device as defined in claim 3 wherein:

said nodes of each of the remainder of layers link the associated mention of a respective layer to each partial entity in any preceding node creating 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.

5. The data storage device as defined in claim 2 wherein:

the plurality of layers has a last leaf layer;

said last leaf layer representing all possible results from chaining the plurality of mentions.

6. The data storage device as defined in claim 3 wherein each node representing each different possible result has an associated score.

7. The data storage device as defined in claim 4 wherein each node representing each different possible result has an associated score.

8. The data storage device as defined in claim 5 wherein each leaf representing each different possible result has an associated score.

9. A data storage device readable by a machine embodying instructions executable by a processor to perform a method for entity tracking, comprising:

inputting a document comprising references to a plurality of objects;

creating a tree structure based on the document comprising a plurality of layers, each layers corresponding to a different mentions mention of a plurality of mentions, and wherein the different mentions are chained to one another, wherein leaf nodes of the tree structure correspond to different entity outcomes wherein each entity is a collection of mentions of the plurality of mentions that refer to a same object; and

searching the tree structure for at least one of the nodes in response to an entity tracking query, wherein searching comprises selecting the at least one of the nodes having a score greater than a threshold as a response to the entity tracking query,

each node having at least one partial entity and representing a unique result;

wherein the tree structure includes probability information representing the combined probability of;

a first mention of the plurality of mentions is part of a same entity as a second mention of the plurality of mentions;

a third mention of the plurality of mentions is part of the same entity as the first and second mentions, given that the first mention and the second mention are part of the same entity;

the third mention is part of the same entity as the first mention but not the second mention, given that the first mention is not part of the same entity as the second mention; and

the third mention is part of the same entity as the second mention but not the first mention, given that the first mention is not part of the same entity as the second mention.

10. The data storage device as defined in claim 9, wherein the tree structure is a Bell Tree structure comprising the plurality of layers, each layer of said plurality of layers having at least one node.

11. The data storage device as defined in claim 10 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 root layer includes a single node; and

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

12. The data storage device as defined in claim 11 wherein:

said nodes of each of the remainder of layers link the associated mention of a respective layer to each partial entity in any preceding node creating 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.

13. The data storage device as defined in claim 10 wherein:

the plurality of layers has a last leaf layer;

said last leaf layer representing all possible results from chaining the plurality of mentions.

14. The data storage device as defined in claim 11 wherein each node representing each different possible result has an associated score.

15. The data storage device as defined in claim 12 wherein each node representing each different possible result has an associated score.

16. The data storage device as defined in claim 13 wherein each leaf representing each different possible result has an associated score.