• Table of Contents
  • 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

    Introduction

    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 [24], automobiles [2], American Indians [23], the world history [27], science and technology [16], arts [17][18], and architecture[26] 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 [23] and Timelines of War [24] 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 [27] 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 [14][15]. 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.

    Problem area

    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 [13]. Most previous work has addressed use of timelines in specific domains [14][15] 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.

    Research objective

    Researchers recently have started looking into interactive timelines [13] [14] 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.

    1. Modeling of events (a more general term for an event is entity) and timelines is an important research area, making possible the use of events and timelines as first class objects that can be manipulated by users. Modeling is essential as it provides a domain-independent, abstract view of the timelines, on which event and timeline operations can be defined. There is only one model of timelines cited in the published literature [15] and it does not allow manipulation of entities.
    2. Novel techniques of displaying timelines that make better use of available screen space such as curves and distortion techniques are needed. Judicious display of texts, lines, rectangles that satisfy the aesthetics constraints in the limited available screen space is required. Display of multiple types of events on a single timeline is also important for providing the context for understanding the forgoing causes and the resulting consequences of an event. Data visualization techniques using advanced graphics open new doors for innovative visualization of timelines.
    3. Methods of displaying different types of relationship between events, e.g. causal relationship, "is-a", "is-part-of", spatial, and temporal relationships, are also largely unexplored. Representation of qualitative and quantitative magnitude of relationship is an issue that has not yet been addressed by researchers. Inter-timeline relationship is also an important issue as visualizing one timeline in the context of another is quite informative.

    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.

    Related work

    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 [4] 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 [15] 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 [13], suggesting many novel visualization techniques. This work also addresses the issue of the lack of formalism in this area. Lifelines [14], deals with use of timelines for visualizing personal histories, but remains mostly an ad hoc effort for one domain.

    Ahlberg et. al. [21], 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 [22]. Xerox Corp. offers software called Visual Recall [29], 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 [20]. 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 [25] and [19]. 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.

    Modeling entities and timelines

    Modeling entities

    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.

    Tractability assumptions

    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.

    Analyzing relationships

    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.

    1. Show relationships between entity A and entity B.
    2. What events, persons, etc., ultimately led to entity X i.e., give an explanation of X.
    3. Display the chain of entities that caused entity A.
    4. Display all sequences of events in which entity A is involved.
    5. Display the temporal context of entity A.
    6. Display the spatial context of entity A.
    7. Display the nesting context of entity A.
    8. Make compound queries using AND and OR connectives.
    9. Join two timelines to create a single timeline.

    Mapping abstract entities onto the physical display

    Visualization of simple entities

    The visualization examples presented in [1][2] 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 [6]. Use of curves, similar in nature to spirals [2] will be explored. A curved timeline will help in improving the ink to blank ratio [12]. The Handbook and Atlas of Curves [32] 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.

    Visualizing multiple entities and timelines

    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.

    Visualizing relationships

    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.

    Visualization techniques

    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 [6][7][9][10][11]. 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.

    1. Fish-eye views [6][7].

    Fish-eye view is a novel distortion based technique for displaying large information in a small screen area. Mathematical equations developed in [7] will be incorporated into the proposed prototype. Since timelines are highly skewed in one dimension, a variation of the above methodology will be used.

    1. Perspective Wall [9].

    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.

    1. Folding Paper.

    Folding Paper is a novel 3D method for displaying large information bodies whose display is extremely wide. See appendix B for further details.

    1. Log transformation.

    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.

    Authoring tools

    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.

    Summary

    In summary, the proposed prototype will be able to display information in the following ways.

    1. Overview of the whole timeline, i.e. a zoomed out view.
    2. Zoomed-in view with parts of the hierarchy pruned.
    3. Display entities at various levels (depth) in the hierarchy.
    4. Show all critical entities with certain level of criticality.
    5. Show all relationships w.r.t. entity X.
    6. Color code by user defined dimension.
    7. Color code by strength of relationships.
    8. Perform an elision operation.
    9. Superimpose one timeline on another.
    10. Show timeline after various transformations as proposed in section 6.4.

    As described above, the proposed system will make use of information visualization techniques which are still in the research phase.

    Design and Implementation

    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 [33]. 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.

    1. The system should have an extremely easy way to input data.
    2. System should be portable across the most common operating systems (Sun Solaris and Microsoft Windows)
    3. Users should not be required to have any specialized hardware such as, specific graphics boards, and specialized I/O devices.
    4. All the features should be accessible from the menu or a control panel of the application.
    5. Access to the detail on any entity should be available with minimal interaction.
    6. Help in hypertext form should be available at all times during interaction with the system.

    Evaluation

    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 [31]

    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.

    Research contribution

    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.

    References

    1. History of Mathematics Timeline. URL : http://aleph0.clarku.edu/~djoyce/mathhist/time.html
    2. Toyota Museum of Cars. URL: http://www.toyota.co.jp/Museum/Tam/chart.html
    3. Laurel, Brenda Editor. The Art of Human Computer Interface Design. Addison Wesley, , 1990, pp. 483.
    4. Allen J.F. Maintaining Knowledge about Temporal Intervals. CACM. Nov. 1983, page 832-845.
    5. Tyson R. Henry and Scott E. Hudson Interactive graph layout. In Proc. ACM SIGGRAPH, SIGCHI Symposium on User Interface Software and Technology. 1991, pp. 55-65.
    6. Furnas, G.W. Generalized Fisheye Views. In Proc. ACM SIGCHI '86 Conf. on Human Factors in Computing Systems. 1986, pp. 16-23.
    7. Sarkar, M., Brown, M.H. Graphical Fisheye Views of Graphs. In Proc. of CHI, 1992, ACM. New York. 1992, pp. 83-91.
    8. Kyoichi Arai, Teruo Yokoyama, and Yutaka Matsushita A Window System with Leafing Through Mode: BookWindow. In Proc. of CHI'92. 1992, pp. 291-292.
    9. Mackinlay, J.D., Robertson, G.G., and Card, S.K. The Perspective Wall: Detail and Context Smoothly Integrated. In Proc. of CHI'91. 1991, pp. 173-179.
    10. Robertson, G.G., Mackinlay, J.D., and Card, S.K. Cone Trees: Animated 3D Visualizations of Hierarchical Information. In Proc. of CHI'91. 1991, pp. 189-194.
    11. Johnson, B. and Shneiderman, B. Tree-Maps: A Space Filling Approach to the Visualization of Hierarchical Information Structures. In Proc. of IEEE Visualization '91. October 22-25, San Deigo, CA, 1991, pp. 284-291.
    12. Tufte, Edward. The Visual Display of Quantitative Information. Graphics Press, Cheshire, CT, 1983.
    13. Allen, R.B. Interactive Timelines as Information Systems Interfaces. Symposium on Digital Libraries. Japan, August 1995.
    14. Plaisant, C., Milash, B., Rose, A., Widoff, S., and Shneiderman, B. LifeLines: Visualizing Personal Histories. To appear in ACM Proc. of CHI'96. Vancouver, BC, Canada, April 14-18, 1996.
    15. Karam, G.M. Visualization using Timelines. Proc. of Intl. Symposium on Software Testing and Analysis (ISSTA), 1994. In SIGSOFT, ACM Software Engineering Notes. 1994.
    16. Ocha, George The Timeline Book of Science. Ballantine Books, New York, 1995.
    17. Ocha, George The Timeline Book of Arts. Ballantine Books, New York, 1995.
    18. Denvir, Bernard The Chronicle of Impressionism: a Timeline History of Impressionist Art. Bulfinch Press, Boston, 1993.
    19. Jansen, C. Weisbecker, A., and Ziegler, J. Generating User Interfaces from Data Models and Dialogue Net Specifications. In Proc. of InterCHI'93. April 24-29, 1993, pp. 418-423.
    20. Roth, S.F., and Mattis, J. Data Characterization for Intelligent Graphics Presentation. In Proc. of ACM CHI'90. April 1990, pp. 193-200.
    21. Ahlberg, C., Williamson, C., and Shneiderman, B. Dynamic Queries for Information Exploration: An Implementation and Evaluation. In Proc. of ACM CHI'92. May 3-7, 1992, pp. 619-626.
    22. Burger, J.D., and Marshall, R.J. The Application of Natural Language Models to Intelligent Multimedia. In Intelligent Multimedia Interfaces, MIT Press, Mark Maybury, Editor.
    23. Waldman, Carl Timeline of Native American History. Prentice Hall general reference, New York, 1994.
    24. Brownstone, David M. Timelines of War: A chronology of warfare from 100,000 BC to the present. Little, Brown Publishing, Boston, 1994.
    25. Mckinlay, J.D. Automating the Design of Graphical Presentation of Relational Information. ACM Transaction on Graphics. 5, 2 (April 1986), 1986, pp. 110-141.
    26. Mann, William A. Landscape Architecture: an illustrated history in timelines, site plans and biography. John Wiley publishers. New York, 1993.
    27. Smithsonian Institution. Smithsonian Timelines of the Ancient World. Smithsonian Institution Press. Washington D.C., 1993.
    28. Tom Schneider Production. Chronos. version 1.1, Tom Schneider Production. 1995.
    29. Xsoft Corp. Visual Recall: Personal Edition. version 2.0, 1995.
    30. Gansner, E.R., North, S.C. and Vo, K.P. Dag: A Program That Draws Directed Graphs. Software-Practice and Experience. Vol 18, 1988, pp. 1047-1062.
    31. Shneiderman, B. Designing the User Interface: Strategies for Effective Human-Computer Interaction, 2nd ed. Addison-Wesley, 1992.
    32. Shikin, Eugene V. The Handbook and Atlas of Curves. CRC Press Inc., 1995.
    33. Olsen, G.M. and Olsen, J.S. User Centered Design of Collaboration technologies. Journal of Organizational Computing. Vol. 1, 1991, pp. 61-83.