System and method for presenting message threads

• US 8,161,381 B2
• Filed: 07/09/2007
• Issued: 04/17/2012
• Est. Priority Date: 12/08/2000
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Newman, Paula S., Wang Baldonado, Michelle Q.
• Primary Examiner(s): Ries, Laurie
• Assistant Examiner(s): SMITH, TIONNA M
• Application Number:
  US11/827,145
• Publication Number:
  US 20070300153A1
• Time in Patent Office: 1,744 Days
• Field of Search: 715/255
• US Class Current: 715/255
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 51/216 Handling conversation history, e.g. grouping of messages in sessions or threads
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for presenting message threads is provided. A main body and one or more excerpts are parsed from each of a plurality of messages into nodes structured to form a message tree through a procedural top-down recursive descent. The nodes in the message tree are related by determining line-group types for the main body and the excerpts of each message, which are enumerated into partitions for each of the line-group types. An output network of alternative paths through the messages is created based upon the partitions of the message tree. A document is formed from the output network to identify and remove redundant components in each message.

Claims

1. A computer-implemented system for presenting message threads, comprising:

a memory; and

a processor operatively coupled to the memory and configured to execute computer executable program modules, including;

a grammar module defining a grammar comprising an array of arcs that each span a start state and an end state with each of the arcs associated with a line-group type test;

an analysis module comprising;

a parser module performing a procedural top-down recursive descent of a plurality of messages, comprising parsing features from the plurality of messages, which divide each message into a main body and one or more excerpts, matching each line in each of the main body and the excerpts to the start state and the end state in one of the arcs in the grammar, and evaluating the line-group type test associated with the arc;

an output network module building an output network comprising output network arcs that each correspond to the arcs in the grammar, each output network arc being assigned a cumulative weight that comprises weights assigned by the line-group type tests for the corresponding arcs in the grammar along a partial path through the output network terminating at that arc;

a message tree module creating a message tree comprising the maximally weighted paths in a forward direction through the output network for each of the main body and the excerpts;

a relationship module relating the messages in the message tree comprising, matching the excerpts in the message tree with a source message in the plurality of messages and identifying one or more predecessor message in the plurality of messages for each such main body in the message tree; and

a presentation module collating the source and the predecessor messages as related into a conversational document form.

2. A system according to claim 1, further comprising at least one of:

an extractor module extracting header information from the message, which is stored into one such node; and

a concatenation module logically concatenating the main body of the message into a single extent.

3. A system according to claim 1, further comprising:

a finite state machine partitioning the main body and the excerpts into the line-group types through a weighted finite state grammar; and

an output network of alternative paths comprising arcs that simultaneously correspond to a line of the message and an arc of the weighted finite state grammar.

4. A system according to claim 1, further comprising at least one of:

a thread formatter creating a compressed form of each message; and

a block formatter providing each message that is in reply to another such message as an annotation.

5. A computer-implemented method for presenting message threads, comprising:

defining a grammar comprising an array of arcs that each span a start state and an end state with each of the arcs associated with a line-group type test;

performing a procedural top-down recursive descent of a plurality of messages, comprising;

parsing features from the plurality of messages, which divide each message into a main body and one or more excerpts; and

matching each line in each of the main body and the excerpts to the start state and the end state in one of the arcs in the grammar and evaluating the line-group type test associated with the arc;

building an output network comprising output network arcs that each correspond to the arcs in the grammar, each output network arc being assigned a cumulative weight that comprises weights assigned by the line-group type tests for the corresponding arcs in the grammar along a partial path through the output network terminating at that arc;

creating a message tree comprising the maximally weighted paths in a forward direction through the output network for each of the main body and the excerpts;

relating the messages in the message tree comprising, matching the excerpts in the message tree with a source message in the plurality of messages and identifying one or more predecessor;

message in the plurality of messages for each such main body in the message tree; and

collating the source and the predecessor messages as related into a conversational document form.

6. A method according to claim 5, further comprising at least one of:

extracting header information from the message, which is stored into one such node; and

logically concatenating the main body of the message into a single extent.

