Methods, systems, and user interface for e-mail search and retrieval

Methods and systems for searching e-mails are disclosed. In one embodiment, a method for searching e-mails includes receiving input indicative of one or more search terms. A query plan is determined based on the one or more search terms. The method includes performing a search in response to the query plan to determine information related to the one or more e-mails. Then, a set of results are generated based on the information related to the one or more e-mails.

BACKGROUND OF THE INVENTION

Embodiments of the present invention generally relate to techniques for processing electronic messages. More particularly, the present invention relates to methods, systems, and user interfaces for e-mail search and retrieval.

Collaboration using electronic messaging, such as e-mail and instant messaging, is becoming increasingly ubiquitous. Many users and organizations have transitioned to “paperless” offices, where information and documents are communicated almost exclusively using electronic messaging. As a result, users and organizations are also now expending time and money to sort and archive increasing volumes of digital documents and data.

At the same time, state and federal regulators such as the Federal Energy Regulatory Commission (FERC), the Securities and Exchange Commission (SEC), and the Food and Drug Administration (FDA) have become increasingly aggressive in enforcing regulations requiring storage, analysis, and reporting of information based on electronic messages. Additionally, criminal cases and civil litigation frequently employ electronic discovery techniques, in addition to traditional discovery methods, to discover information from electronic documents and messages.

One problem is that complying with these disclosure and/or reporting requirements is difficult because of the large amounts of electronic messages that accumulate. As broadband connections to the Internet are common in most homes and businesses, e-mails frequently include one or more multi-megabyte attachments. Moreover, these e-mails and attachments are increasingly of diverse and propriety formats, making later access to data difficult without the required software.

Another problem is that the disclosure and/or reporting requirements do not simply require that the electronic message be preserved and then disclosed. Often, the disclosure and/or reporting requirements are more focused toward information about the electronic message, such as who had access to sensitive data referred to in the contents of a particular electronic message. Some companies have teams of employees spending days and weeks reviewing e-mails in order to respond to regulatory audits and investigations. For these reasons, the inventors believe that users and organizations need electronic message analysis solutions to help lower costs in disclosing and/or reporting information related to electronic messaging.

In light of the above, there is a need for techniques for processing electronic messages that address some of the problems in the prior art.

BRIEF SUMMARY OF THE INVENTION

Embodiments of the present invention generally relate to techniques for processing electronic messages. More particularly, the present invention relates to methods, systems, and user interfaces for e-mail search and retrieval.

In various embodiments, a method for searching e-mails includes receiving input indicative of one or more search terms. A query plan is determined based on the one or more search terms. A search is then performed in response to the query plan to determine information related to the one or more e-mails. A set of results is generated based on the information related to the one or more e-mails.

In some embodiments, given large volumes of e-mails, a search request includes specific textual strings found in the body of an e-mail or the subject line of an e-mail. The search request may also include other parameters, such as a date-range and the like.

In one embodiment, performing a search includes organizing the content in an index, using a full-text searchable index for a textual string-based search and a relational database with database records for range queries. In addition to performing a search, the user may add new tags and other annotations to the search results using a relational database. When data is stored in the full-text index and a relational table, a query plan may be determined and generated to perform the search.

In some embodiments, determining the query plan based on the one or more search terms includes determining a cost associated with executing a database query. A cost associated with executing a full-text query is further determined. The query plan is then generated using a combination of the database query and the full-text query.

In one embodiment, generating the set of results based on the information related to the one or more e-mails includes receiving a first portion of the information in response to the database query. A second portion of the information is received in response to the full-text query. The first and second portions of the information are then merged to generate the set of results.

In various embodiments, determining the query plan based on the one or more search terms includes receiving a filter associated with a set of e-mails. A query is generated in response to the filter. Performing the search using the query plan may include performing the search asynchronously. A score may also be associated with each of the one or more e-mails. Relevance of the one or more e-mails may be determined in response to the score associated with each of the one or more e-mails.

In some embodiments, a computer program product includes a computer-readable medium storing a set of code modules which when executed by a processor of a computer system cause the processor to search for e-mails. The computer program product includes code for receiving input indicative of one or more search terms, code for determining a query plan based on the one or more search terms, code for performing a search in response to the query plan to determine information related to the one or more e-mails, and code for generating a set of results based on the information related to the one or more e-mails.

In further embodiments, a system for searching e-mails includes a crawler, an indexer, and a query engine. The crawler is configured to receive a plurality of e-mails. The indexer is configured to store index information associated with the plurality of e-mails in a database index and a full-text index. The query engine is configured to receive input indicative of one or more search terms, determine a query plan based on the one or more search terms, perform a search in response to the query plan to determine information related to the one or more e-mails, and generate a set of results based on the information related to the one or more e-mails.

A further understanding of the nature and the advantages of the inventions disclosed herein may be realized by reference of the remaining portions of the specification and the attached drawings.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present invention generally relate to techniques for processing electronic messages. More particularly, the present invention relates to methods, systems, and user interfaces for e-mail search and retrieval.

Processing of Electronic Messages

FIG. 1is a block diagram of an electronic message processing system100in one embodiment according to the present invention. Electronic message processing system100includes master index105, messaging applications programming interface (MAPI) module110, e-mail servers115, duplicate eliminator120, buffer manager125, indexer130, thread analyzer135, topic classifier140, analytics extraction, transformation, and loading (ETL) module145, directory interface150, and directory servers155. Master index105includes e-mail tables160, e-mail full text index165, topic tables170, cluster full text index175, distribution list full text index180, dimension tables185, participant tables190, and fact tables195. E-mail servers115include one or more mail servers117. Directory servers155include one or more directory servers157.

Master index105includes hardware and/or software elements that provide storage and retrieval of information associated with electronic messages, such as e-mail, instant messaging (IM) messages, Short Message Service (SMS) messages, Multimedia Message Service (MMS), and the like. Some examples of master index105are flat files, databases, data marts, data warehouses, and other repositories of data. Although the disclosure references electronic messages as e-mail messages, the disclosure should not be considered as limited to only e-mail message formats. The disclosure may also apply to other types of electronic messages, such as IM, SMS, MMC messages, and the like.

In various embodiments, e-mail tables160store information associated with e-mail messages processed by the system100. E-mail full text index165stores an inverted index that enables fast searching of contents (e.g., headers and body), metadata, and attachments of e-mail messages processed by the system100. Topic tables170store relationships between categories or topics and e-mail messages processed by the system100. Cluster full text index175stores an index of e-mail messages that have a close relationship, such as relationships based on statistical analysis of noun phrases, and the like. The e-mail messages having close relationships are then associated with topics in the topic tables170. Distribution list full text index180stores the full text of e-mail messages associated with a distribution or mailing list. Participant tables190store information related to participants of a distribution or mailing list (e.g., To-recipients, CC-recipients, BCC-recipients, etc.). Dimension tables185and fact tables195store information related to data warehouse processing of e-mail messages.

MAPI module110is linked to the e-mail servers115and to the duplicate eliminator120. In this example, the e-mail servers115include one or more mail servers117. MAPI module110includes hardware and/or software elements that communicate with the e-mail servers115. E-mail servers115include hardware and/or software elements that provide electronic messaging services, such as e-mail transport, storage, and retrieval. One example of the mail servers117is a computer system running Microsoft Exchange Server 2000 from Microsoft Corporation of Redmond, Wash. In other examples, the e-mail servers117may include operating systems, such as Microsoft Windows 2000/XP/2003, UNIX, and Linux, and mail transport agents, mail user agents, and the like. E-mail messages may be stored on the mail servers117in a file, such as an Outlook PST file, and the like.

Duplicate eliminator120includes hardware and/or software elements that detect and eliminate redundant and/or duplicative information retrieved by the MAPI module110. Buffer manager125is linked to the duplicate eliminator120and the indexer130. Buffer manager125includes hardware and/or software elements that manage data communications between the duplicate eliminator120and the indexer130.

Indexer130is linked to the master index105. Indexer130includes hardware and/or software elements that process electronic messages to determine message content and generate metadata associated with the electronic messages. For example, the index130may process an e-mail message to parse header and body fields to retrieve message content and generate metadata associated with the e-mail message.

