Indexing and searching of electronic message transmission thread sets

• US 20070038707A1
• Filed: 08/10/2005
• Published: 02/15/2007
• Est. Priority Date: 08/10/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fontoura, Marcus, Broder, Andrei, Lempel, Ronny, Herscovici, Michael, Eiron, Nadav, Shekita, Eugene, McPherson, John
• Granted Patent: US 7,565,347 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

A method includes describing the thread configurations of a volume of well-ordered electronic message transmissions (EMT) and utilizing the thread configuration data to conduct selective searches of the EMT volume. An apparatus includes a thread processor and a query manager. The thread processor analyzes the EMT threads and records the thread configuration data. The query manager utilizes the thread configuration data to conduct selective searches of the EMT volume.

Claims

1. A search engine comprising:

a compacting indexer of well-ordered threads of electronic message transmissions (EMTs); and

a query manager to search through an index produced by said compacting indexer and to identify at least one qualifying EMT of a qualifying EMT thread as a search result when provided with a query.

2. The search engine according to claim 1 and wherein said compacting indexer comprises a thread processor to determine the configurations of said EMT threads and to generate a compact EMT volume for indexing into an index.

3. The search engine according to claim 2 and wherein said thread processor comprises:

a docID assigner to assign consecutive numerical IDs to said EMTs from meta-data associated with said EMTs;

a compact EMT compiler to generate a compact EMT for each said numerical ID, said compact EMT being formed of said meta-data of said EMT and new content text added by said EMT to its thread; and

a thread configuration data compiler to compile thread configuration data for said EMT threads.

4. The search engine according to claim 3 and wherein said thread configuration data compiler comprises:

a root EMT determiner to determine a root EMT of said EMT thread; and

a last offspring determiner to determine a last offspring EMT of each EMT belonging to said EMT thread.

5. The search engine according to claim 4 and wherein said thread configuration data compiler also comprises a thread type determiner to determine a thread type of each said EMT thread.

6. The search engine according to claim 2 and wherein said query manager comprises:

a candidate enumerator to select a candidate EMT for examination with respect to terms of said query and said EMT thread configurations;

a postings iteration manager to search posting lists of said index for said terms; and

an assessment unit to assess multiple said qualifying EMTs against said query.

7. The search engine according to claim 6 and wherein said assessment unit comprises a candidate ranker which provides, per said qualifying EMT thread, said at least one qualifying EMT as said search result to said query according to a variable retrieval policy of said search engine wherein said retrieval policy is defined by at least one of a user and said search engine.

8. The search engine according to claim 7 and wherein said retrieval policy dictates that said result is at least one of the following:

the chronologically first said qualifying EMT in each said qualifying EMT thread;

the chronologically last said qualifying EMT in each said qualifying EMT thread;

the highest scoring said qualifying EMT in each said qualifying EMT thread; and

all said qualifying EMTs.

9. The search engine according to claim 2 and wherein said query manager comprises:

a query processor; and

a virtual cursor layer.

10. The search engine according to claim 9 and wherein said query processor comprises:

a postings iteration manager to search posting lists of said index for terms of said query; and

an assessment unit to assess multiple said qualifying EMTs against said query.

11. The search engine according to claim 9 and wherein said virtual cursor layer guides a candidate enumeration process to enumerate candidate EMTs with respect to terms of said query and said EMT thread configurations.

12. The search engine according to claim 10 and wherein said assessment unit comprises a candidate ranker which provides, per said qualifying EMT thread, said at least one qualifying EMT as said search result to said query according to a variable retrieval policy of said search engine wherein said retrieval policy is defined by at least one of a user and said search engine.

13. The search engine according to claim 12 and wherein said retrieval policy dictates that said result is at least one of the following:

the chronologically first said qualifying EMT in each said qualifying EMT thread;

the chronologically last said qualifying EMT in each said qualifying EMT thread;

the highest scoring said qualifying EMT in each said qualifying EMT thread; and

all said qualifying EMTs.

14. A method comprising:

representing an unmodified volume of electronic message transmission (EMT) threads as a compact EMT volume;

indexing said compact EMT volume into an index;

searching said index; and

returning EMT results from said unmodified volume.

15. The method according to claim 14 and wherein said representing comprises:

associating, with a unique ID number assigned to each EMT in said unmodified volume, meta-data of each said EMT and new content text added by each said EMT to its thread.

16. The method according to claim 15 and wherein said indexing comprises distinguishing between occurrences of a term in said EMT meta-data and in said EMT content.

17. The method according to claim 14 and also comprising determining thread configuration data describing said EMT threads and wherein said searching comprises searching said index with said thread configuration data.

18. The method according to claim 17 and wherein said determining comprises:

analyzing said EMT threads to identify a root EMT of each said EMT thread and a last offspring EMT of each said EMT.

19. The method according to claim 14 and wherein said searching comprises:

identifying as a candidate EMT, an EMT which appears in a posting list of said index of a required query term, said candidate EMT having content and meta-data;

verifying the occurrences of all remaining required terms of said query in at least one of said content, said meta-data and ancestor content of said candidate EMT;

verifying the absence of all forbidden terms of said query in said content, said meta-data and said ancestor content; and

advancing all posting lists of said index past invalid EMTs to select additional said candidate EMTs.

20. The method according to claim 19 and wherein said advancing comprises interpreting thread configuration data to determine the identities of said invalid EMTs.

21. The method according to claim 19 and wherein said returning comprises, per qualifying EMT thread, choosing at least one qualifying EMT meeting said query terms.

22. The method according to claim 21 and wherein a quantity and type of said qualifying EMTs is variable and is determined by at least one of a system and a user definition.

23. The method according to claim 22 and wherein said quantity and type of said qualifying EMTs is at least one of the following:

the chronologically first said qualifying EMT in each said qualifying EMT thread;

the chronologically last said qualifying EMT in each said qualifying EMT thread;

the highest scoring said qualifying EMT in each said qualifying EMT thread; and

all said qualifying EMTs.

24. A method comprising:

storing information describing configurations of discussion threads of EMTs;

compacting said EMT discussion threads; and

indexing compacted EMT discussion threads generated by said compacting.

25. The method according to claim 24 and wherein said information includes the following:

enumeration of said EMTs in each said EMT discussion thread;

thread types of each said EMT discussion thread;

a root EMT of each said EMT discussion thread; and

a last offspring EMT of each said EMT in each said EMT discussion thread

26. The method according to claim 25 and wherein said enumeration comprises consecutive numerical IDs assigned to each of said EMTs within each of said EMT discussion threads.

27. The method according to claim 25 and wherein said root EMT comprises the source EMT spawning said EMT thread.

28. The method according to claim 26 and wherein said last offspring EMT comprises the EMT having the highest said numerical ID of all EMTs referring to said EMT.

29. The method according to claim 24 and wherein each said EMT comprises meta-data and new content which said EMT adds to its discussion thread and wherein said compacting comprises per said EMT, identifying its said meta-data and said new content and wherein said indexing comprises indexing said meta-data and said new content for said EMTs.

30. The method according to claim 29 and wherein said second indexing comprises distinguishing between occurrences of a term in said EMT meta-data and in said EMT content.

31. A computer product readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps, said method steps comprising:

representing an unmodified volume of electronic message transmission (EMT) threads as a compact EMT volume;

indexing said compact EMT volume into an index;

searching said index; and

returning EMT results from said unmodified volume.