The proliferation of electronic communication including computer mail, faxes, voice mail, and net news has led to a variety of disjoint applications and usage paradigms that forces users to deal with multiple different user interfaces and access related information arriving over the different communication media separately. To enable users to cope with the overload of information arriving over heterogeneous communication media, we have developed the Gold document handling system that allows users to access all of these forms of communication at once, or to intermix them. The Gold system provides users with an integrated way to send and recieve messages using different media, efficiently store the messages, retrieve the messages based on their contents, and to access a variety of other sources of useful information. At the center of the Gold document handling system is the Gold Text Indexing Engine (GTIE) that provides a full text index over the documents. The paper describes our implementation of GTIE and the concurrency control protocols to ensure consistency of the index in the presence of concurrent operations.

The emergence of the pen as the main interface device for personal digital assistants and pen-computers has made handwritten text, and more generally ink, a first-class object. As for any other type of data, the need of retrieval is a prevailing one. Retrieval of handwritten text is more difficult than that of conventional data since it is necessary to identify a handwritten word given slightly different variations in its shape. The current way of addressing this is by using handwriting recognition, which is prone to errors and limits the expressiveness of ink. Alternatively, one can retrieve from the database handwritten words that are similar to a query handwritten word using techniques borrowed from pattern and speech recognition. In particular, Hidden Markov Models (HMM) can be used as representatives of the handwritten words in the database. However, using HMM techniques to match the input against every item in the database (sequential searching) is unacceptably slow and does not scale up for large ink databases. In this paper, an indexing technique based on HMMs is proposed. The new index is a variation of the trie data structure that uses HMMs and a new search algorithm to provide approximate matching. Each node in the tree contains handwritten letters, where each letter is represented by an HMM. Branching in the trie is based on the ranking of matches given by the HMMs. The new search algorithm is parametrized so that it provides means for controlling the matching quality of the search process via a time-based budget. The index dramatically improves the search time in a database of handwritten words. Due to the variety of platforms for which this work is aimed, ranging from personal digital assistants to desktop computers, we implemented both main-memory and disk-based systems. The implementations are reported in this paper, along with performance results that show the practicality of the technique under a variety of conditions.