Thread analyzer135is linked to the indexer130and the master index105. Thread analyzer135includes hardware and/or software elements that organize e-mail messages into one or more e-mail threads. An e-mail thread is a series or sequence of one or more e-mail messages that form a logical “discussion” or “communication.” Some examples of e-mail messages within an e-mail thread are e-mail messages related by sender address, recipient address, topic, and time. Another example of e-mail messages within an e-mail thread are e-mail messages with forwarding replies, CC-recipients, BCC-recipients, and the like. In this example, the thread analyzer135determines the position of an e-mail message in an e-mail thread in response to message content and metadata of the e-mail message.

Topic classifier140is linked to the master index105. Topic classifier140includes hardware and/or software elements that determine one or more topics or categories in response to e-mail message content and metadata. The topic classifier140may determine the topic of an e-mail message based on the subject header or in response to the content of the body of an e-mail message. The topic classifier140may also associate an e-mail message with a given topic, classifier, and/or category.

Analytics ETL module145is linked to the master index105. Analytics ETL module145includes hardware and/or software elements that provide an interface accessing content and metadata processed by the system100. In one example, the analytics ETL module145provides an interface for extracting data from the master index105and/or external data sources; an interface for transforming the data, which includes cleansing, aggregation, summarization, integration, as well as basic transformation; and an interface for loading the data into some form of data warehouse for further analysis and processing.

Directory interface150is linked to the master index105and the directory servers155. Directory interface150includes hardware and/or software elements that access information stored in a directory. A directory is any database of information associated with objects, such as users or computer hosts. In various embodiments, the directory servers155include one or more directory servers157running Active Directory by Microsoft Corporation of Redmond, Wash. In other embodiments, other types of directory servers and/or services may be used such as Lightweight Directory Access Protocol (LDAP) servers, Identity Management servers, and the like. In various embodiments, examples of information stored in the directory servers155include “organizational” or “corporate” data, such as department identifiers associated with a user or computer host, a group identifier associated with a user, a corporate or departmental title associated with a user, telephone and address information, and security information.

In operation of the electronic message processing system100, the MAPI module110retrieves e-mail messages from the e-mail servers115(e.g., from one of the mail servers117). For example, the system100may “crawl” the e-mail servers115requesting e-mail messages through the MAPI module110. The duplicate eliminator120filters redundant and/or duplicate e-mail messages received from the e-mail servers115.

The indexer130receives the e-mail messages from the duplicate eliminator120through the buffer manager125. The indexer130processes the e-mail messages to determine the contents of the e-mail messages and metadata associated with each e-mail message. The indexer130stores a full text index of the e-mail messages and the metadata in the master index105. For example, the indexer130stores sender and recipient information associated with an e-mail message in the e-mail tables160; the indexer130stores an inverted word list of the full text of the e-mail message in the e-mail full text index165; etc.

The thread analyzer135processes the contents of the e-mail messages and the metadata in the master index105to organize the e-mail messages into e-mail threads. In general, the thread analyzer135organizes the e-mail messages into e-mail threads that form a discussion or communication of a topic or concept. One example of operation of the thread analyzer135is described below with respect toFIGS. 9,10A, and10B. The topic classifier140processes the contents of the e-mail messages and the metadata in the master index105to determine topics or categories associated with the e-mail messages. The topic classifier140stores the categories or topics in the topics tables170, and stores a full text index of e-mail messages belonging to and/or associated with the same topic in the cluster full text index175.

The directory interface150retrieves directory or organizational information from the directory servers155(e.g., from one of the directory servers157) related to the e-mail messages. The indexer130or the thread analyzer135may use the organizational information during, processing, indexing, and/or threading of the e-mail message. In this example, the organizational data is stored in the participant tables190and the distribution list full text180.

A user or computer process connects to the analytics ETL module145to retrieve information associated with the e-mail messages processed by the system100. Advantageously, the electronic message processing system100provides a user or organization with access to e-mail messages, and other information, such as header information, message contents, message attributes, metadata, and the like, to assist in reporting requirements or gathering information for the purposes of electronic discovery. After “crawling” e-mail repositories (e.g., one of the mail servers117) to retrieve e-mail messages, the system100processes and indexes the retrieved e-mail messages and stores metadata related to the processed e-mail messages in the master index105. The system100allows the user or organization to search and query the processed e-mail messages and the metadata to quickly extract and process relevant information. The system100further provides threading and topic classification of e-mail messages to enhance the discovery and presentation of relevant information to the user or organization.

In various embodiments, after an initial crawl of a data or e-mail repository, such as the e-mail servers115, the system100may incrementally process newly arriving e-mail messages on a daily bases, an hourly basis, or the like. As described above, the new e-mail messages may be incorporated into the master index105.

FIG. 2is a block diagram of software components200for processing e-mail messages in one embodiment according to the present invention. Software components200include portal202, indexer204, crawler206, distributed services208, and administration interface210. Portal202is linked to the indexer204, which is linked to the crawler206. Distributed services208and administration interface210are linked to each of the portal202, the indexer204, and the crawler206.

Portal202includes software elements for accessing and presenting information provided by the indexer204. In this example, the portal202includes web applications212communicatively coupled to information gathering and presentation resources, such as a Java Server Page (JSP) module214, a query engine216, a query optimization module218, an analytics module220, and a domain templates module222.

Indexer204includes software elements for processing and storing e-mail messages. The indexer204includes metadata224, full text indices226, thread analysis228, group effects230, and topics232.

Crawler206includes software elements for retrieving e-mail messages from an e-mail repository. Some examples of an e-mail repository are an e-mail server (e.g., one of the mail servers117ofFIG. 1), a Post Office Protocol (POP) enabled computer server, an Internet Message Access Protocol (IMAP) enabled computer server, and files, such as PST files, UNIX style maildirs/mbox formats, and the like. In this example, the crawler206includes Reference Information Storage System (RISS) module234, Enterprise Vault Software (EV) module236, MAPI module238, PST module240, Directory Services (ADS) module242, and a Microsoft Exchange Server Mailbox Merge Wizard (ExMerge) module244.

FIG. 3is a block diagram of a computer system300in one embodiment according to the present invention. In this example, computer system300includes a monitor310, computer320, a keyboard330, a user input device340, one or more computer interfaces350, and the like. In the present embodiment, the user input device340is typically embodied as a computer mouse, a trackball, a track pad, a joystick, wireless remote, drawing tablet, voice command system, eye tracking system, and the like. The user input device340typically allows a user to select objects, icons, text and the like that appear on the monitor310via a command such as a click of a button or the like.

Embodiments of the computer interfaces350typically include an Ethernet card, a modem (telephone, satellite, cable, ISDN), (asynchronous) digital subscriber line (DSL) unit, FireWire interface, USB interface, and the like. For example, the computer interfaces350may be coupled to a computer network355, to a FireWire bus, or the like. In other embodiments, the computer interfaces350may be physically integrated on the motherboard of the computer320, may be a software program, such as soft DSL, or the like.

In various embodiments, the computer320typically includes familiar computer components such as a processor360, and memory storage devices, such as a random access memory (RAM)370, disk drives380, and system bus390interconnecting the above components.

The RAM370and disk drive380are examples of tangible media configured to store data such as embodiments of the present invention, including executable computer code, human readable code, or the like. Other types of tangible media include floppy disks, removable hard disks, optical storage media such as CD-ROMS, DVDs and bar codes, semiconductor memories such as flash memories, read-only-memories (ROMS), battery-backed volatile memories, networked storage devices, and the like.

In various embodiments, computer system300may also include software that enables communications over a network such as the HTTP, TCP/IP, RTP/RTSP protocols, and the like. In alternative embodiments of the present invention, other communications software and transfer protocols may also be used, for example IPX, UDP or the like.

It will be readily apparent to one of ordinary skill in the art that many other hardware and software configurations are suitable for use with the present invention. For example, the computer may be a desktop, portable, rack-mounted or tablet configuration. Additionally, the computer may be a series of networked computers. Further, the use of other micro processors are contemplated, such as Pentium™ or Core™ microprocessors from Intel; Sempron™ or Athlon64™ microprocessors from Advanced Micro Devices, Inc.; and the like. Further, other types of operating systems are contemplated, such as Windows®, WindowsXP®, WindowsNT®, or the like from Microsoft Corporation, Solaris from Sun Microsystems, LINUX, UNIX, and the like. In still other embodiments, the techniques described above may be implemented upon a chip or an auxiliary processing board (e.g. a programmable logic device or a graphics processor unit).