7. A method according to claim 5, further comprising:

partitioning the main body and the excerpts into the line-group types through a weighted finite state grammar; and

creating an output network of alternative paths comprising arcs that simultaneously correspond to a line of the message and an arc of the weighted finite state grammar.

8. A method according to claim 5, further comprising at least one of:

creating a compressed form of each message; and

providing each message that is in reply to another such message as an annotation.

9. A computer-implemented system for presenting message threads, comprising:

a memory; and

a processor operatively coupled to the memory and configured to execute computer executable program modules, including;

a grammar module defining a grammar comprising an array of arcs that each span a start state and an end state with each of the arcs associated with a procedurally-coded test;

a parser module parsing features from a plurality of messages, which divide each message into a main body and one or more excerpts through a procedural top-down recursive descent;

a relationship module matching each line in the main body and the excerpts to the start state and the end state in one of the arcs in the grammar and evaluating the procedurally-coded test associated with the arc;

a network module creating an output network comprising output network arcs that each correspond to the arcs in the grammar, each output network arc being assigned a cumulative weight that comprises weights assigned by the procedurally-coded tests for the corresponding arcs in the grammar along a partial path through the output network terminating at that arc and creating a message tree comprising the maximally weighted paths in a forward direction through the output network for each of the main body and the excerpts;

a relationship module relating the messages in the message tree comprising, matching the excerpts in the message tree with a source message in the plurality of messages and identifying one or more predecessor message in the plurality of messages for each such main body in the message tree; and

a presentation module forming a collection of annotations comprised for each of the excerpts either having a matching source message or at least one predecessor message.

10. A system according to claim 9, further comprising at least one of:

a extraction module storing header information from each message into one such node; and

a concatenation module logically concatenating the main body of the message into a single extent.

11. A system according to claim 9, wherein the partitions of the line-group types are formed through a weighted finite state grammar.

12. A system according to claim 9, wherein the alternative paths of the output network comprise arcs that simultaneously correspond to a line of the message and an arc of a weighted finite state grammar.

13. A system according to claim 9, comprising:

a compressed presenter presenting the document as a compressed form of each message in a semi-linear sequence; and

a block presenter presenting the document as a block that provides each message that is in reply to another such message as an annotation.

14. A system according to claim 9, wherein the messages are selected from the group comprising email and documents.

15. A computer-implemented method for presenting message threads, comprising:

defining a grammar comprising an array of arcs that each span a start state and an end state with each of the arcs associated with a procedurally-coded test;

parsing features from a plurality of messages, which divide each message into a main body and one or more excerpts through a procedural top-down recursive descent;

matching each line in the main body and the excerpts to the start state and the end state in one of the arcs in the grammar and evaluating the procedurally-coded test associated with the arc;

creating an output network comprising output network arcs that each correspond to the arcs in the grammar, each output network are being assigned a cumulative weight that comprises weights assigned by the procedurally-coded tests for the corresponding arcs in the grammar along a partial path through the output network terminating at that arc;

creating a message tree comprising the maximally weighted paths in a forward direction through the output network for each of the main body and the excerpts;

relating the messages in the message tree comprising, matching the excerpts in the message tree with a source message in the plurality of messages and identifying one or more predecessor message in the plurality of messages for each such main body in the message tree; and

forming a collection of annotations comprised for each of the excerpts either having a matching source message or at least one predecessor message.

16. A method according to claim 15, further comprising at least one of:

storing header information from each message into one such node; and

logically concatenating the main body of the message into a single extent.

17. A method according to claim 15, further comprising:

forming the partitions of the line-group types through a weighted finite state grammar.

18. A method according to claim 15, wherein the alternative paths of the output network comprise arcs that simultaneously correspond to a line of the message and an arc of a weighted finite state grammar.

19. A method according to claim 15, comprising:

presenting the document as a compressed form of each message in a semi-linear sequence; and

presenting the document as a block that provides each message that is in reply to another such message as an annotation.

20. A method according to claim 15, wherein the messages are selected from the group comprising email and documents.