System And Method for Processing A Message Store For Near Duplicate Messages

• US 20090307630A1
• Filed: 08/17/2009
• Published: 12/10/2009
• Est. Priority Date: 03/19/2001
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Kawai, Kenji, McDonald, David T.
• Granted Patent: US 7,836,054 B2
• Time in Patent Office: Days
• US Class Current: 715/810
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/08 Annexed information, e.g. attachments
• CPC Class Codes: H04L 51/216 Handling conversation history, e.g. grouping of messages in sessions or threads
• CPC Class Codes: H04L 51/42 Mailbox-related aspects, e.g. synchronisation of mailboxes
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method for processing a message store for near duplicate messages is provided. Metadata, content, and each attachment associated with messages are extracted. Near duplicate messages in the message store are identified. Compound digests taken of the metadata for, of the content contained in, and of the each attachment associated with each of the messages in the message store are compared. Each message having a compound digest not matching the compound digest of any other message is marked as unique and each message having a compound digest matching the compound digest of at least one other message is marked as an exact duplicate. Messages remaining unmarked and having similar content are grouped into sets that each includes one or more near duplicate messages. One of the near duplicate messages is designated as unique and each remaining near duplicate message in the set is designated as a near duplicate.

Claims

1. A system for processing a message store for near duplicate messages, comprising:

a deduper module configured to identify near duplicate messages in a message store, comprising;

a comparer module configured to compare compound digests taken of metadata for, of content contained in, and of each attachment associated with each of the messages in the message store; and

a marker module configured to mark each such message having a compound digest not matching the compound digest of any other such message as unique; and

mark each such message having a compound digest matching the compound digest of at least one other such message as an exact duplicate; and

a classifier module configured to group those messages remaining unmarked and having similar content into sets that each comprise one or more near duplicate messages, wherein the marker is further configured to designate a first of the near duplicate messages in each of the sets as unique and each remaining near duplicate message in the set as a near duplicate; and

a processor to execute each of the modules, which are stored on a computer-readable storage medium.

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

a message digester module configured to calculate a message sequence comprising a substantially unique hash code over at least part of the metadata for and of content contained in each message as a message sequence;

an attachment digester module configured to calculate an attachment sequence comprising a substantially unique hash code over at least part of the each attachment associated with each message; and

a concatenator module configured to concatenate the message sequence and the attachment sequence into the compound digest.

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

a user interface to present the near duplicate messages for user review and selection.

4. A system according to claim 1, wherein one or more of the messages are selected from the group comprising reply messages and forwarded messages.

5. A system according to claim 1, wherein the metadata comprises one or more fields of a header comprised as part of each message.

6. A system according to claim 1, wherein the compound digest is calculated using a one-way function and comprises alphanumeric, numeric, and alphabetic character strings.

7. A computer-implemented method for processing a message store for near duplicate messages, comprising:

maintaining messages in a message store;

retrieving the messages from the message store and extracting metadata for, content contained in, and each attachment associated with each of the messages in the message store into a memory;

identifying near duplicate messages in the message store, comprising;

comparing compound digests taken of the metadata for, of the content contained in, and of the each attachment associated with each of the messages in the message store;

marking each such message having a compound digest not matching the compound digest of any other such message as unique; and

marking each such message having a compound digest matching the compound digest of at least one other such message as an exact duplicate;

grouping those messages remaining unmarked and having similar content into sets that each comprise one or more near duplicate messages;

designating a first of the near duplicate messages in each of the sets as unique and each remaining near duplicate message in the set as a near duplicate; and

outputting the unique, exact duplicate, and near duplicate message markings to the message store.

8. A computer-implemented method according to claim 7, further comprising:

calculating a message sequence comprising a substantially unique hash code over at least part of the metadata for and of content contained in each message as a message sequence;

calculating an attachment sequence comprising a substantially unique hash code over at least part of the each attachment associated with each message; and

concatenating the message sequence and the attachment sequence into the compound digest.

9. A computer-implemented method according to claim 7, further comprising:

presenting the near duplicate messages for user review and selection.

10. A computer-implemented method according to claim 7, wherein one or more of the messages are selected from the group comprising reply messages and forwarded messages.

11. A computer-implemented method according to claim 7, wherein the metadata comprises one or more fields of a header comprised as part of each message.

12. A computer-implemented method according to claim 7, wherein the compound digest is calculated using a one-way function and comprises alphanumeric, numeric, and alphabetic character strings.

13. A computer-readable storage medium holding code for performing the process according to claim 7.

14. A system for classifying messages, comprising:

a metadata signature for metadata describing and a content signature signifying each of a plurality of messages in a message store;

a message deduper module configured to identify those messages having both unique metadata signatures and content signatures as unique messages; and

to identify those messages having both matching metadata signatures and content signatures as exact duplicate messages;

a message processor module configured to process any of the messages remaining unidentified, comprising;

a comparer module configured to compare the contents of those remaining messages having matching metadata signatures; and

a marker module configured to designate each of the matching messages having unique content as unique messages and any remaining messages as near duplicate messages;

an attachment signature for each attachment comprised with one or more of the message;

a compound signature for the metadata signature, content signature, and the attachment signature for each attachment comprised with each message, wherein the deduper module is further configured to identify those exact duplicate messages and those near duplicate messages having unique compound signatures as unique messages; and

a processor to execute each of the modules, which are stored on a computer-readable storage medium.

15. A system according to claim 14, further comprising:

a digester module configured to generate each of the metadata signatures, content signatures, and attachment signatures as hash codes respectively taken over at least part of the metadata, content, and attachment for the associated message.

16. A system according to claim 14, further comprising:

a shadow store to store the non-unique messages.

17. A computer-implemented method for classifying messages, comprising:

maintaining a plurality of messages in a message store;

retrieving the messages from the message store into a memory;

forming a metadata signature for the metadata describing and the content signature signifying each of the plurality of messages in the message store;

identifying those messages having both unique metadata signatures and content signatures as unique messages;

identifying those messages having both matching metadata signatures and content signatures as exact duplicate messages;

processing any of the messages remaining unidentified, comprising;

comparing the contents of those remaining messages having matching metadata signatures; and

designating each of the matching messages having unique content as unique messages and any remaining messages as near duplicate messages;

forming an attachment signature for each attachment comprised with one or more of the messages;

forming a compound signature for the metadata signature, content signature, and the attachment signature for each attachment comprised with each message;

identifying those exact duplicate messages and those near duplicate messages having unique compound signatures as unique messages; and

outputting the unique, exact duplicate, and near duplicate message identifications to the message store.

18. A computer-implemented method according to claim 17, further comprising:

generating each of the metadata signatures, content signatures, and attachment signatures as hash codes respectively taken over at least part of the metadata, content, and attachment for the associated message.

19. A computer-implemented method according to claim 17, further comprising:

maintaining a shadow store to store the non-unique messages.

20. A computer-readable storage medium holding code for performing the process according to claim 17.