E-MAIL THREAD HIERARCHY DETECTION

• US 20120066227A1
• Filed: 09/10/2010
• Published: 03/15/2012
• Est. Priority Date: 09/10/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Contractor, Danish, Joshi, Sachindra, Ng, Kenney, Hosurmath, Manjula Golla
• Granted Patent: US 8,898,177 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

A plurality of segments in an e-mail collection by parsing content of e-mails is generated. Corresponding segment signature for each segment is created and a signature index is populated using the generated segment signatures. After receiving a query e-mail, a plurality of query segments in the query e-mail is generated using content of the query e-mail and corresponding query segment signature for each query segment is generated. A query root segment is identified and corresponding query root segment signature is generated. A set of root segment signatures of the signature index is identified and the query root segment signature is compared with each root segment signature from the signature index. A subset of the signature index is identified, using a match between the root segment signature and the query root segment signature. An e-mail thread hierarchy is built using the identified subset of the signature index.

Claims

1. A computing device implemented method for identifying an e-mail thread hierarchy in a collection of e-mails, the method comprising:

parsing at least one e-mail from the collection of e-mails to generate a plurality of segments based on the content of the at least one e-mail;

creating a corresponding segment signature for each of the segments of the plurality of segments; and

populating a signature index using the created segment signatures of the plurality of segments.

2. The method of claim 1, wherein the step of creating the corresponding segment signature uses near-duplicate detection.

3. The method of claim 1, wherein the step of creating the corresponding segment signature includes a pre-defined number of tokens.

4. The method of claim 3, wherein the step of creating the corresponding segment signature includes a set of pre-defined tokens comprising at least one of a set of words and a set of numbers.

5. The method of claim 1, further comprises:

generating at least one of a word index and a metadata index, wherein the word index comprises at least one of a keyword and subject information, and wherein the metadata index comprises at least one of temporal information and navigation information.

6. The method of claim 1, further comprising:

receiving a query e-mail;

parsing the query e-mail to generate a plurality of query segments based on the content of the query e-mail;

creating a corresponding query segment signature for each of the query segments of the plurality of query segments; and

identifying a query root segment and corresponding query root segment signature of the query e-mail.

7. The method of claim 6, further comprising:

receiving a pre-defined token match threshold;

identifying a set of root segment signatures of the signature index;

comparing the query root segment signature with each root segment signature of the set of root segment signatures of the signature index;

identifying a subset of the signature index, wherein a match between the root segment signature and the query root segment signature is at least the pre-defined token match threshold; and

building the e-mail thread hierarchy using the identified subset of the signature index.

8. The method of claim 7, the step of building further comprising:

identifying a first e-mail having only one segment, wherein the first e-mail is corresponding to the query root segment signature in the subset of the signature index;

assigning the first e-mail as a root node of the e-mail thread hierarchy;

in a recursive manner, for all e-mails corresponding to the subset of the signature index;

comparing a plurality of segment signatures from the subset of the signature index by near-duplicate detection;

determining a position of corresponding e-mail in the e-mail thread hierarchy, in response to the comparing a plurality of segment signatures from the subset of the signature index; and

updating the e-mail thread hierarchy; and

presenting the e-mail thread hierarchy.

9. The method of claim 7, further comprising:

identifying a set of query words;

comparing the set of query words with contents of a word index associated with the subset of the signature index; and

modifying the subset of the signature index in response to the comparing the set of query words with the contents of the word index.

10. The method of claim 7, further comprising:

identifying a query metadata;

comparing the query metadata with contents of a metadata index associated with the subset of the signature index; and

modifying the subset of the signature index in response to the comparing the query metadata with the contents of the metadata index.

11. A system for identifying an e-mail thread hierarchy in an e-mail collection, the system comprising at least one processor and at least one memory, wherein the processor is adapted to:

parse at least one e-mail from the collection of e-mails to generate a plurality of segments based on the content of the at least one e-mail;

create a corresponding segment signature for each of the segments of the plurality of segments; and

populate a signature index using the created segment signatures of the plurality of segments.

12. The system of claim 11, wherein the creation of the corresponding segment signatures uses near-duplicate detection and uses a pre-defined number of tokens and a set of pre-defined tokens.

