Method for organizing large numbers of documents

• US 8,825,673 B2
• Filed: 07/02/2008
• Issued: 09/02/2014
• Est. Priority Date: 07/02/2007
• Status: Active Grant

• Current Assignee: Microsoft Israel Research And Development (2002) Ltd (Microsoft Corporation)
• Original Assignee: Equivio Ltd. (Microsoft Corporation)
• Inventors: Ravid, Yiftach, Milo, Amir
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US12/667,664
• Publication Number:
  US 20100198864A1
• Time in Patent Office: 2,253 Days
• Field of Search: 707/1, 707/100, 707/769, 707/692, 707/711, 707/736, 707/749, 707/758, 707/797, 707/804, 715/752
• US Class Current: 707/749
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images
• CPC Class Codes: H04L 51/216 Handling conversation history, e.g. grouping of messages in sessions or threads

Abstract

A computer product including a data structure for organizing of a plurality of documents, and capable of being utilized by a processor for manipulating data of the data structure and capable of displaying selected data on a display unit. The data structure includes a plurality of directionally interlinked nodes, each node being associated with one or more documents having a header and body text. All the documents are associated with a given node and have identical normalized body text. All documents that have identical normalized body text are associated with the same node. One or more of the nodes is associated with more than one document. For any node that is a descendent of another node, the normalized body text of each document associated with the node is inclusive of the normalized body text of a document that is associated with the other node.

Claims

1. A non-transitory computer product including a data structure for organizing of a plurality of documents, and capable of being utilized by a processor for manipulating data of said data structure and for displaying selected data on a display unit, said data structure comprising:

a plurality of directionally interlinked nodes, each node being directly linked to one or more documents, at least one of the nodes being directly linked to more than one document, each document having at least a header and a body text, each document having a fingerprint, all documents that are directly linked to a same node having a same fingerprint and identical normalized body text, and all documents that have a same fingerprint and identical normalized body text being directly linked to the same node;

wherein for any first node of said nodes that is a descendent of a second node of said nodes, the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node,

wherein each fingerprint comprises a representation of the normalized body text of a corresponding document,

wherein the normalized body text is the body text in which at least body text formatting and added characters are removed, and

wherein said plurality of nodes are arranged in terms of more than one tree, each tree comprising at least one node from said plurality of directionally interlinked nodes, each tree comprising at least a root node and at least a leaf node, a root node being a node that is not a descendant of any other node, and a leaf node being a node that has no descendent nodes, a node not being prohibited from being both a root node and a leaf node, all nodes that are descendant from said root node are contained by said tree.

2. The non-transitory computer product of claim 1, wherein all documents having the same fingerprint and being directly linked to the same node have identical normalized subject parameter in said header.

3. The non-transitory computer product of claim 1 wherein said documents are emails.

4. The non-transitory computer product of claim 1 wherein said documents are emails and wherein all emails having the same fingerprint and being directly linked to the same node further having identical normalized attachments.

5. The non-transitory computer product of claim 1 wherein:

said plurality of nodes are arranged in terms of at least a first tree and a second tree that contain a link to one another; and

said link is indicative of the fact that said first tree contains a node that is directly linked to a document that is a near-duplicate of a document that is directly linked to a node in said second tree.

6. The non-transitory computer product of claim 1 wherein said documents are emails, and the computer product further comprises additional nodes that are directly linked to presumed documents.

7. The non-transitory computer product of claim 1, wherein the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node, irrespective of whether a normalized subject parameter from a header of a document directly linked to the first node and a normalized subject parameter from a header of a document directly linked to the second node are identical.

8. The non-transitory computer product of claim 1, wherein said documents are emails, and all emails being directly linked to the same node further having the same normalized one or more attachments, the normalized body text of each email directly linked to the first node being inclusive of the normalized body text of each email that is directly linked to the second node, irrespective of whether a normalized attachment in an email directly linked to the first node and a normalized attachment in an email directly linked to the second node are identical.

9. The non-transitory computer product of claim 8 wherein said second node includes at least one attachment, which is not included in said first node and wherein said first node is identified by an inclusive minus flag.

10. The non-transitory computer product of claim 1, wherein said normalized body text includes the body text in which headers, footers, disclaimers and signatures are removed.

11. The non-transitory computer product of claim 1, wherein the data structure comprises a hierarchical data structure wherein the hierarchical data structure is identical irrespective of the order that the documents are processed.

12. A system comprising:

a processor and associated display communicating with a data structure,

the data structure comprising;

a plurality of directionally interlinked nodes, each node being directly linked to one or more documents, at least one of the nodes being directly linked to more than one document, each document having at least a header and a body text, each document having a fingerprint, all documents that are directly linked to a same node having a same fingerprint and identical normalized body text, and all documents that have a same fingerprint and identical normalized body text being directly linked to the same node;

wherein for any first node of said nodes that is a descendent of a second node of said nodes, the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node,

wherein each fingerprint comprises a representation of the normalized body text of a corresponding document,

wherein the normalized body text is the body text in which at least body text formatting and added characters are removed,

