Distributed email threading
Distributed email threading is disclosed. Emails are grouped into smaller related groups, as opposed to one large group, so that the groups are processed serially or in parallel to save processing power and time. Each email message group is handled in an independent job, which is distributable among any number of servers. A bipartite graph of email messages and message identifiers (such as subject line, recipient address, etc.) is created and used to determine connected sub-groups within the graph and, ultimately, which messages are connected to each other as part of an email thread. The sub-groups are processed independently for efficiency.
1. A method in a data processing system for distributed email threading, the method comprising:
receiving, by a processor, a set of email messages;
extracting, by the processor, identifiers from each email message in the set of email messages;
determining, by the processor, a bipartite graph of connections between the identifiers and the email messages in the set of email messages, a given connection between a first email message and a first identifier conveying that the first email message includes the first identifier, wherein the identifiers and the email messages in the bipartite graph of connections form two disjoint sets, the identifiers within a first disjoint set do not connect directly with each other, and the email messages within a second disjoint set do not connect directly with each other;
generating, based on the bipartite graph, one or more disjoint connected graphs, wherein each email message in a given disjointed connected graph shares at least one identifier with at least one other email message in the given disjointed connected graph;
determining, by the processor, groups of the email messages from among the set of email messages based on the bipartite graph of connections, a given group having email messages that belong to a same email conversation, each group of the email messages corresponding to a disjoint connected graph; and
performing, by the processor, email threading on two or more groups of email messages by processing in parallel the two or more groups of email messages independently of each other.
2. The method of claim 1 , wherein the bipartite graph includes a first set of nodes of corresponding email messages from the set of email messages.
3. The method of claim 1 , wherein the bipartite graph includes a second set of nodes corresponding to the identifiers from email messages in the set of email messages.
4. The method of claim 1 , wherein performing the email threading comprises:
performing, by the processor, the email threading on the two or more groups of email messages, wherein the email threading includes identifying forward, reply, or reply-all email messages of an email conversation to identify message relationships, the message relationships including one or more of a common email thread, individuals involved in a given email conversation, or duplicate emails, wherein a given email thread starts with an original email as a beginning of the email conversation and includes subsequent email messages in the email conversation; and
causing display, through a user interface, of one or more email conversations determined based on the email threading of a given group of email addresses.
5. The method of claim 1 , further comprising:
storing one or both of at least a portion of the email messages or at least a portion of the corresponding identifiers using a disjoint set data structure.
6. The method of claim 1 , wherein the identifiers include one or more message header fields.
7. The method of claim 6 , wherein the one or more message header fields include one or more of message recipient name or email address, message sender name or email address, message subject, carbon copy email address, blind carbon copy email address, message content type, message precedence, message identifier, in-reply-to message identifier, references message identifier, reply-to email address, or message archived-at link.
8. The method of claim 1 , wherein determining groups of email messages from among the set of email messages based on the bipartite graph includes identifying the one or more disjoint connected graphs within the bipartite graph.
9. A computing system for distributed email threading, comprising:
a memory having executable instructions; and
one or more hardware processors configured to execute the instructions to:
receive a set of email messages;
extract identifiers from each email message in the set of email messages;
determine a bipartite graph of connections between the identifiers and the email messages in the set of email messages, a given connection between a first email message and a first identifier conveying that the first email message includes the first identifier, wherein the identifiers and the email messages in the bipartite graph form two disjoint sets, the identifiers within a first disjoint set do not connect directly with each other, and the email messages within a second disjoint set do not connect directly with each other;
generate, based on the bipartite graph, one or more disjoint connected graphs, wherein each email message in a given disjointed connected graph shares at least one identifier with at least one other email message in the given disjointed connected graph;
determine groups of the email messages from among the set of email messages based on the bipartite graph of connections, a given group having email messages that belong to a same email conversation, each group of the email messages corresponding to a disjoint connected graph; and
perform email threading on two or more individual group of the groups of email messages by processing in parallel the two or more of groups of email messages independently of each other.
10. The computing system of claim 9 , wherein the bipartite graph includes a first set of nodes of corresponding email messages from the set of email messages.
11. The computing system of claim 9 , wherein the bipartite graph includes a second set of nodes corresponding to the identifiers from email messages in the set of email messages.
12. The computing system of claim 9 , wherein the one or more hardware processors are further configured to execute the instructions to:
perform email threading on individual group of the groups of email messages, wherein the email threading includes identifying forward, reply, or reply-all email messages of an email conversation to identify message relationships, the message relationships including one or more of a common email thread, individuals involved in a given email conversation, or duplicate emails, wherein a given email thread starts with an original email as a beginning of the email conversation and includes subsequent email messages in the email conversation; and
cause display, through a user interface, of one or more email conversations determined based on the email threading of a given group of email addresses.
13. The computing system of claim 9 , wherein the one or more hardware processors are further configured to execute the instructions to:
store one or both of at least a portion of the email messages or at least a portion of the corresponding identifiers using a disjoint set data structure.
14. The computing system of claim 9 , wherein the identifiers include one or more message header fields.
15. The computing system of claim 14 , wherein the one or more message header fields include one or more of message recipient name or email address, message sender name or email address, message subject, carbon copy email address, blind carbon copy email address, message content type, message precedence, message identifier, in-reply-to message identifier, references message identifier, reply-to email address, or message archived-at link.
16. The computing system of claim 9 , wherein determining groups of email messages from among the set of email messages based on the bipartite graph includes identifying the one or more disjoint connected graphs within the bipartite graph.