13. The system of claim 11, wherein the processor is further adapted to:

receive a query e-mail;

parse the query e-mail to generate a plurality of query segments based on the content of the query e-mail;

create a corresponding query segment signature for each of the query segments of the plurality of query segments;

identify a query root segment and corresponding query root segment signature of the query e-mail;

receive a pre-defined token match threshold;

identify a set of root segment signatures of the signature index;

compare the query root segment signature with each root segment signature of the set of root segment signatures of the signature index;

identify a subset of the signature index, wherein a match between the root segment signature and the query root segment signature is at least the pre-defined token match threshold; and

build the e-mail thread hierarchy using the identified subset of the signature index.

14. The system of claim 13, wherein the processor is further adapted to:

identify a first e-mail having only one segment, wherein the first e-mail is corresponding to the query root segment signature in the subset of the signature index;

assign the first e-mail as a root node of the e-mail thread hierarchy;

in a recursive manner, for all e-mails corresponding to the subset of the signature index;

compare a plurality of segment signatures from the subset of the signature index using a near duplicate detection approach;

determine a position of corresponding e-mail in the e-mail thread hierarchy, in response to the comparing a plurality of segment signatures from the subset of the signature index; and

update the e-mail thread hierarchy; and

present the e-mail thread hierarchy.

15. The system of claim 14, wherein the processor is further adapted to:

generate at least one of a word index and a metadata index, wherein the word index comprises at least one of keyword and subject information, and wherein the metadata index comprises at least one of temporal information and navigation information;

identify at least one of a set of query words and a query metadata;

compare at least one of the set of query words with contents of the word index associated with the subset of the signature index and the query metadata with contents of the metadata index associated with the subset of the signature index; and

modify the subset of the signature index in response to at least one of the comparing the set of query words with the contents of the word index and the comparing the query metadata with the contents of the metadata index.

16. A computer program product for detecting an e-mail thread hierarchy in an e-mail collection, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured to;

parse at least one e-mail from the collection of e-mails to generate a plurality of segments based on the content of the at least one e-mail;

create a corresponding segment signature for each of the segments of the plurality of segments; and

populate a signature index using the created segment signatures of the plurality of segments.

17. The computer program product of claim 16, wherein the creation of the corresponding segment signatures uses near-duplicate detection approach and uses a pre-defined number of tokens and a set of pre-defined tokens.

18. The computer program product of claim 16, further configured to:

receive a query e-mail;

parse the query e-mail to generate a plurality of query segments based on the content of the query e-mail;

create a corresponding query segment signature for each of the query segments of the plurality of query segments;

identify a query root segment and corresponding query root segment signature of the query e-mail;

receive a pre-defined token match threshold;

identify a set of root segment signatures of the signature index;

compare the query root segment signature with each root segment signature of the set of root segment signatures of the signature index;

identify a subset of the signature index, wherein a match between the root segment signature and the query root segment signature is at least the pre-defined token match threshold; and

build the e-mail thread hierarchy using the identified subset of the signature index.

19. The computer program product of claim 18, further configured to:

identify a first e-mail having only one segment, wherein the first e-mail is corresponding to the query root segment signature in the subset of the signature index;

assign the first e-mail as a root node of the e-mail thread hierarchy;

in a recursive manner, for all e-mails corresponding to the subset of the signature index;

compare a plurality of segment signatures from the subset of the signature index using a near duplicate detection approach;

determine a position of corresponding e-mail in the e-mail thread hierarchy, in response to the comparing a plurality of segment signatures from the subset of the signature index; and

update the e-mail thread hierarchy; and

present the e-mail thread hierarchy.

20. The computer program product of claim 19, further configured to:

generate at least one of a word index and a metadata index, wherein the word index comprises at least one of keyword and subject information, and wherein the metadata index comprises at least one of temporal information and navigation information;

identify at least one of a set of query words and a query metadata;

compare at least one of the set of query words with contents of the word index associated with the subset of the signature index and the query metadata with contents of the metadata index associated with the subset of the signature index; and

modify the subset of the signature index in response to at least one of the comparing the set of query words with the contents of the word index and the comparing the query metadata with the contents of the metadata index.