Persistent identi cation of entities in Personal Information Management (PIM) is necessary to enable stable, long-term references in archives and semantic applications. In the case of e-mails, the standard o ers Message-IDs (MID), which are widely deployed. However, stores do not use the MID but rather rely on a path, which is likely to change, to refer to e-mails and thus do not o er a stable identi cation. We show that MIDs are viable to identify and retrieve e-mails from an IMAP store in real-world scenarios. The presented concept can be integrated into any store, but we also o er a software solution that serves as an additional layer above the store and allows real-time access over MID. We propose a validation method to prove that the concept is working and some applications that are enabled by e-mail identi cation are sketched.
Sending e-mails has long replaced traditional letters, especially in the business
and research context. Being digital, e-mails can be easily stored and accessed
from di erent locations, building up large archives as part of the personal
information managed by each user. Although a central element of communication,
e-mails are still tied to special software, the Mail User Agent, instead of being
integrated into the overall work ow. Part of the reason is the lack of means to
reliably identify an e-mail message within an archive. While the Internet
Message Format{the de-facto e-mail standard{provides a globally unique Message-ID
(MID) and this identi er is present in each e-mail, it is not used for identi
cation [
Using a stable and persistent identi er for e-mails enables novel applications: Most archives are only accessible in a read-only mode, either due to technical reasons, e.g. WORM and similar media, or because of law regulations or policies. Therefore references cannot be adapted and identi ers need to be stable in the rst place. Semantic applications store outside references to e-mails. With today's stores, those references become stale if a message is moved. As a result, references to e-mails are either not available or must be enforced by a very tight integration, locking out other applications. A further bene t of stable identi ers is the intrinsic cross-referencing given through the fact that identical messages have the same identi er, even across archives, i.e. an e-mail has the same MID at the sender and the receiver. When researching e-mail archives, for example in legal cases or historic research, this e ect leads to higher e ciency.
We present a concept that enables referencing of e-mails by their MessageIDs. While this concept can be implemented into any software solution, we developed a prototype that works on top of IMAP-enabled stores, thus allowing additional functionality without changing running systems.
In the following, Related Work towards the topic is discussed. We then present the Message-ID Index, that adds MID-based references to an IMAP store, followed by a discussion of a validation method. Based on the availability of persistent identi cation, a set of enabled applications is sketched. The paper closes with a conclusion and the list of references. 2
In [
Tools for alternative access to an IMAP store already exist. For example,
[
The Internet Message Format, base for the e-mail format, is de ned in
RFC 5322 [
In [
To the authors' knowledge current standard-conforming IMAP server
implementations do not support an e cient query by Message-ID. The only known
solution that uses an e-mail's Message-ID for identi cation is the Gnowsis 3
semantic desktop [
2 SPARQL is an acronym for \SPARQL Protocol And RDF Query Language". See http://www.w3.org/TR/rdf-sparql-query/ for further reading. 3 http://www.semantic-web.at/de/gnowsis 3
E-Mail Identi cation. Even without semantic applications and archiving,
message identi cation is necessary for communication between a Mail User Agent
(MUA) and an e-mail store. In the following we concentrate on the Internet
Message Access Protocol (IMAP) as de ned in RFC 3501 [
A solution, however, is already embedded in each e-mail: The Internet
Message Format de ned in RFC 5322 [
Default operations of an IMAP store require fast access to folders and random access to messages within a folder, leading to a default hierarchy of message lists within a folder tree and the above identi cation scheme. While the MID is accessible from each single message, it does not help IMAP operations to make them available on a higher level, therefore this operation is not supported. There are IMAP implementations that use the Message-ID as le name for disk storage, but even then the folder tree, represented by directories, and the message lists apply.
To make the Message-ID quickly accessible, we propose an index on top of the IMAP structure that maps and updates Message-IDs to locations within the IMAP store. For an e cient solution in terms of runtime-e ciency, the index should be included in an IMAP server implementation. However, this would limit the use to a speci c system and requires e ort beyond the proof of concept, i.e. requires to adapt a software component that needs to be very reliable and can 4 A draft can be found at http://tools.ietf.org/html/draft-ietf-usefor-message-id-01 cause severe data loss on misbehavior. It is, however, feasible to integrate the index into future implementations or create a specialized version that leverages features of a speci c IMAP store.
Index Structure. The index is structured as follows: hMessage-IDi 7 ! hMessage-IDi 7 ! (hFolder URIi; hUIDi)unique (hreference typei; hMessage-IDi) with hreference typei 2 (Reference; In-Reply-To) and
In-Reply-To ! Reference Message-IDs are mapped to locations, which consist of a folder and the message's UID. The location pair is unique, i.e. there can be only one message at a speci c location. However, since copying messages is allowed, the same e-mail can be found at several locations. While the resolution from a Message-ID to a message is unambiguous, the mapping to a location is not. The rst line is su cient to resolve MIDs, but we decided to index reference elds as well to allow quick searches for related e-mails. Those references are In-Reply-To for answers to a speci c e-mail and Reference for a more generic reference, e.g. all e-mails from a discussion thread. The In-Reply-To eld implies the Reference eld and the reference is stored only once. Note that referenced e-mails are not necessarily available. For example, the user may have deleted the original e-mail before getting an answer, hence the In-Reply-To eld points to an e-mail that does not exist locally. Still the identi er is valid and might be resolvable by a thirdparty user, e.g. the sender who kept the e-mail he answered.
Challenges. The main challenges are to create and update the index. Creation requires to crawl all available messages in order to extract their MID and references and add them to the index. While this process takes a while, it is only necessary on setting up the index. Subsequent runs can ensure consistency to avoid missed updates, but are by design not necessary. Keeping the index up to date is the larger problem. As the user moves messages around, a number of location entries change: First the moved message now is at a di erent location and the index entry for this message must be updated. The UID value should not change often, but if the server decides to re-organize the folder structure5, all locations for this folder are invalid and must be retrieved again. For a responsive system, this re-indexing must be nished before the next Message-ID resolution.
The index implementation is very defensive against invalid entries. Therefore each location mapping is checked before it is returned to the caller. Checking is done by loading the message at the denoted location and comparing its MessageID with the stored value. If there is no match, the entry is discarded as invalid. When no valid entries can be found, there is either no e-mail corresponding to the Message-ID in the store or the message is in a folder pending for reindexing, in which case the resolution is stalled until the index is consistent 5 The UIDVALIDITY attribute allows to detect when UID values have become invalid. again. Regarding the latter case, there are two look-up contexts with di erent performance behavior: For resolution of a Message-ID to an e-mail, only one valid entry is needed, as all entries will point to the same content. However, for a list of all locations, the index must be consistent, otherwise the result may be incomplete. In a responsive user interface, this distinction should be made to avoid unnecessary long processing times.
Optimization. Having thorough checks on all mappings allows an optimization in the update process: When an e-mail is moved only the new location is stored. Since the same e-mail can be stored at di erent locations, a complete re-check of all locations would be necessary when a message is updated. This way, only the new entry must be added, which is a much faster operation. The other way around, uniqueness of locations allows to overwrite entries if the location mapping shows to a di erent Message-ID. These optimizations lead to faster indexing, but may result in an inconsistent index. Further performance tests are needed to decide whether these optimizations are necessary or if there is a faster solution.
Operations. Besides updates and consistency checks, which run automatically in the background, the index o ers two main operations to a user: First, a MessageID can be resolved either to its content, i.e. the complete message, or to the set of locations where the respective e-mail can be found. The main di erence between those resolutions is that nding an e-mail requires only one valid location while nding all locations needs a completely consistent index and therefore has to wait until all update operations are nished. However, as the main purpose of the index is the resolution of Message-IDs to e-mail content, the faster query method will most likely be used. Second, the index allows to retrieve references to a speci c e-mail, allowing to query preceding e-mails or related e-mails from an ongoing conversation. Note that this information come solely from the header elds within the message and are not inferred by further content analysis. If a Mail User Agent fails to set the respective elds, these references will not be available. However, apart from some Web-based mail systems, the data quality seems to be very good.
Architecture. Figure 1 shows the component diagram of the index. The Application has access to the underlying IMAP store for message content access and IMAP-related operations. Thus the default IMAP behavior is not hindered. To look up a Message-ID, the Application sends a Query to the Resolver, which in turn reads the mapping from an SQL DBMS. The result is checked against the IMAP store and, if valid, returned to the Application, otherwise invalidated in the DBMS. When the Resolver invalidates an entry, the Crawler is triggered, which in turn will read e-mails from a provided folder and update the respective mappings in the DBMS. The Observer is noti ed by the IMAP store if the message count in a folder changes, i.e. if messages are added, moved or removed, and triggers the Crawler to update the mappings. These noti cation can also IMAP Store Application DB Crawler Trigger Observer Resolver be received by the Application to update displays or trigger other applicationdependent reactions.
Runtime Environment. We implemented the index using Java6 and the Java Mail API 7 for generic IMAP access. For the IMAP store we are currently using the Courier MTA8. The index is stored in a MySQL9 DBMS.
Our deployment environment is quite distributed, i.e. IMAP store, DBMS, index and application run on di erent machines in di erent networks. The rst implementation could crawl 100.000 e-mails in about 2 hours. None of the machines showed substantial load, so most of the time goes into network communication. The current implementation uses parallelized crawling and bulk access to the database, so that with a rate of 50 e-mails per second the complete store can be crawled in half an hour.
Trigger 4
Due to time constraints, validation is not yet nished. However, we want to present our validation concept and rst results.
The goal of validation is to show that with the index, resolution of MessageIDs to e-mail locations within an IMAP store is 1) faster than without an index and 2) fast enough for user interaction. Additionally, we measure the \usefulness" of the index at the time of access, i.e. the hit/miss ratio.
We expect that any of the supported operations is faster with the index
than without. This follows from the rationale that a completely inconsistent or
empty index would crawl the IMAP store, which is about the same operation as
Message-ID lookup without an index. It is more interesting to see if the index is
fast enough for user interaction. Studies have shown that a user becomes
impatient after waiting two seconds for a response and annoyed after four seconds [
The readiness of the index can by evaluated by the ratio between hits, i.e. found entries, and misses in terms of invalid entries or entries that where not available due to re-indexing. It is important not to evaluate if entries could not be found, as they may come from Message-IDs for e-mails that were never available in the store. To count as a miss the entry should have been available in a perfect index. We expect misses on two occasions: Either a message has been added, but is not yet available in the index or messages have been removed 10 A quad-core Intel Atom platform. However, these values are only rst estimates as the test setup is not yet t for clean statistics. 11 IMAP bulk operations appear when a large number of messages are marked as read, as supported folder-wise by many clients, or a large number of messages is moved to another folder. from a folder, but re-indexing is still pending. The observer module is directly informed about e-mails that have been added to a folder, so new messages are available very quickly. However, it may take time to re-organize if the message numbers have changed. So in most cases not the moved, but the remaining messages are a ected. We expect that in a real scenario this lessens the number of misses, as the focused message is always readily available. However, re-indexing is relevant if an application frequently requests all storage locations. Furthermore we measure the time the index spends in an inconsistent state with pending reindexing. We observed only two scenarios where the index was not ready within one second after a change: 1) When emptying the trash, as each message is reported individually. 2) When marking a large number of messages read, which happens often for mailing list conversations. As observation and crawling are parallelized processes, other folders were not a ected and changes in these folders were available within one second. Therefore we could not observe a signi cant amount of cache misses.
A trivial approach towards a test scenario is a random distribution of operations (add, move, delete e-mails) and accessed e-mails. However, this pattern is far away from typical use cases. After their receipt only a small fraction of e-mails will ever be accessed again. As a consequence, there is a rather small set of \hot" e-mails a user might ask for, while the larger part will never be accessed. We suspect that those relatively new e-mails are in a distinct set of folders, like the INBOX or folders based on current project, while the rest has been moved to archive folders where they will most likely stay, so that for every (re)move operation only a very small part of messages is a ected. Therefore, a more realistic test-scenario will weight the access based on the age of an e-mail and on the folder. A third test scenario comes from user observation. Due to privacy reasons it is however very hard to get the respective data. Observing user behavior on e-mails relies on an index on the user's e-mail store and tracking of live usage data in a critical part of everyday communication. Therefore the test set will only be very small. While the last scenario is hard to acquire, we expect the best evaluation results since it matched actual access patterns best. 5
In this section we present three applications that are enabled by fast Message-ID resolution.
Related E-Mails. The rst application allows to view related messages in a Mail User Agent (MUA). While a tree view within a folder is often available, it is not possible to display a series of messages across folder boundaries, since related messages cannot be found fast enough. With the index, however, related messages can be easily retrieved and displayed in a tree alongside a selected message. This allows the user to easily navigate through a set of messages, regardless of the folder they are stored in. Since older messages are often moved to archive folders, this application allows the user to see all related messages even if they have already been archived. Misplaced E-Mails. Related e-mails are often stored in the same folder, e.g. based on a project or the communication partner. When a message is accidentally misplaced it is very hard to recover this message later on.12 A quick access to message references, provided by the second part of the index, allows to check if there are any stray messages. While it cannot be assumed how a user organizes e-mails, the amount of e-mails references that cross folder boundaries can be used to determine if a message may be in the wrong folder and where it should be. An appropriate noti cation can inform the user about the potential mishap and o er a quick solution.
External References. A third application directly uses the fact that Message-ID references can be easily resolved: Using an add-on, the browser can be enabled to understand the MID URI scheme. When confronted with a respective URI, the message will be looked up and displayed in the browser or opened directly in the MUA. As a result it is now possible to send links to e-mail messages, e.g. via e-mail, instant messenger or embedded into a document, regardless where they are stored. 6
Although e-mails play an important role in modern communication, there is no applicable way of referencing them. We have shown that a generic IMAP store can be enhanced so that the already existing Message-ID eld is viable for persistent, long-term identi cation and reference of e-mail messages in archives and semantic applications. We have also presented a set of applications that are enabled by fast e-mail identi cation via Message-ID.
The validation concept is ready and our next step will be a long-term
validation of the index on realistic scenarios to proof its usefulness. As mentioned
before, evaluation on real data is challenged by privacy issues. During further
research we will try to build a test set based on the ENRON e-mail dataset [
For the software itself, further implementation will include more statistics for the validation process and a better recoverability on link failures to the IMAP server.
Afterwards the applications sketched in the outlook will be implemented. 12 The best way to hide a book in a library is to put it into another shelf.