In operation, computer system300receives electronic messages, such as e-mail messages, from electronic messaging repositories. Computer system300processes an e-mail message to determine message attribute data associated with the e-mail messages. Message attribute data is information related to an attribute or content of an electronic message. Some examples of message attribute data are sender e-mail address or sender identifiers, recipient identifiers, names associated with sender/recipient identifiers, attachment data, in-line text, body content, routing information, header information, and the like. The message attribute data allows computer system300to provide users and organizations with access to message content, relationships between e-mail messages, topics, rankings, and the like.

FIG. 4is a block diagram of an exemplary e-mail message400. The e-mail message400can be any message transmitted over a communications network, such as the Internet. In one example, the e-mail message400is a message communicated using one of the protocols adapted for communication using the Transport Control Protocol/Internet Protocol (TCP/IP) suite of protocols used over the Internet, such as the Simple Mail Transfer Protocol (SMTP). The e-mail message400may be communicated by using dedicated messaging client, such as Outlook and the like, and a web browser, such as Mozilla Firefox and Microsoft Internet Explorer and the like using a web-mail interface.

E-mail message400includes e-mail header410and e-mail body420. In this example, e-mail header410generally includes message attribute data related to header information, such as routing information, spam/virus scanning information, a subject, a sender identifier (e.g., the originating or sending e-mail address), one or more recipient identifiers (e.g., To-recipients, CC-recipients, and BCC-recipients, and distribution list e-mail addresses), priority, and the like. As the e-mail message400travels to its destination, information about the path or network hosts through which the e-mail message400passed may be appended to the e-mail header410in the routing information.

E-mail header410may also contain information about the e-mail client from which the e-mail message400was sent. Additionally, the e-mail header410may include information related to the format or encoding used to communicate the e-mail body420.

The e-mail message400is typically encoded in ASCII (American Standard Code for Information Interchange) text. The e-mail message400includes message attribute data related to portions (e.g., headers, body, etc.) of the e-mail message400. In various embodiments, the e-mail body420includes non-text data, such as graphic images and sound files and the like, in-line with text and as attachments. Some examples of the contents of the e-mail body420are plain text, base-64 encoded text, an encoded binary file, a portion of an e-mail message, an attached Portable Document Format (PDF) file, an attached or in-line Microsoft Word document file, and the like.

In various embodiments, e-mail body420of the e-mail message400also includes a quoted message430. The quoted message430itself includes quoted message header440and quoted message body450. In general, quoted message430is a portion of an e-mail message or an entire e-mail message. Portions of e-mail messages are often included in-line with other text in the e-mail body420. For example, the e-mail message400may be a reply to an initial or earlier e-mail message that is included in the e-mail body420as the quoted message430. Entire or complete e-mail messages are often included in-line or as an attachment to the e-mail message400. In other embodiments, quoted message430may be a forwarded messages, etc.

Quoted message header430comprises information, such as sender and recipient identifiers, much like the e-mail header410. Often, the quoted message header430includes at least a sender identifier, one or more recipient identifiers, a subject, a timestamp, and the like. Quoted message body450may be plain text, html, encoded text, and the like. The quoted text body450also may include portions of other e-mail messages and attachments.

FIG. 5is a block diagram illustrating an exemplary processing flow of electronic messages in one embodiment according to the present invention. In crawler box505, computer system300retrieves e-mail messages from e-mail repositories, such as an e-mail server or a file containing e-mail messages, and sends the e-mail messages to a buffer manager. In buffer manager box510, computer system300buffers or otherwise manages production and consumption of the e-mail messages retrieved while computer system300is “crawling” the e-mail repositories. In e-mail provider box515, computer system300creates batches of e-mail messages. In this example, batching the e-mail messages allows computer system300to apply batch-processing techniques to message attribute data associated with a batch of e-mail messages. For example, computer system300may create batches of 10, 50, or 100 e-mail messages.

In duplicate eliminator box520, computer system300processes the e-mail messages in the e-mail message batches to determine duplicates or redundant e-mail messages. For example, a user A of the mail server117(FIG. 1) may have sent an e-mail message addressed to user B and to user C. When computer system300retrieves e-mail messages from mailboxes on the mail server117for users A, B, and C, user A's mailbox contains the e-mail message as sent to user B and user C. Additionally, both user B's and user C's mailbox contains the respective user's copy of the e-mail message as received from user A. In this example, computer system300receives possibly three copies of the e-mail message in the duplicate eliminator box520.

Computer system300determines which of the three copies of the e-mail message to further process. In one example, computer system300determines two MD5 checksums for each e-mail message to “identify” an e-mail message. A first strict MD5 checksum is computed to be unique and represents an exact match of a previously processed e-mail message. A second “relaxed” MD5 checksum is computer to be non-unique or semi-unique.

When computer system300receives a new e-mail, computer system300processes the new e-mail message (e.g., address normalization and cleansing) and computes a strict MD5 checksum for the new e-mail message and compares the strict MD5 checksum to previously computed strict MD5 checksums to determine whether the new e-mail message is unique. In one example of operation, computer system300computes the strict MD5 checksum in response to message attribute data associated with an e-mail message using the sender e-mail address or sender identifier, sorted To-recipient e-mail addresses or To-recipient identifiers, sent time, alpha-numeric contents of subject, and the body text (e.g., body text size, contents of the body text, etc.).

Computer system300then computes a relaxed MD5 checksum using a portion of the message attribute data used to compute the strict MD5 checksum. Other information not included in the e-mail message but associated with the message attribute data may be used to compute the strict and relaxed MD5 checksums. Other types of integrity, detection, and authenticity algorithms, such as cyclical redundancy checks (CRCs), hashes, and the like, may be used in addition to or in the alternative to the MD5 checksum.

In this example, if the strict MD5 checksum for the new e-mail message is different, computer system300computes a relaxed MD5 checksum for the new e-mail message and compares the relaxed MD5 checksum to previously computed relaxed MD5 checksums. If the relaxed MD5 checksum for the new e-mail message is different, then the new-e-mail address is not a duplicate. If the relaxed MD5 checksum for the new e-mail message is the same as one or more previously computed relaxed MD5 checksums, computer system300applies rules or policies to eliminate possible duplicate e-mail messages that may occur due to time differences, header processing, and the like, and also the addition of trailing content, such as disclaimers, names of attachment files, and the like.

In surface processor box525, computer system300processes the e-mail messages (e.g., to populate the master index105ofFIG. 1with information related to the message attribute data). Some examples of surface processing are whether text in a body of an e-mail message is text included in another e-mail message (e.g., as a response to the e-mail message), identity information of senders, and identity information of recipients. In attachment processor box530, computer system300processes the e-mail message for attachments. If an e-mail message includes an attachment, computer system300further processes the attachment in stellent processing box535. In this example, computer system300processes the attachment according to content management and searching solutions from Stellent, Inc. of Eden Prairie, Minn. In attachment full text index box540, computer system300stores an inverted index of the extracted text of an attachment, if any (e.g., in the master index105).

In e-mail processing box545, after attachment processing or if no attachment exists in an e-mail message, computer system300operates on the batch of e-mail messages to parse or extract further information associated with message attribute data from the e-mail messages. In NP extraction box550, for example, computer system300processes subject and body content of the e-mail messages, such as to extract noun phrases, and the like. Computer system300then normalizes the extracted noun phrases into a feature vector that represents topical information associated with the e-mail messages.

In batch committer box555, computer system300commits the processed e-mail messages in the batch to storage. In one example, computer system300populates the master index105with information parsed or indexed in the e-mail processor box545. In e-mail full text index box560of this example, computer system300stores a full text index of the e-mail messages (e.g., in the e-mail full text index165ofFIG. 1). In SQL tables box565, computer system300prepares Structured Query Language (SQL) tables allowing the e-mail messages and message attribute data associated with the e-mail messages in the batch to be searched using SQL statements.

In thread analyzer box570, computer system300processes the e-mail messages to determine e-mail threads in response to message attribute data of the e-mail messages. In thread full text index box575, computer system300stores a full text index of e-mail threads (e.g., in the master index105). Further operations of computer system300in the thread analyzer box570are described further with respect toFIGS. 8A,8B,9,10A, and10B.