wherein said plurality of nodes are arranged in terms of more than one tree, each tree comprising at least one node from said plurality of directionally interlinked nodes, each tree comprising at least a root node and at least a leaf node, a root node being a node that is not a descendant of any other node, and a leaf node being a node that has no descendent nodes, a node not being prohibited from being both a root node and a leaf node, all nodes that are descendant from said root node are contained by said tree,

wherein said plurality of nodes are arranged in terms of at least a first tree and a second tree that contain a link to one another, and

wherein said link is indicative of the fact that said first tree contains a node that is directly linked to a document that is a near-duplicate of a document that is directly linked to a node in said second tree,

the processor and associated display configured to manipulate data of said data structure and display selected data on a display unit, wherein said processor is further configured to display said first tree and a node from said second tree in close proximity on said display unit.

13. The system of claim 12 wherein said processor is configured to mark for said display unit an entire thread inclusively including all the nodes directly between a root node and given leaf node.

14. A system comprising:

a processor and associated display communicating with a data structure,

the data structure comprising;

a plurality of directionally interlinked nodes, each node being directly linked to one or more documents, at least one of the nodes being directly linked to more than one document, each document having at least a header and a body text, each document having a fingerprint, all documents that are directly linked to a same node having a same fingerprint and identical normalized body text, and all documents that have a same fingerprint and identical normalized body text being directly linked to the same node;

wherein for any first node of said nodes that is a descendent of a second node of said nodes, the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node,

wherein each fingerprint comprises a representation of the normalized body text of a corresponding document,

wherein the normalized body text is the body text in which at least body text formatting and added characters are removed, and

wherein said plurality of nodes are arranged in terms of more than one tree, each tree comprising at least one node from said plurality of directionally interlinked nodes, each tree comprising at least a root node and at least a leaf node, a root node being a node that is not a descendant of any other node, and a leaf node being a node that has no descendent nodes, a node not being prohibited from being both a root node and a leaf node, all nodes that are descendant from said root node are contained by said tree,

the processor and associated display configured to manipulate said data structure and display selected data on a display unit, wherein said processor is further configured to compare text of two documents, each document having a fingerprint, said documents being directly linked to different nodes.

15. A system comprising:

a processor and associated display communicating with a data structure,

the data structure comprising;

a plurality of directionally interlinked nodes, each node being directly linked to one or more documents, at least one of the nodes being directly linked to more than one document, each document having at least a header and a body text, each document having a fingerprint, all documents that are directly linked to a same node having a same fingerprint and identical normalized body text, and all documents that have a same fingerprint and identical normalized body text being directly linked to the same node;

wherein for any first node of said nodes that is a descendent of a second node of said nodes, the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node,

wherein each fingerprint comprises a representation of the normalized body text of a corresponding document,

wherein the normalized body text is the body text in which at least body text formatting and added characters are removed, and

wherein said plurality of nodes are arranged in terms of more than one tree, each tree comprising at least one node from said plurality of directionally interlinked nodes, each tree comprising at least a root node and at least a leaf node, a root node being a node that is not a descendant of any other node, and a leaf node being a node that has no descendent nodes, a node not being prohibited from being both a root node and a leaf node, all nodes that are descendant from said root node are contained by said tree,

the processor and associated display configured to manipulate said data structure and display selected data on a display unit, wherein said processor is further configured to display the header and the body text of a document, said document having a fingerprint and being directly linked to one of the nodes.

16. The system of claim 15 wherein at least one of said documents includes at least one member of a group that includes:

signature, disclaimers, attachment notification, and at least one attachment, and wherein said processor is configured to suppress the display of at least one of said members.

17. The system of claim 15 wherein said document is an email and said processor is further configured to display one or more attachments of said email being directly linked to one of the nodes.

18. A system comprising:

a processor and associated display communicating with a data structure,

the data structure comprising;

a plurality of directionally interlinked nodes, each node being directly linked to one or more documents, at least one of the nodes being directly linked to more than one document, each document having at least a header and a body text, each document having a fingerprint, all documents that are directly linked to a same node having a same fingerprint and identical normalized body text, and all documents that have a same fingerprint and identical normalized body text being directly linked to the same node;

wherein for any first node of said nodes that is a descendent of a second node of said nodes, the normalized body text of each document that is directly linked to the first node is inclusive of the normalized body text of each document that is directly linked to the second node,

wherein each fingerprint comprises a representation of the normalized body text of a corresponding document,

wherein the normalized body text is the body text in which at least body text formatting and added characters are removed, and

wherein said plurality of nodes are arranged in terms of more than one tree, each tree comprising at least one node from said plurality of directionally interlinked nodes, each tree comprising at least a root node and at least a leaf node, a root node being a node that is not a descendant of any other node, and a leaf node being a node that has no descendent nodes, a node not being prohibited from being both a root node and a leaf node, all nodes that are descendant from said root node are contained by said tree,

the processor and associated display configured to manipulate said data structure and display selected data on a display unit, wherein said processor is further configured to display a list of documents that are directly linked to leaf nodes, each of the documents having a respective fingerprint, wherein a leaf node comprises a node that has no descendant nodes.