System and method for clustering nodes of a tree structure

• US 8,156,430 B2
• Filed: 03/03/2008
• Issued: 04/10/2012
• Est. Priority Date: 12/16/2002
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Newman, Paula S.
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US12/041,455
• Publication Number:
  US 20080154926A1
• Time in Patent Office: 1,499 Days
• Field of Search: 715/200, 715/234, 715/243, 715/254, 715/255
• US Class Current: 715/255
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A system and method for clustering nodes of a tree structure is provided. A plurality of messages is maintained. Each message is represented as a node in a tree structure. A word vector is assigned to each message. Pairs of the nodes are identified based on relationships in the tree structure. The nodes of one or more of the pairs are combined into clusters. Boundaries of each cluster are adjusted, including at least one of placing a root node into one such duster having a closest related child node, separating children nodes into distinct groups and retaining a relationship between a parent node and one such group including a nearest child node, and transferring a parent node to one such cluster having all children of the parent node. A digest of the messages, including one or more of the clusters is formed.

Claims

1. A system for clustering nodes of a tree structure, comprising:

a storage module to maintain a plurality of messages, each message represented as a node in a tree structure;

a word vector module to assign a word vector to each message;

a node pair module to identify pairs of the nodes based on relationships in the tree structure and to combine the nodes of one or more of the pairs into clusters;

a cluster boundary module to adjust boundaries of each cluster, comprising at least one of;

a placement module to place a root node into one such cluster having a closest related child node;

a retention module to separate children nodes into distinct groups and to retain a relationship between a parent node and one such group comprising a nearest child node; and

a transfer module to transfer a parent node to one such cluster having all children of the parent node;

a digest module to form a digest of the messages comprising one or more of the clusters; and

a display processor to execute the modules.

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

a parameter module to determine parameters comprising one or more of a halting cluster size, maximum cluster size, and halting distance; and

a comparison module to apply the parameters to each pair of the nodes.

3. A system according to claim 2, wherein the maximum cluster size is larger than the halting cluster size.

4. A system according to claim 2, wherein the nodes of the one or more pairs are combined into the clusters based on the parameters.

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

an primary assignment module to assign a primary status to those clusters that are larger than a minimum size;

a secondary assignment module to assign a secondary status to the clusters that are smaller than the minimum size; and

a presentation module to present the primary and secondary clusters.

6. A system according to claim 5, wherein the minimum size is determined by one of a predetermined number of the messages in one such primary cluster and a function of a number of the messages in the tree structure.

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

a distance module to determine a distance between the nodes of one or more pairs; and

a cluster module to combine the nodes into the clusters based on the distance.

8. A method for clustering nodes of a tree structure, comprising:

maintaining a plurality of messages, each message represented as a node in a tree structure;

assigning a word vector to each message;

identifying pairs of the nodes based on relationships in the tree structure and combining the nodes of one or more of the pairs into clusters;

adjusting boundaries of each cluster, comprising at least one of;

placing a root node into one such cluster having a closest related child node;

separating children nodes into distinct groups and retaining a relationship between a parent node and one such group comprising a nearest child node; and

transferring a parent node to one such cluster having all children of the parent node; and

forming a digest of the messages comprising one or more of the clusters.

9. A method according to claim 8, further comprising:

determining parameters comprising one or more of a halting cluster size, maximum cluster size, and halting distance; and

applying the parameters to each pair of the nodes.

10. A method according to claim 9, wherein the maximum cluster size is larger than the halting cluster size.

11. A method according to claim 9, wherein the nodes of the one or more pairs are combined into the clusters based on the parameters.

12. A method according to claim 8, further comprising:

assigning a primary status to those clusters that are larger than a minimum size;

assigning a secondary status to the clusters that are smaller than the minimum size; and

presenting the primary and secondary clusters.

13. A method according to claim 12, wherein the minimum size is determined by one of a predetermined number of the messages in one such primary cluster and a function of a number of the messages in the tree structure.

14. A method according to claim 8, further comprising:

determining a distance between the nodes of one or more pairs; and

combining the nodes into the clusters based on the distance.