FIG. 6is a block diagram illustrating an exemplary message sequence chart related to an e-mail thread. An e-mail thread is a series or sequence of one or more e-mail messages that form a logical “discussion” or “communication.” E-mail messages can be related by thread criteria, such as time, sender, topic, etc. An e-mail thread also can provide an indication of user interactions to an earlier or original e-mail message that initiated a discussion or communication formed by a series of e-mail messages. Typically, the e-mail that initiated the subsequent user interactions or communications is called a thread origin (e.g., e-mail message605).

Referring toFIG. 6, a thread criterion defines an initial time starting indicative of when an e-mail message605was sent. As a result, the e-mail thread includes e-mail messages, transmitted during a time interval, that satisfy another thread criterion. In this example, computer system300determines e-mail messages that satisfy the thread criterion are e-mail messages related to the e-mail message605or otherwise transmitted in response to the e-mail message605.

In this example, user (Sender) A composes e-mail message605to three users. The e-mail message605may be considered the origin of the e-mail thread illustrated inFIG. 6. User B receives e-mail message610as a carbon copy (CC) recipient. User C receives e-mail message615as a To-recipient. User D receives an e-mail message620as a CC-recipient.

In response to the e-mail message610, the user B composes an e-message to users A and D. The user A receives e-mail message625as a To-recipient, and the user D receives e-mail message630as a CC-recipient. The user B may have forwarded or replied to the e-mail message610such that the e-mail messages625and630included the body text of the e-mail message610(in other words the original e-mail message605). The e-mail messages625and630may also include the e-mail message610as an attachment, and include a similar subject as the e-mail message610.

Next in the e-mail thread ofFIG. 6, in response to the e-mail message615, the user C composes an e-mail message to user A. The user A receives e-mail message635as a To-recipient. Subsequently, again in response to the e-mail message615, the user C composes an e-mail to users A, B, and D. The user A receives e-mail message640as a To-recipient. The user B receives e-mail message645as a To-recipient. The user D receives e-mail message650as a CC-recipient.

After receiving the e-mail message640, the user A composes an e-mail message to users B, C, and D in response to the e-mail message625. The user B receives e-mail message655as a CC-recipient. The user C receives e-mail message660as a To-recipient. The user D receives e-mail message665as a CC-recipient.

Subsequently, in response to the e-mail message640, the user A composes an e-mail message to users B, C, and D. The user B receives e-mail message670as a CC-recipient. The user C receives e-mail message675as a To-recipient. The user D receives e-mail message680as a CC-recipient.

Advantageously, computer system300allows a user or organization to discover information in e-mail messages that relates to discussions or communications about specific topics. Computer system300organizes the information, such as e-mail messages, into a thread and generates one or more topics in response to message attribute data associated with e-mail messages. Computer system300allows the user or organization to analyze the information to drive better business performance and/or comply with regulatory requirements.

Furthermore, computer system300allows the users and organizations to analyze properties of e-mail (such as recipients, replies, forwards, subject header, etc.), and combine the properties with organizational or corporate data to derive discussions and communication patterns within an organization or corporation. Computer system300provides access to electronic messages and message attribute data associated with the electronic messages. This allows users and organizations to quickly extract, analyze, and report information.

Derived Electronic Messages

As a result of user interactions in response to an e-mail message, subsequent e-mail messages may include quoted text from prior e-mail messages or include prior e-mail messages as attachments. Computer system300(FIG. 3) allows users or organizations to retrieve transactional e-mail messages from local e-mail repositories. Transactional e-mail messages are electronic messages that are received from and/or stored on an e-mail server or in a file (e.g., one of the mail servers117ofFIG. 1). A transactional message may include quoted text or attachments.

In various embodiments, computer system300processes the transactional e-mail messages to determine derived e-mail messages. Derived e-mail messages are electronic messages sent by electronic messaging services, where the electronic messages are included within other electronic messages. As described with respect toFIG. 4, some examples of derived e-mail messages are quoted text in forwarded or replied to e-mail messages, and e-mail messages included as attachments. For example, a transactional e-mail message may include a derived e-mail message. A benefit provided by various embodiments is that computer system300allows users and organizations to capture information in derived e-mail messages that otherwise may not have been retrieved from the local e-mail repositories as transactional e-mail messages.

As the use of electronic messaging proliferates, e-mails are often received from outside of organizations that initiate discussions or communications within the organization. Computer system300provides the users or organizations the ability to determine from derived e-mail messages whether discussions or communication originated from outside the organization. Additionally, computer system300allows the users or organizations to track whether topic discussion left or went outside the organization during a series of e-mail messages and later returned to an internal discussion within the organization.

In general, a system for processing e-mail messages (e.g., computer system300ofFIG. 3) includes a processor and a communications interface. The communications interface receives, from an e-mail repository, a transactional e-mail message comprising message attribute data. The processor is coupled to the communications interface. As described above, the processor places the transactional e-mail message in an e-mail thread in response to the message attribute data of the transaction e-mail message. The processor then determines whether there is a derived e-mail message included in the transactional e-mail message. For example, if a derived e-mail messages such as a reply or forwarded message, is included in the transactional e-mail message, the processor determines derived message attribute data of the derived e-mail message. The processor then places the derived e-mail message in the e-mail thread in response to the derived message attribute data of the derived e-mail message.

FIG. 7is a flowchart for processing e-mail messages to determine derived e-mail messages in one embodiment according to the present invention.FIG. 7begins in step700. In step705, computer system300(FIG. 3) receives a transactional e-mail message from an e-mail repository. A transactional e-mail message is an e-mail message directly retrieved from an e-mail message repository, such as an e-mail server or an e-mail storage file (e.g., a PST file), as opposed to a derived e-mail message which generally is determined from a transactional e-mail message.

In step710, computer system300determines message attribute data of the transactional e-mail message. Some examples of message attribute data are message content body, quoted text sections, attachments, signature sections, and message header information—such as a sender identifier, one or more recipient identifiers, the number of recipients, routing information, a subject line, a time stamp, and the like. In step715, computer system300determines an e-mail rank associated with the transactional e-mail message. An e-mail rank is any quantitative value, symbol, or indicator associated with an e-mail message that is used to provide an indication of qualitative value, relevance, standing, degree, or position of the e-mail message.

In this example, computer system300determines a numerical value in response to the message attribute data for the e-mail rank associated with the transactional e-mail message. Computer system300may also assign the transactional e-mail message 3 or 4 stars out of 5 stars. Additionally, computer system300may also use external sources of information to determine the e-mail rank of e-mail messages. One exemplary method of determining an e-mail rank associated with e-mail messages is described with respect toFIGS. 8A and 8B.

In step720, computer system300places the transactional e-mail message in an e-mail thread in response to the message attribute data. In step725, computer system300determines whether a derived e-mail message is included in the transactional e-mail message. The derived e-mail message may be included in the transactional e-mail message as quoted text and as an attachment.

In step730, if a derived e-mail message does not exist or is not included in the transactional e-mail message, the flowchart ends in step750. Alternatively, if a derived e-mail message does exist or is included in the transactional e-mail message, the flowchart continues in step735.

In step735, computer system300determines derived message attribute data of the derived e-mail message. Some examples of derived message attributed data are a relationship with the transaction e-mail message (e.g., in-line, attached, forwarded, replied, etc.), derived message content body, quoted text sections, attachments, signature sections, and derived message header information—such as a sender identifier, one or more recipient identifiers, the number of recipients, routing information, a subject line, a time stamp, and the like.

In step740, computer system300determines an e-mail rank associated with the derived e-mail message. In this example, computer system300determines the e-mail rank of the derived e-mail message in response to the derived message attribute data and the e-mail rank of the transactional e-mail message. In step745, computer system300places the derived e-mail message in the e-mail thread, along with the transactional e-mail message, in response to the derived e-mail message data.FIG. 7ends in step750.

Ranking Electronic Messages

In various embodiments, computer system300processes e-mail messages (e.g., transactional e-mail messages and derived e-mail messages) to determine an e-mail rank associated with the e-mail message. A benefit provided by various embodiments is that computer system300allows users and organizations to sort, analyze, and process captured information in transactional and derived e-mail messages in response to e-mail ranks.

In general, a system (e.g., computer system300ofFIG. 3) for ranking electronic messages includes a processor. The processor receives an e-mail message and determines a sender identifier associated with the e-mail message. The processor may also determine message attribute data in response to the e-mail message. The processor then determines an e-mail rank associated with the e-mail message in response to the sender identifier. The processor may determine the e-mail rank based on the message attribute data.

