System and method for identifying unique and duplicate messages

• US 8,458,183 B2
• Filed: 01/30/2012
• Issued: 06/04/2013
• Est. Priority Date: 03/19/2001
• Status: Expired due to Term

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Kawai, Kenji, McDonald, David T.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/361,900
• Publication Number:
  US 20120130961A1
• Time in Patent Office: 491 Days
• Field of Search: 707/626, 707/736, 707/737, 707/822
• US Class Current: 707/737
• 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 identifying unique and duplicate messages is provided. Messages are maintained, and a header and message body are extracted from each of the messages. A hash code is calculated for each message over at least part of the header and the body of that message. The messages with matching hash codes are grouped. One message in each group with two or more messages is randomly selected as a unique message. The remaining messages in the group are marked as exact duplicate messages.

Claims

1. A system for identifying unique and duplicate messages, comprising:

a database of messages;

an extractor module to extract a header and a message body from each message;

a parser module to calculate a hash code for each message over at least part of the header and the body of that message and to group the messages having matching hash codes;

a deduper module to randomly select one message in each group with two or more messages as a unique message and to mark the remaining messages in the group as exact duplicate messages;

an attachment parser module to calculate a hash code over at least a portion of an attachment to two or more of the messages; and

a concatenator module to generate a compound hash code for each of the two or more messages by concatenating the hash code for that message and the hash code for the attachment; and

a processor to execute the modules.

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

a grouper module to group the two or more messages having matching compound hash codes;

a selection module to randomly select a single message in each group with two or more messages as a unique message; and

a message marker module to mark the remaining messages in the group as exact duplicate messages.

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

an identification module to identify the messages that are not unique and not exact duplicates and to group the identified messages by conversation thread; and

an order module to order the identified messages in order of length of the message body.

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

a comparison module to compare a longest identified message with each of the other identified messages in the conversation thread; and

a message marker module to mark at least one of the other identified messages in the conversation thread as a near duplicate of the longest identified message when the message body of the at least one other identified message is contained within the message body of the longest identified message.

5. A system according to claim 4, wherein the message deduper marks the longest identified message as unique.

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

a comparison module to compare a longest identified message with each of the other identified messages in the conversation thread; and

a message marker module to mark at least one of the other identified messages in the conversation thread as unique when the message body of the at least one other identified message is not contained within the message body of the longest identified message.

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

an identification module to identify the messages that are not unique and not exact duplicates and to group the identified messages by conversation thread;

a calculation module to calculate a hash code over at least a portion of an attachment to one or more of the identified messages;

an order module to order the identified messages in order of length of the message body;

a message comparison module to compare a longest identified message with each of the other identified messages in the conversation thread;

a determination module to determine that the message body of at least one of the other identified messages is contained within the message body of the longest identified message;

an attachment comparison module to compare the attachment hash codes for the longest identified message and the at least one other identified message; and

a message marker module to mark the at least one other identified message as a near duplicate of the longest message when the attachment hash codes match.

8. A system according to claim 1, wherein each hash code is calculated using a one-way function to generate a unique alphanumeric value comprising one of a purely numeric and purely alphabetic value.

9. A system according to claim 1, wherein the message extractor parses metadata from each of the messages, which is stored with the hash code for that message.

10. A method for identifying unique and duplicate messages, comprising the steps of:

maintaining messages;

extracting a header and a message body from each message;

calculating a hash code for each message over at least part of the header and the body of that message;

grouping the messages having matching hash codes;

randomly selecting one message in each group with two or more messages as a unique message; and

marking the remaining messages in the group as exact duplicate messages;

calculating a hash code over at least a portion of an attachment to two or more of the messages; and

concatenating the hash code for each of the two or more messages with the hash code for the attachment into a compound hash code,

wherein the steps are performed by a suitably-programmed computer.

11. A method according to claim 10, further comprising:

grouping the two or more messages having matching compound hash codes;

randomly selecting a single message in each group with two or more messages as a unique message; and

marking the remaining messages in the group as exact duplicate messages.

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

identifying the messages that are not unique and not exact duplicates and grouping the identified messages by conversation thread; and

ordering the identified messages in order of length of the message body.

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

comparing a longest identified message with each of the other identified messages in the conversation thread; and

marking at least one of the other identified messages in the conversation thread as a near duplicate of the longest identified message when the message body of the at least one other identified message is contained within the message body of the longest identified message.

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

marking the longest identified message as unique.

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

comparing a longest identified message with each of the other identified messages in the conversation thread; and

marking at least one of the other identified messages in the conversation thread as unique when the message body of the at least one other identified message is not contained within the message body of the longest identified message.

16. A method according to claim 10, further comprising:

identifying the messages that are not unique and not exact duplicates and grouping the identified messages by conversation thread;

calculating a hash code over at least a portion of an attachment to one or more of the identified messages;

ordering the identified messages in order of length of the message body;

comparing a longest identified message with each of the other identified messages in the conversation thread;

determining that the message body of at least one of the other identified messages is contained within the message body of the longest identified message;

comparing the attachment hash codes for the longest identified message and the at least one other identified message; and

marking the at least one other identified message as a near duplicate of the longest message when the attachment hash codes match.

17. A method according to claim 10, wherein each hash code is calculated using a one-way function to generate a unique alphanumeric value comprising one of a purely numeric and purely alphabetic value.

18. A method according to claim 10, further comprising:

parsing metadata from each of the messages; and

storing the metadata with the hash code for that message.

19. A method for identifying unique and duplicate messages, comprising the steps of:

maintaining messages;

extracting a header and a message body from each message;

calculating a hash code for each message over at least part of the header and the body of that message;

grouping the messages having matching hash codes;

randomly selecting one message in each group with two or more messages as a unique message; and

marking the remaining messages in the group as exact duplicate messages;

identifying the messages that are not unique and not exact duplicates and grouping the identified messages by conversation thread; and

ordering the identified messages in order of length of the message body,

wherein the steps are performed by a suitably-programmed computer.

20. A method according to claim 19, further comprising:

comparing a longest identified message with each of the other identified messages in the conversation thread; and

marking at least one of the other identified messages in the conversation thread as a near duplicate of the longest identified message when the message body of the at least one other identified message is contained within the message body of the longest identified message.

21. A method according to claim 20, further comprising:

marking the longest identified message as unique.

22. A method according to claim 19, further comprising:

comparing a longest identified message with each of the other identified messages in the conversation thread; and

marking at least one of the other identified messages in the conversation thread as unique when the message body of the at least one other identified message is not contained within the message body of the longest identified message.

23. A method for identifying unique and duplicate messages, comprising the steps of:

maintaining messages;

extracting a header and a message body from each message;

calculating a hash code for each message over at least part of the header and the body of that message;

grouping the messages having matching hash codes;

randomly selecting one message in each group with two or more messages as a unique message; and

marking the remaining messages in the group as exact duplicate messages;

identifying the messages that are not unique and not exact duplicates and grouping the identified messages by conversation thread;

calculating a hash code over at least a portion of an attachment to one or more of the identified messages;

ordering the identified messages in order of length of the message body;

comparing a longest identified message with each of the other identified messages in the conversation thread;

determining that the message body of at least one of the other identified messages is contained within the message body of the longest identified message;

comparing the attachment hash codes for the longest identified message and the at least one other identified message; and

marking the at least one other identified message as a near duplicate of the longest message when the attachment hash codes match,

wherein the steps are performed by a suitably-programmed computer.