Introduction 1Problem area 1Research objective 2Related work 2Modeling entities and timelines 3Modeling entities 3Tractability assumptions 4Analyzing relationships 4Mapping abstract entities onto the physical display 5Visualization of simple entities 5Visualizing multiple entities and timelines 5Visualizing relationships 6Visualization techniques 6Authoring tools 7Summary 7Design and Implementation 7Evaluation 8Research contribution 9References 10Appendix A 12Appendix B 13Appendix C 14
A timeline is a graphical or textual display of events in chronological order and is an important technique for representation of large temporal data sets. Timelines have been used to represent the chronology of wars , automobiles , American Indians , the world history , science and technology , arts , and architecture to name a few. Many instances of timelines are not found in literature as they are created on an ad hoc basis by reporters, historians, graphic artists, researchers, and writers.
Most of the timelines in the literature are text based, in that the author/compiler lists the date and a brief description of the event that occurred during that time period, Timelines of Native American History  and Timelines of War  are some examples of this usage. Some timelines make use of an aesthetically pleasing visual presentation. For example the Smithsonian Timeline of the Ancient World  is a more visually attractive rendering of world history than its text-based counterparts. With the onset of information age, we are faced everyday with even larger and larger amount of information. We are expected to read, analyze, and assimilate this information quickly and accurately. A graphic timeline is a powerful tool, that along with interactive computer graphics techniques can ease the burden on the human cognitive system.
Much of the earlier computer related work on timelines has focused on visualization of a large amount of data on the computer screen . Until recently, such visualization was largely the domain of artistically talented computer experts, as even static graphics required expensive hardware and a very creative and innovative use of limited screen area. Recent advances in graphical user interface technology, however, have opened new opportunity for the rest of us to create visually appealing and informative timelines quickly and economically on desktop computers. Authors can now convey more information by presenting succinct representation of events to the readers. End users on the other hand, can use such timelines as a tool to browse large amount of temporal information.
Unprecedented growth of published material in print, and electronic form demands innovative techniques to allow effective use of this information. The timeline is an innovative information visualization and browsing paradigm in this respect. As yet, the use of advanced graphical user interfaces, to interact with timelines remains largely unexplored.
Recent literature on Human-Computer Interaction (HCI) has emphasized the use of timelines to visualize large bodies of information; e.g. work on interactive timelines at Bellcore . Most previous work has addressed use of timelines in specific domains  and consequently, there has been little work done to formalize timelines. A positive experimental evaluation of timelines by many researchers warrants a more formal study of the subject. Formal methods would enable us to apply the timeline concept to new applications in a domain independent manner and would help us create an application framework that is operating system independent.
Researchers recently have started looking into interactive timelines   as an interface to large bodies of information. They have highlighted many shortcomings of the current approaches, which open a plethora of opportunities for further research. Following are some of the issues that need further exploration.
The research proposed in this paper, encompasses the above three research areas. Issue # 1 deals with the logical modeling of timelines. This provides the theory in which the later ideas are grounded. Issue # 2 and 3 are visual presentation issues and warrant study of various GUI techniques in order to find effective presentation of information.
The study of timelines is a multi-disciplinary research area. Almost all fields of research measure some variable with respect to time. In this proposal, we are mainly interested in entities that constitute a timeline and various attributes of those entities. An entity has a specific duration during which it is said to be active. Many events are active at any point in time. Events are related to each other via temporal and causal relations. Allen  describes the thirteen possible temporal relations between any two events. When a set of events is compiled together, a timeline is formed. In everyday life all 2D and 3D plots involving time, Gant/Pert charts, resource schedules, calendars fall under the broad definition of timeline.
Karam  conducted a formal study of timelines for visualization of software events. He used state machine diagrams to model events and activities. A prototype timeline generator for X Windows was also implemented, although dependency and relationships were not addressed. Use of interactive timelines as system interfaces appears in , suggesting many novel visualization techniques. This work also addresses the issue of the lack of formalism in this area. Lifelines , deals with use of timelines for visualizing personal histories, but remains mostly an ad hoc effort for one domain.
Ahlberg et. al. , through empirical research, showed that comprehension of subject matter is better when students were provided graphical feedback of the query results. Timelines are one method of presenting the result of queries in graphical form . Xerox Corp. offers software called Visual Recall , which makes use of timelines to visualize personal and corporate data. It is excellent for visualization but offers little analytical capability. Use of Interval Charts for displaying complex relationships among variables is mentioned in . However, it only describes the data characteristics for graphical presentations.
Many Computer Aided Software Engineering (CASE) tools incorporate a graphical editor for visualizing entity-relationship diagrams e.g. Oracle*CASE and InfoModeler. These editors are able to produce graphics from a list of entities and the relationships between them. Such automatic generation of graphics for relationships is described in  and . However, without the use of an analytical engine and advanced computer-human interaction techniques, such methods remain largely unsuitable as interfaces to large complex information bases.
Various elements that make up a timeline e.g. events, people, nations will be identified. An entity is an abstract representation of all such elements. This paper proposes a model of timeline that is able to fully describe user definable entities and their attributes. Each entity in this model has a unique identifier that makes it distinct from other entities in the system. Each entity also has some attributes describing physical and behavioral aspects of the entity. The attributes are organized in two groups, namely required and optional attributes. At the time of defining a new entity type a user can define the attributes for each of the two categories, along with the acceptable ranges for each attribute domain.
We model an abstract timeline as a hierarchically organized set of entities. At the root of hierarchy is the timeline entity. Leaf nodes represent atomic entities. Entities at the non-leaf nodes are composite entities and are composed of one or more atomic entities or other composite entities. Each node except the root node can be child of one or more parents. In the graph terminology this structure is described as a forest abstract data type. The reader is referred to appendix A for further details.
To present a timeline, entities in the graph are ordered along one of the dimensions. A dimension is a user definable required attribute e.g. temporal, spatial, causal, "part-of", etc. After ordering, entities can be mapped to physical display for visualization and analyses.
When dealing with real-world cases one is faced with enormous number of entities and complex inter-relationship between them. Available information is often times approximate and incomplete, for example dates in historical narration--early eighties, about nineteenth century, etc. It is necessary to make some assumptions to make the problem tractable by mapping some qualitative values to quantitative values. These assumption will be made as new problems are encountered during modeling and implementation.
Relationships in this model are treated as one class of entity. Thus relationships have the same structure as regular objects in the model. This allows one to treat relationships as first class objects that can be manipulated like other objects. It also simplifies the data structure for the model.
The model also provides primitives to analyze the relationships between entities and deduce new relationships. In particular, the model will allow querying capability on entities. Other areas of computer science have successfully addressed the query issues on entities (relational algebra, object oriented languages, hypertext, deductive databases, logic programming, semantic modeling, knowledge discovery etc.), and ideas from such matured research areas will be incorporated as becomes necessary. Specifically, the following operations will be supported by the proposed model.
The visualization examples presented in  are very effective in conveying the semantics to the user as long as the data sets are small. With larger data sets, scrollbars can be used to pan the event of interest into the view. However, there is a loss of context with extensive panning . Use of curves, similar in nature to spirals  will be explored. A curved timeline will help in improving the ink to blank ratio . The Handbook and Atlas of Curves  lists many curves along with their equation that are suitable for this purpose.
One factor affecting the display is the magnitude of the time-span. There are very critical events of extremely short duration (e.g. earthquakes, lightning etc.) and extremely long duration events of little significance (e.g. formation of mountains). How can both types of events be incorporated on the same timeline? The proposed prototype will make use of color intensity to mark the criticality/significance of the entities. To manipulate relatively short duration entities, use of different cursor shapes will be explored.
In many real life situations a user likes to see many different types of events that occurred in a short period of time. A typical example is visualization of a coup in a country. In hindsight, a coup is a collection of rapidly occurring events that are from political, economic (devaluation of currency, foreign aid etc.), military, and social arena. Since these events are all parts of the same theme, visualizing them as a single timeline makes sense, although we would still like to be able to distinguish individual elements. If each timeline is about one type of events, a user may like to display multiple timelines on the same screen to get a wider perspective of events. User definable color and texture at the entity level will be supported in the proposed system.
First, it is necessary to identify various types of relationships with which entities interact then find ways to represent these relationships. Some instances of relationship types are causal, "part-of", "is-a", etc. Another factor is the possible use of logical operators (AND, OR, NOT, XOR) between different events. Relationships will be implemented as a separated subsystem. so a user can choose to disable or enable its display.
There are two broad types of relationships to consider. The first type is called categorical relationship, where entities fall into some user defined categories. An examples of this kind is, the kind of music written by music composers. Relationships having a notion of strength or magnitude fall into the second category of relationship types. For example the 'influence' relationship, one may want to represent how much the style of one music composer was influenced by his predecessors and contemporaries.
Various ways of displaying relationships will be explored. In particular, use of texture, styled lines, color gradients, shapes, and position are some of the possible approaches in dealing with this issue.
Timelines are a linear placement of abstract entities on the time axis. The resulting graph tends to have a highly skewed width compared to height. To view such a graph, extensive horizontal scrolling is mandated, which results in loss of context as mentioned above. Zooming out does not help, as the details get obscured. In short, this is traditional detail - context problem, for which many researchers have suggested solutions . The variations of these techniques and other novel techniques will be built into the system. In particular, use of the following techniques will be researched.
Fish-eye view is a novel distortion based technique for displaying large information in a small screen area. Mathematical equations developed in  will be incorporated into the proposed prototype. Since timelines are highly skewed in one dimension, a variation of the above methodology will be used.
A 3D Perspective Wall is a promising distortion based technique for displaying large information bodies whose display is very wide. It is ideally suitable for timeline application. The proposed prototype will incorporate a 2D version of the Perspective Wall.
Folding Paper is a novel 3D method for displaying large information bodies whose display is extremely wide. See appendix B for further details.
Log transformation is a useful display size reduction method. Time axis will be transformed to log scale to allow extremely large duration entities to be shown along with relatively short duration entities.
As described in the previous sections, generation of timelines requires input of information about events, attributes and relationships. During the development phase, a text editor will be used to enter this information, however a authoring tool will be more appropriate for this purpose. Specifically, two versions of such tools, one for authors who would like to create learning material for students. Another, a more advanced version will be directed to expert historians, political and social scientists who would like to define events at a finer granularity with more relationships and make use of advanced user-interface technique. Construction of such tools, using a suitable prototyping language is proposed. A very crude screen mockup of a authoring tool is given in appendix C.
In summary, the proposed prototype will be able to display information in the following ways.
As described above, the proposed system will make use of information visualization techniques which are still in the research phase.
Principles of "user centered design" will be employed in the design of this system. It has been shown that user centered design is clearly beneficial compared to traditional design-implement-test cycle . A few people will be selected to represent the potential user population of the proposed system. They will be contacted on a regular basis and their input will be sought in the critical design issues. As new features are implemented in the system, they will be asked to test the features and provide their opinion of it.
The implementation of the system will target the following design goals.
The proposed system, apart from meeting the design requirements, must be efficient, responsive, and a useful tool for information acquisition. An informal experiment with real subjects will be conducted to find the usefulness of the proposed system. The procedure of the experiment is described in this section. It follows the experimental methodology described in 
A prototype system incorporating the ideas described in this proposal will be implemented on the UNIX and Microsoft Windows operating system. Data for timelines will be collected from various fields. In particular, discipline of history, philosophy, literature, social science and political science are most relevant. There is ample data in books, magazines, encyclopedias, newspapers, and the Internet for this purpose.
This will involve obtaining volunteers to take part in the experiment. Volunteers are selected from the fields mentioned above and will be required to have familiarity with Windows style graphical user interfaces.
Subjects will be familiarized with the system, and detailed directions regarding "the information acquisition task" to be completed will be given. The task will involve a mix of identifying relationships between people and events, and between events, discovering critical events, testing simple claims etc.
Subjects will be asked to evaluate the system based on their experience, and rank it between one and five on several questions. An above average score will determine that it is a useful tool.
As discussed in the previous sections, alternate representation of information are needed to cope with ever increasing amount of information encountered in every-day life. Timeline is a powerful paradigm for organizing a major subset (the temporal information) of the vast body of information. The major contribution of this research is the development of presentation and analysis tools for timelines. The proposed system will combine many existing, and some novel, visualization and analysis techniques. The proposed evaluation will determine the efficacy of these approaches in allowing users with easier and quicker acquisition of information.