FIG. 8AandFIG. 8Bare a flowchart for determining an e-mail rank associated with an e-mail message in one embodiment according to the present invention.FIG. 8Abegins in step800. In step805, computer system300receives message attribute data of the e-mail message. In this example, the e-mail message can be a transactional e-mail message or a derived e-mail message.

In step810, computer system300determines a sender identifier related to the e-mail message based on the message attribute data. Some examples of sender identifiers are Internet e-mail address (such as To, CC, and BCC), usernames, hostnames, last names, and first names. In step815, computer system300determines a sender value for the e-mail message in response to the sender identifier.

In step820, computer system300receives organizational data related to the sender identifier. For example, computer system300may determine that the sender identified is the CEO, CIO, CTO, President, and the like. In various embodiments, computer system300retrieves the organizational data from organizational or corporate directories, corporate organization charts, and the like. In step825, computer system300determines a sender weight for the e-mail message in response to the organizational data related to the sender identifier. In step830, computer system300determines a sender portion of the e-mail rank in response to the sender value and the sender weight.

In step835, computer system300determines a recipient identifier related to the e-mail message based on the message attribute data. In step840, computer system300determines a recipient value for the e-mail message in response to the recipient identifier.

Referring toFIG. 8B, in step845, computer system300receives organizational data related to the recipient identifier. In step850, computer system300determines a recipient weight for the e-mail message in response to the organizational data related to the recipient identifier. In step855, computer system300determines a recipient portion of the e-mail rank in response to the recipient value and the recipient weight.

In step860, if multiple recipients of the e-mail exist, the flowchart returns to step835to determine another recipient identifier. If no more recipient identifiers exist or recipient processing is otherwise terminated, the flowchart continues in step870.

In step870, computer system300determines a sender text value for the e-mail message based on text contributed by the sender. In one example, the entire e-mail message comprises original text contributed by the sender. In another example, the e-mail message comprises answers contributed by the sender and questions included in a previously received e-mail message. If no text is contributed, computer system300may determine the sender text value to be zero (0). For the more original text contributed, computer system300determines a larger sender text value.

In step875, computer system300calculates the e-mail rank for the e-mail message in response to the sender portion, the recipient portion of one or more recipients, and the sender text value. Computer system300maps or otherwise associates the e-mail rank to the e-mail message.FIG. 8Bends in step880.

In one embodiment, computer system300determines the e-mail message rank as a weighted average of a SenderValue, ToValue, and CCValue. For example, computer system300determines the e-mail rank (e.g., MessageRank) according to the following equation:

In this example, computer system300derives the SenderValue component using a weighted average of the sender's role (e.g., organizational role or corporate office) and the text contributed by the sender. Computer system300determines the value of the text contributed by the sender based on word frequency. Another example of determining e-mail rank is described in U.S. Provisional Application No. 60/761,500, filed Jan. 23, 2006 and entitled “E-Mail Threading, Ranking, Derivation and Topic Classification Methods and Apparatus.”

Electronic Message Threading

In various embodiments, computer system300processes e-mail messages (e.g., transactional e-mail messages and derived e-mail messages) to determine “discussions” or “communications.” These discussions or communications may be found in a series or sequence of e-mail messages. A benefit provided by various embodiments is that computer system300allows users and organizations to sort, analyze, and process captured information in transactional and derived e-mail messages into logical discussions or communications.

In general, a system (e.g., computer system300ofFIG. 3) for threading of electronic messages includes a processor. The processor receives an e-mail message and determines message attribute data in response to the e-mail message. The processor then determines the position of the e-mail in an e-mail thread in response to the message attribute data.

FIG. 9is a flowchart for processing e-mail messages for placement in an e-mail thread in one embodiment according to the present invention.FIG. 9begins in step900. In step910, computer system300receives an e-mail message. In step920, computer system300determines message attribute data of the e-mail message. In step930, computer system300processes the message attribute data to determine a location of the e-mail message in an e-mail thread.

In step940, computer system300determines whether the e-mail message is similar to an existing e-mail message in the e-mail thread. If the e-mail message is not similar to an existing e-mail message in the e-mail thread,FIG. 9ends in step980. Alternatively, if the e-mail message is similar to an existing e-mail message in the e-mail thread, the computer system300determines whether the existing e-mail message is a transactional e-mail message in step950. In this example, computer system300provides deference to transactional e-mail messages, as opposed to derived e-mail messages whose message texts may have been altered during a reply or forward operation.

In step960, computer system300marks the e-mail message as a duplicate. In step970, computer system300deletes the duplicate e-mail message.FIG. 9ends in step980.

FIG. 10AandFIG. 10Bare a flowchart for organizing an e-mail message, such as the e-mail message640from user C ofFIG. 6, in an e-mail thread in one embodiment according to the present invention.FIG. 10Abegins in step1000. In step1005, computer system300receives the e-mail message640(e.g., from one of the mail servers117ofFIG. 1). In step1010, computer system300determines message attribute data of the e-mail message640, such as sender identifier, recipient identifier, subject, timestamps, and the like.

In step1015, computer system300determines whether the subject of the e-mail message640(e.g., from the message attribute data) is substantially similar to the subject of an e-mail thread. If the subjects are not similar, in step1020, computer system300determines whether the e-mail message640includes quoted text from a chronologically earlier e-mail message in the e-mail thread (e.g., text from e-mail messages615). If the e-mail message640does not include quoted text, computer system300determines whether the e-mail message640is included as an attachment of an existing e-mail message in the e-mail thread (e.g., in e-mail messages670,675, or680) in step1025.

If the e-mail message640is not included as an attachment, in step1030, computer system300determines whether a relationship exists between a sender of the e-mail message640and a recipient of an existing e-mail message in the e-mail thread (e.g., with the e-mail message615,670,675, and680). If computer system300makes a negative determination in each of the steps1015,1020,1025, and1030, computer system300creates a new e-mail thread with the subject of the e-mail message640in step1035. If computer system300makes a positive determination in any of the steps1015,1020,1025, and1030, computer system300proceeds to determine the position of the e-mail message640within the corresponding e-mail thread in step1045.

Referring toFIG. 10B, in step1050, computer system300determines whether a portion of the e-mail message640is included in a chronologically later e-mail message in the e-mail thread, for example in the e-mail messages670,675, or680. If a positive determination is made, computer system300determines whether there is no quoted text or attachments (such as would indicate an earlier derived e-mail message) in the e-mail message640in step1055. If another positive determination is made, computer system300determines whether multiple existing e-mail messages in the e-mail thread refer to the e-mail message640in step1060.

If computer system300makes a positive determination in the steps1050,1055, and1060, computer system300marks the e-mail message640as an origin of the e-mail thread. In general, the origin of an e-mail thread is an e-mail message that initiated the sending of subsequent e-mail messages forming a logical discussion or conversation. Typically, the subsequent e-mail messages have similar subjects as the origin e-mail address or refer to the origin e-mail message. The subsequent e-mail messages may also include all or a portion of the original e-mail address as quoted text or as an attachment.

In step1070, computer system300places the e-mail message640in the e-mail thread in response to the message data. If the computer system makes a negative determination in the steps1050,1055, and1060, computer system300places the e-mail message640in the e-mail thread in response to the message attribute data. If the computer system makes a positive determination in the steps1050,1055, and1060, computer system300places the e-mail message as the origin of the e-mail thread.

In this example, computer system300places the e-mail message640chronologically before the e-mail messages670,675, and680. Computer system300identifies the relationships between the e-mail messages640,670,675, and680, such as between sender and recipient, quoted text, attachments, and the like. Computer system300places the e-mail message640chronologically after the e-mail message615. Computer system300identifies the relationships between the e-mail messages615and640.

In various embodiments, as computer system300incrementally receives e-mail messages, the e-mail message may not be received in chronological order, or any order for that matter. In response, computer system300may continuously “promote” or “demote” processed e-mail messages as the origin of an e-mail thread. Computer system300may continuously organize the e-mail thread in response to processed e-mail messages, altering relationships and updating the positions of e-mail messages in the thread in response to message attribute data of the e-mail messages.FIG. 10Bends in step1075.

Ordering of Electronic Message Threads

