If we had dialogues with on-line books and other documents instead of merely reading them, imagine the benefits. A Dialogue With Documents system would respond to a user’s question or comment by presenting either the most apropos passages in the document, or meta-responses that elicit further user input to continue the dialogue. The intuitive appeal of such a system is supported by the fact that readers of on-line text already tend to scan and pick out passages rather than reading in a traditional sense (Nielsen 1999).
Whether a user consults a manual on repair of computers or automobiles, queries an encyclopedic work for specific facts, studies a work of philosophy or religion for guidance with existential questions, seeks answers within hundreds of web pages returned by a web search engine, or performs any of countless other tasks involving knowledge acquisition from documents, document dialogue systems could greatly benefit information users in the information rich on-line environment of the third millenium. Custom dialogues between users and documents would indeed be a useful and fascinating alternative to traditional ways of reading!
This problem is compelling as the basis of a research program. In addition to its intrinsic value and interest, it is open-ended and challenging enough to advance human knowledge. Yet it is also solvable to a practical extent. Consequently numerous user interfaces and keyword based query tools exist to search textual data --- yet these tools are currently limited, as regular users of library databases or web search engines can attest. Building on the proven value of existing systems ensures the pragmatic potential of the proposed research. Yet the widely recognized limitations of existing related methods makes further research both needed and interesting.
The Dialogue With Documents research program contributes both via its intrinsic interest and value, and also from its interaction with established fields, as we see in the following items.
· Human-Computer Interaction and Dialogues With Documents.
If passage retrieval is the heart of a Dialogue With Documents system, then the user interface is its soul. How information is presented is critical, and the HCI field has much to contribute. New window and window-like methods, such as Pad++ (Schneiderman), Elastic Windows (Kandogan and Schneiderman 1997), and Fisheye type views such as Document Lenses (Robertson and Mackinlay 1993) are important to consider in a Dialogue With Documents system.
Various paradigms and metaphors can be employed when presenting text and associated media (e.g. Golovchinsky and Chignell 1997). These form interesting motivational underpinnings for a Dialogue With Documents system. Apart from the obviously important hypertext, here are some other important ones (see http://engr.uark.edu/~djb/R/DWD/full/paradigms.html for a fuller discussion).
o The book metaphor (e.g. the Electronic Book '98 web site, http://www.nist.gov/ebook98) as presently conceived highlights the value of hand held devices of book size. It also suggests browsing documents whose lengths fall within a book-like range, and further suggests digital analogues of chapters, indexes, page numbers, and tables of contents.
o The citation metaphor suggests viewing the web in terms of the convenience of authoring, following, and transcluding links. In this view, links are citations in cyberspace.
o The composition paradigm (Golovchinsky and Chignell 1997) emphasizes that browsing can involve more than navigating for new things. It also can involve retaining particularly useful things on the screen while navigating.
o The index paradigm views browsing as finding lists of links and then trying some of them, as exemplified by browsing using web search engines.
o The interactivity paradigm emphasizes convenient hands-on interaction as a major element of the appeal of browsers.
o The direct multidisplay technique attempts to minimize the number of user interface actions by having one query lead to simultaneous presentation of several responses (Berghel 1999; Berghel, Berleant, Foy, and McGuire 1999; Berleant et al., in prep.).
o The query paradigm suggests basing a browsing system around query-and-response cycles. Indeed, Golovchinsky and Chignell (1993) argue that ``Queries-R-Links.''
The Dialogue With Documents metaphor implies use of the interactivity and query paradigms. The proposed Dialogue With Documents system will also draw on the composition paradigm and the direct multidisplay technique. The book metaphor applies in that dialogues with texts of roughly book length are currently envisioned.
User studies are also important in a research program of this type. To obtain user data, students will use the Dialogue With Documents system to access existing online course notes to study for exams and/or answer take home questions. User studies are discussed in more detail later.
· Information Retrieval, Related Areas and Dialogues With Documents.
Numerous techniques could contribute to a Dialogue With Documents system, and a Dialogue With Documents system could contribute in turn by providing a valuable application domain in which to assess those techniques.
Here is just a partial list of techniques, some of which we have used (Berghel, Berleant, Foy, & McGuire 1999; Berleant et al.; Soans 1998).
Keyword vectors, boolean expressions on keywords, weighted boolean expressions, cosine measures (with pivoting and without), automatic term weighting based on document and background frequencies, stemming, term truncation, thesaurus lookup and other lexicon lookups, sentence based retrieval, passage based retrieval (e.g. Callan 1994), paragraph based retrieval, word sense disambiguation based on context (e.g. Berleant 1995), part of speech tagging of passages, part of speech tagging of natural language queries, partial parsing (e.g. Yangarber and Grishman 1997), phrasal analysis of questions (Kupiec 1993), relevance feedback, n-gram based term comparisons (e.g. Damashek 1995), natural language query processing, automatic extract creation (Kupiec et al. 1995), question answering (e.g. Burke et al. 1997; Pilkington 1992; Richardson), flexible query answering (e.g. Andreasen et al. 1998), keychaining (Berghel, Berleant, Foy, & McGuire 1999), selective traversal (Salton et al. 1994), visualization of keyword collocations (Hearst 1995; Gershon and Eick 1995), automatic index generation (e.g. Symbolics 1985), automatic table of contents generation, and more.
For document dialogue, passages of one to several sentences, presented in a significant amount of context, seems reasonable. Such passages can be delimited using document structure (e.g. sentence or paragraph boundaries), arbitrary length criteria, and/or automatically detected topic or theme shifts. Delimiting can be done dynamically or in preprocessing. Kaszkiel and Zobel (1997) provide a useful review of this literature; see also Miller et al. (1998) and Salton et al. (1994, 1996). Section 2.4 discusses retrieval in the proposed Dialogue With Documents system further.
The remaining sections elaborate on system specifications (Section 2), system design strategy (Section 3), schedule and goals (Section 4), user studies (Section 5), and related work (Section 6).
This section addresses important specifications for a proposed general purpose document dialogue system. It covers output presentation, then navigation, then additional user interface considerations, and last but not least passage retrieval and other displayed content.
Several outputs are more likely than one output to contain something a user is interested in. Hence presenting several outputs at once lowers the percentage of unproductive queries. Furthermore, sometimes more than one of those outputs will be useful, thereby benefiting the user more than once from one retrieval action. For these reasons, presenting several outputs simultaneously reduces the cognitive overhead of the user interface by maximizing the number of useful outputs per user query.
Simultaneous presentation of more than one output will be referred to as “direct multidisplay,” as mentioned earlier. The prototypes demonstrated this feature (Figures 1 and 2). The Dialogue With Documents system will also employ direct multidisplay, using output screens containing a number of text subwindows. The specifications and design will be significantly more sophisticated than those of the prototypes (Potti 1996; Zhou 1997; Mu 1997), as described next and in the following section.
Figure 1. Screen shot from the original standalone prototype (Potti 1996).

Figure 2. Screen shot of a CGI based prototype written in Perl (Zhou 1997). Try
it at http://www.engr.uark.edu/~djb/Research/NLP/IC/MultiBrowser/versions/Zhou/infproto.html
.
o Split subwindow design (Figure 3). The subwindow consists of upper and lower halves. The lower half displays the retrieved passage and text following, and the upper half displays preceding text. The user can use the lower half to scroll through the document starting from the retrieved passage, yet return to the retrieved passage instantly by simply moving the lower half's scroll bar all the way back to its top with no ``hunting around'' needed. Similarly, the user can scroll through the text preceding the retrieved passage using the upper half, while retaining the retrieved passage in view in the lower half.

Figure 3. A split subwindow design.
· A user study is needed to determine whether the split subwindow design is significantly better (or worse) than the simpler traditional text box subwindows. In either case, scroll bars will enable subwindows to hold both the retrieved text passage and a significant amount of context. The context has been found to be important (Raymond and Fawcett 1990), probably because the author wrote the passage in context expressly to facilitate communication.
· The text display subwindows will be tiled (this was also the case in Elastic Windows). Tiling will make moving from one subwindow to another easier than for the common alternative of overlapping windows. Further, it seems desirable for the subwindow under the mouse cursor to expand, with the other subwindows shrinking to make room. When the mouse cursor is not over any subwindow, they should revert to all being the same size.
If exactly one query was possible, a system could respond to it without the user even having to ask --- the ultimate in low cognitive overhead interfacing. But if flexibility in querying is needed, there must be an expressive way to pose queries. While a flexible query scheme is essential in a Dialogue With Documents system, we also wish to allow very low cognitive overhead queries as well, because very low cognitive overhead interaction is desirable and the correspondingly limited query flexibility can still be extremely useful. Therefore:
Furthermore,
These will be useful when the current passage relates well to a user's concerns and the user wishes to see other related passages (this navigation method was not present in the prototypes). At other times, a very expressive query scheme is appropriate:
Screen history navigation is an important part of how people interact with web browsers (Catledge and Pitkow 1995; Tauscher and Greenberg 1997). Therefore:
· A screen history navigation facility will be part of the Dialogue With Documents system.
Users should be able to retain useful material on the screen while navigating to new material (as in the ``composition'' browsing paradigm, Elastic Windows, and sticky portals in Pad++). To have this retention capability in the Dialogue With Documents system, a user would be allowed to make a desired subwindow retain its presumably particularly interesting contents unchanged through subsequent query-response cycles which update the contents of other subwindows. This is a planned feature not in the prototypes.
Response time is a critical issue in interactive software (Miller 1968; Nielsen 1999). Yet the direct multidisplay requirement suggests that the Dialogue With Documents system should run a number of different text processing and presentation algorithms before all of the subwindows on a screen can display, since different algorithms could retrieve different kinds of relevant passages. However, running multiple algorithms takes time. The response time issue was not adressed in the prototypes. Although speed problems are projected to recede over time due to continuing exponential increases in hardware capabilities, measures must be taken to ensure that users will be unhindered by delays.
The Dialogue With Documents system will address the response time issue by displaying responses resulting from a query one at a time, as each becomes available, so that users will have some responses to view even though all may not yet have been determined. Furthermore, subwindow contents should remain visible until a replacement has been calculated, so that users can have a number of passages to read at all points in the query-response cycle. Finally, the choice and design of methods for preprocessing documents and retrieving passages should ensure that results can be displayed quickly enough.
Passage retrieval algorithms more sophisticated than the straightforward keyword and n-gram based algorithms used in the prototypes are planned to supplement those standard algorithms. This will involve one or more of the following: thesaurus based approximate queries, flexible query answering, and query based text extracts. Other significant features that are missing from the prototypes are also planned:
· Meta-dialogue. At least one subwindow for meta-dialogue will be present. Database tomography (Kostoff 1998, 1999, & accepted) and its application to helping users discover implicit relationships between concepts described in texts appears to be a good starting point for a meta-dialogue capability. To use this for meta-dialogue, two modifications of the technique as it currently is described in the literature (Kostoff, accepted) are needed; (1) using it on sets of passages (e.g. paragraphs) in a single text body instead of using it on sets of independent documents, and (2) partially automating the process of determining what implicit connections exist between concepts and themes described with key words or phrases. Using it on passages instead of documents is a fairly straightforward modification. Partially automating the discovery of implicit connections among concepts described in the document could be done by automatically deriving examples of potentially related concepts by analyzing keyword and key phrase frequencies and collocations, and prompting the user (a) to select which potential examples to examine more closely, and (b) to explicate the connections among concepts in the selected examples.
· The system will fill each subwindow with something reasonable so that no subwindows are left blank, as often happens with the prototypes.
· The system will put different material in each subwindow (the prototypes typically had different subwindows containing the same passage).
· One subwindow is planned to contain a clickable permuted index of content words in the document. Generating this index will also help preprocess the document in support of other passage retrieval algorithms.
· At least one subwindow will show a summarization of the document. One approach is automatic outline generation, a simple method of which is exemplified by the Netscape ``view source'' operation. This operation displays HTML source in a format that tends to be vertically compressed and horizontally stretched. A more sophisticated approach is query-sensitive summarization. A locally developed example of that is keychaining. Another approach is described by Salton et al. (1996).
The specifications constraints of this section could be realized by various design strategies, and it is important to choose an optimal one. Such a design strategy is developed next.
Design strategies tested with prototype implementations were a standalone (non-networked) design (Figure 1), a web client design, and a CGI based design (Figure 2). An applet-based design in which the server serves a large applet containing the Dialogue With Documents system is untried but intriguing, and may become feasible at some point as hardware and networks continue their exponential increases in speed. For the Dialogue With Documents system, an improved design strategy is proposed that is both concrete and doable, is capable of supporting a long term research program, and satisfies the following additional constraints and considerations:
· It should be runnable over the web using a standard web browser from either Netscape, Microsoft, or both. This facilitates access to the system by eliminating the need for users to download and install it.
· A modified WWW server should provide the documents. This server could serve either documents at its own site, or documents from remote sites that it would obtain using HTTP. This maximizes the selection of documents that are available for dialogues.
· The design approach must be flexible enough to accomodate long term system development needs of the research program, which cannot be fully known very many years in advance. Therefore an architectural strategy of incorporating reusable software components will be employed, to enable follow-on research to avoid ground up system reimplementations. (The reusable components approach was also employed by the related system Lector).
One prototype is runnable from web browsers and modified a standard server using Perl based CGI programs (Figure 2). For speed of execution, we plan to implement the Dialogue With Documents system initially as a fastCGI program in C, and then if it seems warranted, port it to an Apache module. Since both the fastCGI and Apache module strategies can retain state from one user query to the next, they will allow a document to be stored in memory in a preprocessed form that supports fast query processing. (The prototypes reprocessed the document for each query, causing excessively slow response times). An Apache server module is a block of code compiled into the Apache server that communicates with it via Apache's programmer API. We are already familiar with Apache modules. Any remaining speed problems should recede at a reasonable rate due to continuing exponential increases in digital hardware capabilities.
Here are some design guidelines for specific student projects.
The basic schedule for construction of a Dialogue With Documents system is shown in Figure 4. In more detail, the basic implementation produced in year 1 will use keyword and n-gram based retrieval algorithms of the type that we have previously used in the prototypes. The permuted index subwindow is also planned for year 1. Year 1 will additionally include determination of the feasibility of flexible query answering and other advanced techniques for passage retrieval in a Dialogue With Documents context. Antonio Badia will investigate the use of flexible query answering. His investigation will also set the stage for potential continued collaboration in subsequent years.
Figure 4. Three year time line for the Dialogue With Documents research
program.
Year 2 will involve implementation of at least one advanced passage retrieval and presentation algorithm, such as flexible query answering, thesaurus based approaches, automatic outlining and abstracting, or document visualization and exploration. Year 2 will also involve interface related user studies. Year 2 will additionally include design of the meta-dialogue facility.
Year 3 will involve implementation of the meta-dialogue capability, user studies related to passage retrieval algorithms, and plans for the next generation of work on document dialogue.
Many opportunities will be available to unfunded graduate students, undergraduate students via summer employment, and undergraduate capstone course students. Such opportunities will include investigating and implementing text processing algorithms, alternative implementations of various system components, and technical support for user studies.
Previous text processing related projects offered by the PI have been popular with graduate students. The PI plans to update his text processing course to include more web programming, and to develop a new course on human-computer interaction. These courses will prepare students interested in human-computer interaction, web programming, text processing, and the Dialogue With Documents research program.
Over the long term, this research will form a foundation for continued exploration of the varied and multidisciplinary issues on the trajectory to society's acceptance of interactive document dialogue.
User studies will contribute to knowledge about document dialogue, as well as provide results of more general interest.
To obtain data from the Dialogue With Documents system for user studies, students will be encouraged to use the Dialogue With Documents system to study pre-existing course notes while preparing for exams or answering assigned questions. Log files can easily record relevant information about user actions. Extensive course notes for the PI's Data Structures course are already in use in lieu of a commercially published textbook, and the PI will be assigned to teach the course as needed to obtain research data. In addition, on-line lecture notes for the PI's courses on object oriented software and software engineering may also be used.
User studies will address the following questions.
· Is the split subwindow design (Section 2.1) better than the typical text boxes provided by languages such as Java and Visual Basic?
· For short passage retrieval, which retrieval algorithms are best and by how much? An early study was done by Noreault et al. (1981). Soans (1998) has developed a system to support further work (Figure 5). In this system, eighteen passage retrieval algorithms provide output, displayed in eighteen windows. To do this user study, the mapping of algorithms to window locations would be randomized to avoid confounding user preferences for retrieval algorithms with user preferences for window locations.
Users would rank the perceived value of the retrieved passages, thus providing data for studying their preferences for different algorithms.
· Screen history navigation is likely to be extremely useful in a Dialogue With Documents system. However a simplistic approach is likely to be suboptimal, as Tauscher and Greenberg have found ways to improve significantly upon the ``Back'' and ``Forward'' options found in common web browsers (Catledge & Pitkow 1995),(Tauscher & Greenberg 1997). A user study is needed to determine the importance of history navigation, and how it should be done in the context of document dialogue.
· Do users like using an interactive, direct multidisplay based Dialogue With Documents system? Once they know how to use it, will they choose to continue using it? What HCI bottlenecks need to be addressed in follow-on research?
This Dialogue With Documents research program relates to a variety of other research areas, including automatic abstracting, document retrieval, computer assisted instruction, electronic books, graphical text summarization, meta-dialogue systems, natural language processing, question answering, windowing strategies, virtual reality, document versioning systems, and others.
Some related work has been discussed earlier in the context of specific issues. Here, other related work is reviewed. Space limitations prevent a full account of the richness and variety of other related work, so the following discussion is abridged. For the expanded version see OtherRelatedWork.html .
· Automatic Abstracting and Extracting. An extract may be an abstract or some other condensation of a document. Extracts could be very useful to present in one or more of the subwindows of a Dialogue With Documents system. Extraction work focusing on generating abstracts goes back to the 1950's (e.g. Luhn 1959) and includes work by Wyllys (e.g. 1967), Edmundson (e.g. 1969), and Paice (e.g. 1981). More recent work (Kupiec et al. 1995; Teufel and Moens 1997, 1998) has investigated how a document extraction system can automatically learn, from a training set of documents and corresponding extracts of them, how to pull out the most important sentences from a document and form them into a good extract.
Salton et al. (1996) address both abstracting (more generally, summarization) as well as the problem of generating extracts that support ``. . . a type of speed reading where an area of interest is specified, and the best text passages representing that area are chosen in response.'' This would be a type of document dialogue if it supported interactivity, as the dialogue metaphor is inherently interactive. However most extract producing systems are distinctly batch oriented, which is appropriate when the intent is to eliminate human processing, as to improve consistency and/or cost.
An exception to the low interactivity of most extraction systems is Cyberbrowser (Berghel, Berleant, Foy, & McGuire 1999). Cyberbrowser users interactively browse a document by using a point-and-click interface to conveniently specify a query, read a single extract consisting of sentences conforming to the query, and specify a new query to start a new query-response cycle. Cyberbrowser is interactive but lacks the important direct multidisplay attribute.
· Bibliographical Database Search Services. The many such services in modern libraries bear witness to the success of systems for locating interesting titles from among a large number of titles. It is important to compare this classic and successful IR application with the document dialogue task.
o One of the more unique and important bibliographic databases consists of the web and its search engines. Typical web search engines output multiple simultaneous responses to a query. However, this is not full direct multidisplay because these responses are not candidate answers to the query but rather annotated links to candidate answers. (As network bandwidths increase, and as electronic ink and other display technologies gradually make inexpensive displays with sizes of the order of a real desk top more feasible, search engines will increasingly find it feasible to employ full direct multidisplay.)
Web search engines generally apply a single algorithmic approach to process a query and identify a (sometimes exceedingly long) list of results. In contrast, the Dialogue With Documents system will use different algorithms in different subwindows, and provide summary and meta-dialogue capabilities. (Some web search engines are now providing primitive meta-dialogue capabilities, suggesting potential cross-fertilization between web search engines and document dialogue systems.)
· Electronic Books. Books form a mature information packaging and presentation technique that has existed for centuries. The book metaphor was important in the relatively early digital systems SuperBook (Egan et al. 1989), Book Emulator (Benest 1990), and Lector (Raymond 1992). An interesting electronic newspaper is described by Kamba et al. (1995).
The concept of electronic books is becoming increasingly visible, with a recent NIST sponsored workshop and a number of companies developing and commercializing different kinds of electronic books (Electronic Book '98; http://engr.uark.edu/~djb/R/DWD/full/paradigms.html).
The current emphasis in the electronic book field differs significantly from the goals of the Dialogue With Documents research program. Document dialogue is inherently software intensive. In contrast, the electronic book field currently emphasizes portable digital devices that can substitute for books. For example, one company has developed a device with two page-like screens connected by a hinged ``binding'' and a leather cover. A Dialogue With Documents system could certainly be used as core software in an electronic book. This would combine the convenience and portability of a hand held device with all of the cognitive advantages of a Dialogue With Documents system.
· Meta-dialogue. A good response to a user could be one that elicits further input, enabling user and system to cooperatively uncover useful passage(s). Varied approaches can be applied to this problem, and previous work goes all the way back to Weizenbaum's ELIZA system (1965). Some more recent techniques include meta-responses that detect and repair communication failures (e.g. Pilkington 1992), menu-based interaction (e.g. Richardson), and user modeling (used extensively in the Computer Assisted Instruction field). Finally, database tomography based discovery of connections between literatures appears well suited to extension to the case of cooperatively helping the user discover implicit knowledge within a single body of text, as described earlier in section 2.4.
· Question answering. There is an obvious parallel between posing a question to a question answering system and inputting a query to a Dialogue With Documents system. Well known modern question answering systems include FAQ finder (Burke et al. 1997), closely related systems (e.g. Kulyukin et al. 1998), and MURAX (Kupiec 1993). Systems such as FAQ finder and MURAX are intended for use with texts composed of diverse, fairly independent text segments (e.g. lists of different frequently asked questions such as FAQs and their answers, and sets of encyclopedia articles). In contrast, a Dialogue With Documents system is intended to support interaction with a single coherent book, or a set of related web pages with overlapping content. Nevertheless, the similarities in intent of the document dialogue and question answering tasks suggest the potential for significant cross-fertilization.
Each MultiBrowser used direct multidisplay and one or more simple sentence extraction algorithm based on keywords and/or n-grams, displaying retrieved sentences in separate subwindows on the screen. Each was developed in accordance with a different design strategy. The main design strategies strategies used are listed next along with their most salient characteristics.
o Virtual reality. The application of graphics techniques to help browse a large document or set of documents could be extended to the point where the document is used as the basis of a virtual reality that users could interact with as a vehicle for interacting with the document.
o Document versioning systems. A potentially useful and important utility would be one that periodically downloads a set of URLs, and archives each of them into a version repository of those URLs if it has changed since the last periodic download. The set could be defined as a simple list of URLs, as a site or partial path or, interestingly, as a search engine query. An appropriate browser for such a repository would provide dialogues with it that include the capability for the user to investigate such informative issues as what has changed in documents, and what URLs or other files have been added over time.
Let's consider the case of a URL set defined as those URLs returned by a particular search engine and query. Over time, URLs might appear and disappear from such a list, and a version repository of them would reflect that. This "alcove" of the Web would form a specialized digital library of interest to users for whom the particular query is relevant (consider e.g. a query like linux and graphics.) Note that the "alcove" would contain information not available from the Web, namely the changes in the Web presence of URLs conforming to the query over time.
As another example, someone might wish to create such a versioned repository based on a search engine query for documents containing their name. Such a user might be very interested in being able to interact with a repository browser in order to find out how their Web presence is changing over time.
As another example, a particular company or product type (e.g. "cable modems") could define the basis of a version repository, which could be interacted with to provide useful strategic information useful for analysts.
A research program focusing on document dialogue is timely --- even overdue. A Dialogue With Documents system will enable people to interact flexibly with documents, forming a valuable and interesting contrast to the standard reading approach of the past. This research program draws on and contributes to a number of established fields. These fields range from human-computer interaction to information retrieval, from electronic books to web browsers, from cognitive science to text processing algorithms, and more. The proposed research forms a well defined research project as well as a foundation for follow on advances in document dialogue. The proposed system is tractable, yet it also promises a fruitful long term future of useful and interesting problems. These problems are large and small, broad and narrow, open-ended and well-defined, long term and short term, and paradigmatic and technical. Document dialogue is the basis of an exciting, high potential research program.