Message thread clustering

• US 8,751,588 B2
• Filed: 12/15/2010
• Issued: 06/10/2014
• Est. Priority Date: 12/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Loofbourrow, Wayne
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Wei, Siren
• Application Number:
  US12/969,550
• Publication Number:
  US 20120158857A1
• Time in Patent Office: 1,273 Days
• Field of Search: 709/204, 709/206, 709/205, 709/201, 709/202
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

A method and apparatus of a device that clusters threads of messages is described. In an exemplary method, the device receives multiple message threads, where each message thread includes one or more messages that are related to each message in that thread. For each of the message threads, the device computes a thread signature using affinity groups, where each affinity group is a group of messages that are related to each other. Furthermore, the device creates a group of related messages using the thread signatures.

Claims

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method comprising:

receiving a plurality of message threads, wherein each of the plurality of threads includes one or more messages that are related to each of the messages in that thread and a message includes a message header with a plurality of message addresses;

for each of the message threads, computing a thread signature using an affinity group, wherein the affinity group is a group of message addresses that represent entities that communicate with each other for a particular common purpose, the thread signature for each of the message threads is based on a plurality of distance vectors between the group message addresses in the affinity group and the message addresses of the one or more messages in that message thread, and the thread signature is a vector with a plurality of values, wherein each of the plurality of values is based on a corresponding one of the plurality of distance vectors; and

creating a group of related message threads using the plurality of thread signatures.

2. The non-transitory machine-readable medium of claim 1, wherein a message is of a type selected from the group consisting of email, Short Message Service, Multimedia Message Service, Enhanced Message Service, TWITTER, FACEBOOK, telephone message log, and instant messaging.

3. The non-transitory machine-readable medium of claim 2, wherein the plurality of message threads includes a plurality of message types.

4. The non-transitory machine-readable medium of claim 1, wherein the computing the thread signature comprises:

computing a message signature for each of the one or more messages in the message thread, wherein the message signature is distance vector between the plurality of message addresses of that message and the affinity group.

5. The non-transitory machine-readable medium of claim 1, wherein the entities communicate above a minimum frequency regarding the particular common purpose.

12. The non-transitory machine-readable medium of claim 1, wherein the creating a group comprises:

computing a plurality of thread similarities between pairs of message threads from the plurality of message threads; and

clustering the plurality of message threads using the plurality of thread similarities.

13. The non-transitory machine-readable medium of claim 4, wherein the computing a thread signature comprises further comprises:

averaging the one or more message signatures to arrive at the thread signature.

6. A method comprising:

receiving a plurality of message threads, wherein each of the plurality of threads includes one or more messages that are related to each of the messages in that thread and a message includes a message header with a plurality of message addresses;

for each of the message threads, computing a thread signature using an affinity group, wherein the affinity group is a group of message addresses that are related to each other and the thread signature for each of the message threads is based on a plurality of distance vectors between the group message addresses in the affinity group and the message addresses of the one or more messages in that message thread, and the thread signature is a vector with a plurality of values, wherein each of the plurality of values is based on a corresponding one of the plurality of distance vectors; and

creating a group of related message threads using the plurality of thread signatures.

7. The method of claim 6, wherein the plurality of message threads includes a plurality of message types.

8. The method of claim 6, wherein the computing the thread signature comprises:

computing a message signature for each of the one or more messages in the message thread, wherein the message signature is distance vector between the plurality of message addresses of that message and the affinity group.

14. The method of claim 6, wherein the creating a group comprises:

computing a plurality of thread similarities between pairs of message threads from the plurality of message threads; and

clustering the plurality of message threads using the plurality of thread similarities.

15. The method of claim 8, wherein the computing a thread signature comprises further comprises:

averaging the one or more message signatures to arrive at the thread signature.

9. An apparatus comprising:

means for receiving a plurality of message threads, wherein each of the plurality of threads includes one or more messages that are related to each of the messages in that thread and a message includes a message header with a plurality of message addresses;

for each of the message threads, means for computing a thread signature using an affinity group, wherein the affinity group is a group of message addresses that are related to each other and the thread signature for each of the message threads is based on a plurality of distance vectors between the group message addresses in the affinity group and the message addresses of the one or more messages in that message thread, and the thread signature is a vector with a plurality of values, wherein each of the plurality of values is based on a corresponding one of the plurality of distance vectors; and

means for creating a group of related message threads using the plurality of thread signatures.

10. The apparatus of claim 9, wherein the plurality of message threads includes a plurality of message types.

11. The apparatus of claim 9, wherein the means for computing the thread signature comprises:

means for computing a message signature for each of the one or more messages in the message thread, wherein the message signature is distance vector between the plurality of message addresses of that message and the affinity group.

16. The apparatus of claim 9, wherein the creating a group comprises:

means for computing a plurality of thread similarities between pairs of message threads from the plurality of message threads; and

means for clustering the plurality of message threads using the plurality of thread similarities.

17. The apparatus of claim 11, wherein the computing a thread signature comprises further comprises:

means for averaging the one or more message signatures to arrive at the thread signature.