In various embodiments, computer system300processes e-mail threads (e.g., transactional e-mail messages and derived e-mail messages) to determine an ordering associated with the e-mail threads. A benefit provided by various embodiments is that computer system300allows users and organizations to sort, analyze, and process captured information in transactional and derived e-mail messages into e-mail threads that may be ordered based on different criteria, such as time, topic, rank, and relevance.

In general, a system (e.g., computer system300ofFIG. 3) for ranking electronic messages includes a processor. The processor receives a plurality of e-mail messages and determines a plurality of e-mail threads in response to the plurality of e-mail messages. The processor determines an e-mail rank associated with each e-mail message in the plurality of e-mail threads. The processor determines an e-mail rank associated with an e-mail message in response to a sender identifier related to the e-mail message.

The processor determines a thread rank for each e-mail thread in the plurality of e-mail threads. The processor determines a thread rank associated with an e-mail thread in response to e-mail ranks of each e-mail message associated with each respective e-mail thread. The processor then determines an ordering of the plurality of e-mail threads in response to the thread rank associated with each e-mail thread in the plurality of e-mail threads.

FIG. 11is a flowchart for ordering e-mail threads in one embodiment according to the present invention.FIG. 11beings in step1100. In step1110, computer system300receives a plurality of e-mail messages. In step1120, computer system300determines the e-mail rank associated with each e-mail message in the plurality of e-mail messages.

In step1130, computer system300determines e-mail threads in response to the plurality of e-mail messages. In step1140, computer system300determines a thread rank associated with each e-mail thread in response to e-mail ranks of each e-mail message associated with each respective e-mail thread. In one example, the thread rank is a weighted average of the e-mail ranks associated with the e-mail message in an e-mail thread.

In step1150, computer system300determines an ordering of the e-mail threads in response to the thread ranks of each e-mail thread. Computer system300then may display the ordering to a user or generate a report containing the ordering. The ordering of e-mail threads allows a user or organization to determine which communications or conversations embodied in e-mail threads are most active or most relevant to a topic or other search criteria.FIG. 11ends in step1160.

Advantageously, computer system300can display the ordering of the e-mail thread to a user. For example, computer system300can provide the user with an ordering of e-mail threads based on a search performed for discussions or communications related to organization trade secrets. In another example, computer system300displays an ordering of the most active or highly discussed topics or categories in an organization.

FIG. 12is a screenshot1200of an exemplary dashboard1205displaying information related to processing of e-mail messages in one embodiment according to the present invention. The dashboard1205includes a search box1210, a search submit button1215, an advanced search button1220, a time span interface1225, a personalized topic display portion1230, a group display portion1235, a current status display portion1240, a participants/topic display portion1245, a total content display portion1250, and a message/topic display portion1255.

In this example, the search box1210allows a user to enter search criteria and click the search submit button1215to search information processed by the system100(FIG. 1). The user may click the advanced search button1220to enter a dialog (not show) provided additional search function features. The retrieved search results may be displayed in the dashboard1205or in a new display window. Additionally, the time span interface1225allows the user to enter day and time information to restrict the information displayed by the dashboard1205.

The personalized topic display portion1230depicts topics of interest to the user. The topic may be arranged in the personalized topic display portion1230according to topic alphabetical order, topic status, the number of discussions related to a particular topic, and the number of messages related to a particular topic, as illustrated. The group display portion1235depicts groups in an organization and the top or most active topics, discussions, and key individuals associated with a topic, as illustrated.

The current status display portion1240depicts the current status of the system100, such as the number of e-mail messages and attachments in the master index105, and the number of messages retrieved from an e-mail server, an archive, and a PST file, as illustrated. The participants/topic display portion1245depicts the number of participants for a particular topic. For example, the top five topics and the number of participants associated with each of the top five topics may be displayed by a pie chart. Each topic may be displayed using a different color, as illustrated.

The total content display portion1250depicts the number of e-mail messages, the number of attachments, the number of topics, the number of discussions, the number of individuals, the number of groups, and the number of annotations in the master index105, as illustrated. A unique or descriptive icon may represent each portion of the content in the master index. The message/topic display portion depicts the message count associated with a particular topic. In this example, the screenshot1200depicts a bar chart for the message count of five topics. In some embodiments, the dashboard1205includes links for printing or downloading information presented on the dashboard.

FIG. 13is a screenshot1300of an exemplary search dialog1310displaying information related to e-mail messages in one embodiment according to the present invention. The e-mail message search dialog1310includes a search box1320, a search button1330, and a search listing1340. The search box1320allows a user to enter search terms to search information processed by the system100. The search button1330submits the search terms to the e-mail processing system (e.g., the analytics ETL116).

The search listing1340displays the information retrieved from the master index105, as illustrated. In this example, the search listing1340displays whether an e-mail message includes an attachment, a time stamp, a sender identifier (“From”), a recipient identifier (“To”), a location or folder identifier, and a subject. In some embodiments, the search listing1340displays the e-mail messages sorted by a subject, a sender identifier, and/or an e-mail rank, as illustrated, as well as by other information desired by the user.

Electronic Message Search and Retrieval

In various embodiments, a query engine component (e.g., query engine216ofFIG. 2) performs an optimized retrieval of e-mail search hits and other assets of e-mails. Typically, in order to perform optimized retrieval of e-mail and other assets associated with e-mails, e-mail documents are indexed first using crawler and indexer components as discussed with respect toFIGS. 1 and 2. The crawler acquires raw e-mails from e-mail repositories, such as Microsoft Exchange, using a communication protocol such as Microsoft Exchange MAPI, or Internet RFC 2822 e-mail message format.

In some embodiments, an e-mail index (e.g., master index105ofFIG. 1) is created using the crawler and indexer components and stored in two forms: a full-text index containing searchable content organized in a way that helps in fast retrieval (e.g., e-mail full-text index165ofFIG. 1) and a set of relational tables containing e-mail meta-data and search information (e.g., e-mail tables160ofFIG. 1). The query engine component enables efficient retrieval of relevant search results from the e-mail index using one or a combination of the full-text index and the set of relational tables.

FIG. 14is a flowchart of a method for e-mail searching and retrieval in one embodiment according to the present invention. The processing depicted inFIG. 14may be performed by software modules (e.g., instructions or code) executed by a processor of a computer system, by hardware modules of the computer system, or combinations thereof.FIG. 14begins in step1400.

In step1410, computer system300receives input indicative of a concept of interest. For example, a searcher may input a name, an e-mail address, a topic, a keyword, and the like. The input may include natural language forms, structured language queries, Boolean logic, wildcards, and the like.

In step1420, computer system300determines a query plan based on the input. For example, computer system300may determine which databases to search (e.g., e-mail tables160, full-text index165, etc.). In another example, computer system300may determine when to present initial results to the searcher, and the relevancy of those initial results.

In step1430, computer system300determines information related to one or more e-mails in response to the query plan as relevant to the concept of interest. Computer system300may retrieve the entire contents on e-mail documents, a portion of an e-mail documents, attachments, quoted-text, header information, and the like.

In step1440, computer system300outputs the determined information related to the one or more e-mails as relevant to the concept of interest. For example, computer system300may display the results to the search using a graphical user interface. Computer system300may present the information to another computer process, such as in XML format, for further processing. In some embodiments, computer system300outputs a portion of the information for nearly instant display to a searcher, while continuing or updating the information in the background.FIG. 14ends in step1450.

FIG. 15is a block diagram illustrating e-mail search and retrieval in one embodiment according to the present invention. In this example, a set of e-mail database tables (e.g., e-mail tables160ofFIG. 1) track various properties of e-mails, documents, attachments, e-mail senders, recipients, e-mail domains, departments, and the like. Indexer130ofFIG. 1analyzes the content portion of an e-mail and constructs an index (e.g., e-mail full-text index165ofFIG. 1). As discussed above, one of the first steps in content analysis is called “surface analysis,” which identifies various regions of e-mail documents.

FIG. 16is a block diagram of contents of an e-mail message1600in one embodiment according to the present invention. In this example, the content portion (e.g., the non-header portion) e-mail document1600includes a new text portion1610, a derived e-mail portion1620, a disclaimer portion1630, and an attachment portion1640. Derived e-mail portion1620may include text quoted from another e-mail document, forwarded from another e-mail document, and reply-to text. Derived e-mail portion1620may include a content portion of another e-mail document1650, with new text, quoted-text, forward text, reply-to text, disclaimers, attachments, and the like. The following are some examples of regions of an e-mail that may be identified:

