Computer-implemented system and method for identifying near duplicate messages

• US 8,626,767 B2
• Filed: 06/03/2013
• Issued: 01/07/2014
• 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/909,065
• Publication Number:
  US 20130268610A1
• Time in Patent Office: 218 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 computer-implemented system and method for identifying near duplicate messages is provided. Messages each including a content body are grouped by conversation thread. One or more of the messages also includes an attachment. The messages for each conversation thread are sorted in order of message length. At least one of the messages is selected from one of the threads and the body of the selected message is compared with the body of one such shorter message in that thread. A determination is made that the body of the shorter message is included in the body of the selected message. Hash codes of the attachments for the selected message and the shorter message are compared. The shorter message is marked as a near duplicate message of the selected message when the hash codes of the attachments match.

Claims

1. A computer-implemented system for identifying near duplicate messages, comprising:

a processor coupled to a memory to execute the following modules comprising;

a message grouping module to group by conversation thread, messages each comprising a content body, wherein one or more of the messages also includes an attachment;

a message sorting module to sort the messages for each conversation thread in order of message length;

a message selection module to select for one of the threads at least one of the messages and to compare the body of the selected message with the body of one such shorter message in that thread;

a determination module to determine that the body of the shorter message is included in the body of the selected message;

a message relationship module to determine a relationship between the selected message and the shorter message by marking the shorter message as a near duplicate of the selected message if the selected message and the shorter message do not have attachments and by comparing hash codes of the attachments for the selected message and the shorter message, if the selected message and the shorter message each have attachments, and marking the shorter message as a near duplicate message of the selected message when the hash codes of the attachments match.

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

a further comparison module to compare one of the other messages with each of the shorter messages in the thread;

a message determination module to determine that the body of one such shorter message is not included in the body of the other message; and

a comparison selection module to select a further one of the messages for comparison.

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

a further comparison module to compare one of the other messages with the shorter messages in the thread;

a message determination module to determine that the body of one such shorter message is included in the body of the other message;

a further comparison module to compare hash codes of the attachments for the other message and the one such shorter message;

a hash determination module to determine that the hash codes do not match; and

a comparison selection module to select a further one of the messages for comparison.

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

a hash generator to generate compound hash codes for each message with an attachment by generating a hash code based on at least part of a header associated with the message and the message body, by generating a hash code for the attachment, and by concatenating the hash codes for the message body and the attachment as the compound hash.

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

a hash sorting module to sort the messages by hash code into groupings of the messages with the same hash code; and

a unique message module to randomly select one of the messages in at least one of the groupings as a unique message.

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

a duplicate message marker to mark the remaining messages in the grouping as duplicate messages.

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

a log to record the shorter message and the near duplicate marking of the shorter message.

8. A system according to claim 1, wherein the near duplicate message comprises content that is recursively included in the selected message.

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

a message inclusion module to identify the shorter message as being recursively included in the selected message based on a message separator and a subject line indicator.

10. A method implemented by a computer comprising at least one processor for identifying near duplicate messages, comprising:

grouping by conversation thread, messages each comprising a content body, wherein one or more of the messages also includes an attachment;

sorting the messages for each conversation thread in order of message length;

for one of the threads, selecting at least one of the messages and comparing the body of the selected message with the body of one such shorter message in that thread;

determining that the body of the shorter message is included in the body of the selected message;

determining a relationship between the selected message and the shorter message comprising at least one of;

if the selected message and the shorter message do not have attachments, marking the shorter message as a near duplicate of the selected message; and

if the selected message and the shorter message each have attachments, comparing hash codes of the attachments for the selected message and the shorter message and marking the shorter message as a near duplicate message of the selected message when the hash codes of the attachments match.

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

comparing one of the other messages with each of the shorter messages in the thread;

determining that the body of one such shorter message is not included in the body of the other message; and

selecting a further one of the messages for comparison.

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

comparing one of the other messages with the shorter messages in the thread;

determining that the body of one such shorter message is included in the body of the other message;

comparing hash codes of the attachments for the other message and the one such shorter message;

determining that the hash codes do not match; and

selecting a further one of the messages for comparison.

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

generating compound hash codes for each message with an attachment, comprising;

generating a hash code based on at least part of a header associated with the message and the message body;

generating a hash code for the attachment; and

concatenating the hash codes for the message body and the attachment as the compound hash.

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

sorting the messages by hash code into groupings of the messages with the same hash code; and

randomly selecting one of the messages in at least one of the groupings as a unique message.

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

marking the remaining messages in the grouping as duplicate messages.

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

recording the shorter message and the near duplicate marking of the shorter message in a log.

17. A method according to claim 10, wherein the near duplicate message comprises content that is recursively included in the selected message.

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

identifying the shorter message as being recursively included in the selected message based on a message separator and a subject line indicator.