RegionDescriptionFromListThe list of e-mail addresses from which an e-mail is sent.ToListThe list of e-mail addresses to which an e-mail is sent.CcListThe list of e-mail addresses from which an e-mail is carbon-copied.BccListThe list of e-mail addresses from which an e-mail is blind-carbon-copied.SentDateTimeTime when an e-mail was sent.ImportanceImportance flags on e-mail.SubjectSubject of an e-mail, with its tokens stemmed to remove wordinflections and endings.Unstemmed SubjectSubject of an e-mail, with its tokens in raw form.E-mailScopeInternal to a domain or external to a domain.NewTextThe New Text content of an e-mail, with its tokens stemmed toremove word inflections and endings.UnstemmedNewTextThe New Text of an e-mail in raw form.AttachmentContents of an attachment, with its tokens stemmed to removeword inflections and endings.UnstemmedAttachmentContents of an attachment in raw form.QuotedTextThe Quoted or Included text, with its tokens stemmed to removeword inflections and endings.UnstemmedQuotedTextThe Quoted or Included text in raw form.

In various embodiments, for each of the regions above, the full-text index contains a list of all tokenized words. The full-text index may also include a list of each document containing a word, along with the location information for each word. This list may be an inverted word index.

Referring again toFIG. 15, in this example, a query1505is received from a searcher. In general, a searcher may be a user, administrator, or other computer process. In various embodiments, when a search request is processed (e.g., query1505), the search request is converted into tokens. For example, search request containing the phrase “Pirates of the Caribbean” may be tokenized into terms: “pirate” and “Caribbean.” The following are some exemplary forms of search for the above phrase:

Search TypeModeDescriptionAll-Of-The-UnstemmedContain all tokenized terms except for commonWordswords such as “of” and “the”, with each term not stemmed.All-Of-The-StemmedRemove inflections and word endings and searchWordsfor all of the words, except for common wordssuch as “of” and “the”.Any-Of-UnstemmedContain any of the tokenized terms, with eachThe-Wordsterm not stemmed, except for common wordssuch as “of” and “the”.Any-Of-StemmedRemove inflections and word endings and searchThe-Wordsfor any of the words, except for common wordssuch as “of” and “the”.None-Of-UnstemmedContain none of the tokenized terms, with eachThe-Wordsterm not stemmed, except for common wordssuch as “of” and “the”.None-Of-StemmedRemove inflections and word endings and searchThe-Wordsfor e-mails that contain none of the words.PhraseUnstemmedMatch exact phrase, including commonlyoccurring words such as “of” and “the”. Theorder of the words in the phrase is important.

In step1510, the tokens are searched against a full-text search (e.g., full-text index165ofFIG. 1). In step1520, a set of search hits is retrieved from the full-text search. In various embodiments, in addition to the token based search retrieval of the full-text index, in step1515, results from relational queries (such as a SQL query) are combined with results from the full-text search hits in step1515. For certain types of queries, computer system300may determine that using a relational query is more suitable for determining search hits in step1520. The following are certain exemplary parameters that may be used for the determination:

ItemReasonDateFor queries that involve a Date Range (E-mail Sent-Time), itRangemay not be possible to construct a searchable full-text index.Relational databases provide a well-established SQL Queryinterface to search date ranges.AccessAccess Control is usually a post-indexing determinant task.ControlFull-text indexes typically provide Insert-Only methods,whereas SQL can provide update capabilities.GroupGroups are collections of individuals in an organization,Member-reflecting the organizational and communication groups toshipwhich individuals belong. Group membership involvesdetermining e-mail senders and recipients, and determininggroups to which they belong. A single e-mail can belong tomultiple groups. The nature of group membership definition isthat it is very dynamic, and subject to change after initialrepresentation/definition. This tends toward the use of arelational database with SQL Queries to generate potentialsearch results.

In step1525, relevance is determined. In general, when a search is performed against a large body of e-mails, very large number of results will be produced. These results need to be ordered, so that the most relevant e-mails are returned. In step1530, the results may be ordered based on attributes and criteria, such as messages1532, attachments1534, tags1456, topics1538, threads1540, and recipients1542.

In various embodiments, relevance may be determined by a scoring formula that involves the attributes, such as term frequency, the field boost, the inverse document frequency, and field length normalization factors, and the like. In various embodiments, term frequency is the number of times a search term appears in a particular e-mail document. The more times a search term appears, the greater the importance of that e-mail, relative to other e-mails. Inverse document frequency is the number of documents a particular term is found in. The more documents a term is found in, the less important that term is in selecting the e-mail as an important result. Field length normalization indicates that if a term appears in a field that contains many other terms, the importance of the term is lower. If a field contains only a small number of terms, and the search term is one of them, that field contributes more to the relevance.

In some embodiments, a relevance score is computed for each e-mail according to the following formula:

For a collection of documents D, a specific document d, and a set of tokens within a region, q containing tiindividual terms, the score for the document is:

coordq,d=q⋂dq
and

The above formulas are based on the Lucene Search Engine query evaluation.

Field boosts indicate, that since an e-mail is broken into several fields, it is important to recognize that some fields are more important than others. The e-mail fields are assigned different field boosts to incorporate such factors. In one example, a search engine assigns the following field boost values:

Boosts for regions may be applied in the Query Scoring formula as follows. Each region's terms are weighted using the boost for the region. For each region rεR, the weights for that region are represented by:
wt,r=weightt,r*boostt,r
The normalization factor is also altered in the following way:
normd,r=normd*boostr
Given the altered weights and normalization factors, the complete scoring is computed per region, and then aggregated into a relevance score:

In step1545, the ordered and relevant results are collected. In step1550, the results are presented to the user or output to an application. In one example, in step1555, a summary of the results is presented to the user. The summary may be presented in a format allowing the user to drill-down or click down on the summary to obtain more detailed information. In step1560, detailed hits are displayed. In step1565, a navigation histogram is displayed. One example of a navigation histogram is described further with respect toFIG. 19.

In various embodiments, the relational tables are organized around determining a set of e-mails and documents that match a set of complex SQL Queries. A main relational table may track all e-mails that have been identified as e-mail documents. A common key (join key) between the full-text tables and the relational database tables may be a unique document id (e.g., EMAILDOCID) associated with each e-mail (as well as attachment), and a full-text index document number (EMAILFTID). Both EMAILDOCID and EMAILFTID are stored in both the SQL database. The full-text index may also store a DOCID associated with each e-mail identified as an e-mail document.

In some embodiments, computer system300determines a query plan that combines searching both the full-text index and the relational database tables. In one example, there are the following three execution options for executing a combined query: 1) Execute the database query first and feed the results (FTIDs) into the full-text query (option here after referred to as DtoF); 2) Execute the full-text query and feed the results into the database query (FtoD); and 3) Execute both the queries independently and combine the two result sets (using hash-based join algorithm) in the Query Engine layer (DjoinF).

Computer system300may determine which execution option to pursue in response to a cost-based heuristics. In various embodiments, a cost analysis is performed where the costs of executing the queries independently are assumed as follows:CD—Cost of executing the database query;CF—Cost of executing the full-text query.

Then, the costs associated with the three execution options above may be described as follows:CDtoF=CD+CF′, where CF′ is the new cost of executing the full-text query;CFtoD=CF+CD′, where CD′ is the new cost of executing the database query;CDjoinF=CD+CF+Cjoin, where Cjoinis the cost of joining the two results.

In one embodiments, the query execution cost is dominated by I/O costs, unless the database is small enough to be cached entirely in memory. Given this, option 1 or 2 may be cheaper than option 3, only if CF′ or CD′ costs are less than the original costs CFand CDrespectively. The new costs can be less, if passing the result of one query to another reduces the I/O cost of the second query.

FIG. 17is a block diagram illustrating filtering search results in one embodiment according to the present invention. In regard to CDtoF, passing the FTIDs resulting from the database query execution to the full-text engine can be achieved by constructing a filter (bitmap) for those documents. This option may be used in cases where the number of result rows from the database query is small (e.g., less than 10,000) and the expected number of hits from the full-text query is relatively large.

In step1710, a search query is separated into parts/components that are relevant for the relational database (e.g., SQL component), and another for the full-text index (Full-Text Query component). In step1720, the SQL component is processed, using several database table JOIN operations, with a final JOIN against the EmailDocument table for roles, participants, visibility filters, and the like. In step1730, a collection is yielded of EMAILDOCID and EMAILFTID in an e-mail document table.

In step1740, the EMAILFTIDs are then converted into a Bitmap. The bitmap is then supplied to the full-text engine as a Filter. In step1750, the full-text engine processes the Filter, plus the Full-Text Query component used in step1760. In step1770, a collection of search hits is yielded.

In regard to the CFtoD, feeding the DOCIDs resulting from the full-text query execution to the database query can be achieved by adding a “docid IN (d1, d2, . . . )” clause to the original database query. The modified database query will be more efficient than the original query, if the number of rows selected from the EmailDocument table in step1730is significantly reduced because of a new IN clause constraint.

FIG. 18is a block diagram illustrating tagging of e-mails in one embodiment according to the present invention. In this example, in step1810, a collection of e-mails are tagged using user-specified tag actions. A tag is any label, symbol, or identifier. As an example, the review process for reviewing large volumes of e-mails requires tagging e-mails with special tags, and then other searches for only those e-mails that contain these special tags.

In step1820, the tagging operation is stored in the form of bitmaps, where each position in the bitmap represents whether a particular e-mail or document has been tagged. Note that the same e-mail can be tagged in multiple independent tags, resulting in many Tag Bitmaps. In step1830, the Tag Query is processed to obtain Query Tag Bitmaps. In step1840, the bitmaps may be stored in the relational database in two tables T_BITMAP and T_BITMAPSEGMENT. At BitMap store time, the BitMap object and the segments may be stored in one transaction. In some embodiments, only those bitmap segments that contain a sequence of bits in either an ON or OFF state are stored, to conserve on space for bitmaps and the associated I/O load on bitmaps.

In step1850, the bitmap is then supplied to the full-text engine as a Filter. In step1860, the full-text engine processes the Filter, plus the Full-Text Query component used in step1870. In step1880, a collection of search hits is yielded.

FIG. 19is a screenshot1900illustrating a collection of search results in one embodiment according to the present invention. In general, the results of a search (e.g., the results of steps1770ofFIGS. 7 and 1880ofFIG. 18) is a collection of search results, plus a collection of histograms for each attribute of the result. The following are some attributes of a search result:

ItemReasonSender NameThe Sender of an e-mailRecipientThe Recipients of an e-mailSender GroupsThe organizational groups the sender belongsRecipient GroupsThe organizational groups the recipients belong toSender DomainThe e-mail domain of the senderRecipient DomainThe e-mail domain of the recipientsCustodianThe Owner/Source location from which an e-mail wasretrievedProject TagsThe various tags that were applied to the e-mail.

A histogram is a breakdown of the search results. For example, a histogram may be broken down into the above categories. Referring toFIG. 19, screenshot1900includes a project attribute1910, a status attribute1920, an important attribute1930, a sender domain attribute1940, a sender location attribute1950, a sender group attribute1960, and a sender name attribute1970.

For sender name attribute1970, the actual counts of the search results are displayed next the sender name, that contain this attribute. This allows the search results to be further filtered, using a guided navigation paradigm. For example, selecting an item narrows the results to only those search hits that pertain to the displayed histogram item.

FIG. 20is a block diagram illustrating a system2000for asynchronous query execution in one embodiment of the present invention. In this example, system2000includes a client2002, a searcher2004, a threadpool2006, a processor2008, a processor2010, a processor2012, a processor2014, a cache2016, a container2018, a container2020, a cache2022, a container2024, a container2026, a cache2028, a container2030, a cache2032, and a container2034.

In general, when very large number of results are retrieved, the search and results retrieval time can take significant processing time. Accordingly, useful partial search results may be initially presented, while the rest of the results are computed in the background. In various embodiments, the results are ranked, so that the search operation can determine relevant initial results and present them to the user, while additional further remaining results may be computed.

A large amount of detail summarizing ongoing search discoveries may be displayed (e.g., using a histogram as inFIG. 19) even while the initial results have been displayed and made available for use by client2002. Detail may be extended to include not only summary counts, but also other kinds of feedback including search status keywords, exceptional results, and the like. The level of detail and its multi-dimensional relationship to the search activity of client2002give a user a much greater sense of the value of the ongoing search activity than single-dimensional displays such as a search progress bar.

In one example of operation, search client2002sends the search parameters to searcher2004(e.g., computer system300ofFIG. 3). Searcher2004launches multiple threads using threadpool2006. In this example, each thread runs a processor (e.g., processors2008,2010,2012, and2014). Each processor is responsible for fetching a certain type or types of objects.

In some embodiments, the input to a processor may be either the search parameters or the output of other processors. The objects fetched by each processor are stored in caches, one for each type of the object. Each cache can have one or more containers associated with it. The containers can specify filter criteria when they attach with the caches. Based on these criteria, the cache sends those objects to the containers as it receives it.

In some embodiments, two object streams may be coming from independent streams. Each object can have a weight with which it is associated. It is possible that the same object is present in both streams, but with different weights. Given that both streams are already sorted on that weight, both streams may be merged, thereby eliminating duplicates, and dynamically merging object weights.

In one embodiment, when objects are inserted into the cache, those objects are tagged with meta-information. For example, many objects are derived from other objects, such as Type A becomes Type B becomes Type C. In this case, all source and target objects are tagged with these relationships. This allows the containers to apply filter criteria. For example, a container can ask for Type B objects that are derived from a given Type A object.

The consumer of the containers (e.g., client2002or another processor) can start fetching objects even when a search is ongoing. In some embodiments, client2002displays initial search results, and then submits a search progress request to system2000. For example, client2002may submit a search progress request to container2024, after which container2024returns search progress data blocks to client2002. The initial results may be displayed in a graphical user interface, where summary results are displayed in a right side pane of a dialog window, and detailed results are displayed in a left side pane of the dialog window.

Client2002updates presentation of search progress information, and repeats search progress requests until receiving an indication that the search is complete. In one embodiment, a differentiated display treatment indicates that the search is complete. Accordingly, client2002can be made to continuously poll an information server (e.g., container2024) for an arbitrarily complex status block, and unobtrusively display that block's contents to the user until the block reports that the results are “final.”

In various embodiments, system2000includes four modules: a search progress display template, a search progress data provider, a client script-based search progress processor, and a client-based progress request mechanism.

The search progress display template renders the display of search progress in a form that may be displayed on client2002, and subsequently, filled-in by the client search progress processor module. In one embodiment, the search progress display template is rendered in HTML using a Java ServerPage (.jsp). Identifiers in the form of ID attributes may be assigned to certain SPAN or DIV HTML elements designated as containers of progress information. The identifiers indicate which data is contained by each relevant SPAN or DIV. Some example identifiers are “messageCount,” “discussionCount,” and “topicCount.”

In various embodiments, the search progress data provider module includes a Java Servlet that is executed in response to a search progress request from client2002. The Servlet consists of Java code that outputs XML data containing cumulative results of the search. XML elements may be used to denote summary progress information corresponding to elements appearing in the Search Progress Display Template such as <messageCount>, <discussionCount>, and <topicCount>. These names may match or may simply be mapped from XML data block to template element by the search progress processor module.

In some embodiments, the client-based search progress processor module processes the requested data returned by the search progress data provider. In general, incoming XML requests are received, parsed, and inserted into the search progress display template. After inserting results, the client progress processor module may alter the display to indicate the search is complete, or issue another search progress request.

In one embodiment, the client-based search progress request mechanism module issues requests of various types to searcher2004. For example, requests may be issued as an XMLHttpRequest, a browser facility that is used to silently send the request to the server without interrupting or otherwise disturbing use of the current page. This facility, coupled with the XML data returned and the script-based incorporation of results into HTML pages, is sometimes referred to as AJAX technology, AJAX being an acronym for Asynchronous Javascript and XML.

The present invention can be implemented in the form of control logic in software or hardware or a combination of both. The control logic may be stored in an information storage medium as a plurality of instructions adapted to direct an information-processing device to perform a set of steps disclosed in embodiments of the present invention. Based on the disclosure and teachings provided herein, a person of ordinary skill in the art will appreciate other ways and/or methods to implement the present invention.