IIMS 92 contents
[ IIMS 92 contents ]

The hyperbase developer's toolkit

John Robertson and Kai Foong
Knowledge and Information Navigation Project
Division of Information Technology, CSIRO

1. Introduction

For the last two years, the Knowledge and Information Navigation Project (KIN) has been involved in the creation of a number of hypermedia systems. During this time we have repeatedly found that the conversion of linearly formatted text to a structure amenable to hypertext presentation systems is the most expensive and difficult phase in the hypermedia system construction process. Discussions with other hypersystem developers has confirmed that this problem is universal. Because of this, we have begun exploring ways to reduce this cost.

The ability to effectively migrate paper based information into a database is crucial to hypermedia's commercial success [Glushko 89]. We are aware that many people are trying to address this difficulty. Most of these efforts attempt to automate this "text to hypertext" process [Raymond 87, Salton 88, Glushko 89]. To do this they use structural information to guide the conversion, ie. keying on markup languages such as SGML or undertaking layout analysis of the text [Frisse 88, Furuta 89, Niblett 89, Zobel et al. 1991]. These efforts have proven to be of limited value. We believe that at present, in order to produce high quality hypertext components, the human cannot be removed from the conversion process [Furuta 89, Frisse 88, Raymond 88, Bernstein 1990]. Thus the expense of constructing hyper-databases must presently include the price of the human expert's participation. By providing software tools to assist the human in this editorial process, we believe that both the overall cost and time involved can be reduced to a commercially acceptable level.

This paper reviews the nature of this "transformation" problem and discuss a solution which employs Hyperbase Developer's Toolkit (HDT), a software system which the KIN project team designed and developed to assist the hyper-editor in the hypermedia database creation operation. Section 2 give an overview of our definitions of hypersystem components and section 3 describes the text to hypertext conversion process. Section 4 presents the Hyperbase Developer's Toolkit in detail and we conclude with discussion of future work in section 5.

2. Hypersystem components

Nodes, anchors, links, index and keywords or key phrases constitute the basic components of any hypersystems. We uses a set of "operational" definitions for various hypersystem components to guide the conversion process with an eye towards developing a more critical description as our experience and "wisdom" grows in this area. The following subsections give our definitions of these components.

2.1 Nodes

To us, a node is a "chunk of information that deals with a single theme". It expresses a complete thought and is not necessarily dependent on external information for understanding of the concepts conveyed within. The node's main function is to display information which could take the form of text, graphics, sound, video, or animation.

2.2 Anchors and links

Practically speaking , anchors and links are easier to define: they bind together associated concepts expressed within a set of nodes. By traversing a set of links, the user is able to browse a network of nodes containing related ideas.

There are two classes of links: structural and referential. The main functions of structural links are for ordering nodes in the same sequence as they appear in the original document and for integrating nodes into a conceptual schema. A hierarchical index of the subject domain can be created and nodes pertinent to each point in the schema can be linked to that point i(Fig. 1). Referential links are generated to bind common concepts together within the set of nodes. As in figure 2, the mention of the Viscomte Francois Rene de Chateaubriand in a node discussing people whose names have become household words would have referential links to nodes containing elaborative information on this man.

Figure 1

Figure 1: Structural links

2.3 Index

Index values are used to classify each node within a hierarchical index. The choice of index values to be assigned to a node conies from a controlled vocabulary, which should include all the possible concepts within the system's subject space without synonyms or overlapping terms [Parsaye 89]. With the hierarchical index, users can quickly and efficiently access nodes which convey particular ideas or topics in the system. 2.4 Keywords and key phrases Keywords and key phrases are word strings selected from the node's text, which relate to the main concepts expressed within the node. These can be used in search routines to find the set of nodes in the system that pertain to a particular subject or idea. Systems which allow searching of database using keyword queries are quite common.

3. Text to hypertext process

3. 1 Stage One: Conversion to an electronic medium

For systems which are to incorporate paper based information, the developer must first duplicate the text and graphics, commonly done with scanners and optical character reading technology (OCR), and then store them in electronic form. The cost of having a person scan in the documents and correct the errors produced by the OCR software can be very high but often unavoidable. Alternatively, it is much easier and cheaper to acquire the data in an electronic format from the author or the publisher.

3.2 Stage Two: Text to hypertext transformation

After the data is in a form which can be edited, it is ready for identification of the hypertext components, ie. nodes, anchors, links, keywords, and index values. This conversion from linearly arranged text into a structure tractable by hyper-databases is the most difficult process in the hypermedia system development process. This is due to the fact that currently, there is no standard methodology to achieve this conversion and even basic concepts such as what constitutes a node, a link, or an anchor, lack universally accepted definitions. In addition, another factor contributing to the difficulty in selecting appropriate hypertext components is that parsing of nodes followed by selections of links, anchors, index values and keywords or key phrases is a highly subjective exercise. It is in this text to hypertext conversion stage where the HDT provides guidance and counsel to the hyper-editor by furnishing a procedural framework which directs the editor through the various steps of the operation and by suggesting possible hypertext candidates in each mode.

3.3 Conversion methodologies

There are a number of different text to hypertext conversion techniques currently being investigated worldwide. The majority of these explorations are based upon the use of some markup language to derive the hyper-components. SGML [ISO 8879] and ODA [ISO 8613] are two markup languages which are being used for this purpose. The drawback of this method is that this approach produces structural links but not the referential ones. Given the main thrust of hypertext/media systems is to allow the reader to browse among concepts using associative links, we believe that the use of markup languages in this fashion is inherently inadequate. Others are exploring how to use the page layout as a clue to the conversion process. For example, text delimited by blank lines in the beginning of the document can be safely assumed as the title. Blank lines followed by some form of indentation on the first line of a body of text could be the beginning of a paragraph. By discovering the structure of the document it can be parsed up into nodes, and structural links can be generated to convey the structure of the original document. Once again, inter-document conceptual link generation is not possible with this approach.

Figure 2

Figure 2: Referential links

Some groups are using principles from the information retrieval discipline to improve the conversion process. The use of statistical, syntactic or semantic routines may be useful in deriving hyperbase components [Clitherow 89, Hayes 89]. These methods result in greater success than efforts in keying off structure because they attempt to derive semantic as well as structural information from the text and thus referential links may be derived from this process. Unfortunately, these techniques still have unacceptable error rates. Others are looking at developing automatic conversion techniques using knowledge based or natural language techniques [Lenat 86, Lenat 89]. Currently, these techniques have limited value for automatic hyperbase component generation.

For these reasons, the KIN Project is approaching this process from the perspective that the human must be provided with tools to assist them in the text to hypertext transformation process . The following sections give a description of the tool currently under development.

4. Description of the toolkit

4.1 Design principles

In order to provide a generic platform for hyperbase construction, it is very important to decouple the database design and the Graphical User Interface (GUI) design. This provides a mechanism which allows different interfaces to utilise the same hypermedia database. Conversely, it provides a way which allows a single interface to access multiple hypermedia databases, economically and efficiently. This design also promotes re-useability of software as adding a new front end will not affect the database manipulation codes. Only a simple protocol needs to be written for communication between the new front end and the database. Likewise, changing the database will only have minimal affect on the GUI code.

To ensure that the hyperbase creation tools are generic, it is important to adhere to standards. However, there is no commonly agreed upon standard for hyperbase system development at this moment. Therefore, we have designed our database schema in such a way that it can be easily modified to conform to emerging standards in the future. This schema is based on the notion that the knowledge in the hyperbase is make up of a collection of nodes or logical information modules (LIMs). These LIMs are arranged in a tree structure which reflect the logical relationship amongst the LIMs. For example, in one of our projects, the Australian Heritage Commission (AHQ Demonstrator, the flora information is arranged in genus-species structure where species are the children of a genus. For documents, this tree structure reflects the arrangement of sections and subsections within the document. In addition to the hierarchical links implied in the tree structure relationship, referential links are built for key phrases in the hyperbase. This design results in a network of linkages which provide the user with a mechanism to browse through the information space by following referential or hierarchical links.

4.2 Overview

The Hyperbase Developer's Toolkit is developed on a Unix platform using a Sun SPARC H workstation. The database layer is implemented using Titan+, an experimental nested relational database system from the Key Centre of Knowledge Based Systems at RMIT [Thom et al 1990]. The GUI is based on Motif 1. 1.2 and WCL, a public domain widget creation library. All the software is written in C.

There are four modules in the system:

  1. Editorial Module --
    This module performs the transformation from raw to marked up data. Both batch and interactive mode of this module are implemented.

  2. Hyperbase creation/loading Module -- is performed.

    In this module, transformation from marked up data to database storage is performed. Syntax errors in the mark up are flagged in this stage.

  3. Maintenance Module --
    This module provides the facility to give selective dumps of the hyperbase content and statistical listing of data in the hyperbase.

  4. Presentation Module --
    This is the front end of the system where the GUI is implemented to handle interactions between users and the hyperbase.
The following sections describe each of these modules in more details.

4.3 Editorial stage

4.3.1 Batch mode

Initially, the editorial stage is entirely decoupled from the hyperbase creation and loading stage. The user edits a text file to put in simple markers to denote nodes, anchors and various components in a hypertext. This process was greatly simplified by the fact that we are working with knowledge in a restricted domain (flora of Tasmania). Once the user has finished with marking up the file, a hyperbase loading program is invoked to parse the file and load the data into the hyperbase as described in the next section. This arrangement worked quite well but we expect an interactive environment should greatly enhance the productivity of the user and reduce error in the processed data. The following subsection describes this improved interactive editorial stage.

4.3.2 Interactive mode

The human uses a customised text editor to identify the various hypertext components contained within the linear document (Fig. 3). The markup language used for this stage includes symbols which define anchors, nodes, node titles, anchor types, node categories, key phrases and index values (Fig. 4). In addition, there is an interactive link-generation tool which allows the editor to choose the destinations of anchors by presenting a list of existing node tides as potential candidates (Fig. 5). Error correction at this stage is limited to ensuring names given to the nodes in the hyper-document are unique.

Figure 3

Figure 3: The Text Editor where nodes are identified

Figure 4(a)

Figure 4(a): Mark a node in a document

Figure 4(b)

Figure 4(b): Process a node individually

Figure 5(a)

Figure 5(a): Window for anchor/link specification

Figure 5(b)

Figure 5(b): Window for keyword/key phrase specification

4.4 Hyperbase creation and loading

4.4.1 Batch mode

With the initial design, the hyperbase is loaded in batch mode. The system reads in and parses all the specified marked up files, loads the hyperbase and generates some diagnostic comments regarding the status of the operation. Anchors without destination are also output as part of the diagnostic comments. The drawback of this batch mode loading is that we have to wait until the loading has finished before any correction can be made. Described in the following subsection is an improved version of hyperbase loading where this process is integrated into the editorial stage in an interactive environment.

4.4.2 Interactive mode

Once the user is satisfied with the markup of the raw data, a parser is invoked from the editor to read in the text file and to insert or update this new data into the hyperbase. At this stage, error checking is performed at the syntactic level. For example, anchors that have no associated link and links which do not have an origin or a destination anchor can be flagged for correction without delay. In addition, the text file with markups can be saved to the file system for backup purposes or future reference and update.

4.5 Maintenance stage

For hyperbase maintenance purposes, there are tools which generate listings, dumps and statistics of the components in the hyperbase, giving the conversion editor various views of the system's structure. Using these tools, users are able to review the contents of the hyperbase as well as check for semantic correctness and consistency. The statistics listing can be used to help the editor identify nodes that have too many links. The editor may then wish to modify the network structure associated with these nodes to avoid overloading the reader with too many navigation options. In addition, the statistics also provide a coarse measure of the general complexity of the hyperbase.

4.6 Presentation stage

There is a presentation manager which provides the users with standard hypermedia functions, for example, searching, index, browsing and session navigation history. The following subsections describe each of these functions in details.

4.6.1 The main display

This module consists of GUI which allows the user to access information in the hyperbase. There is a main window (Fig. 6) which consists of three areas:

  1. Active information display (AID)
  2. History and bookmark window
  3. Function panel

Figure 6

Figure 6: The main window

AID displays the content of one LIM at a time and a way for the user to traverse the hyperbase is by double clicking on anchors in the AID. There is a history and bookmark mechanism associated with this display. The history is a list of LIMs titles visited by the user in one session. The user can mark LIMs for future reference and by clicking on the Return button, the latest marked LIM will be displayed in the AID.

If there are pictures associated with a LIM, a click on the Graphics button will give a pull down menu which consists of a list of picture titles. A picture is displayed by selecting a title from this menu. In addition, if there is a map associated with the LIM, a click on the Map button will instruct the system to retrieve the associated map from a remote GIS database [Abel et al. 1991]. There is a facility to save the content of a LIM into a text file. When the Save button is clicked, the user is prompted for a file name and the content of the currently displayed LIM will be saved into a disk file.

A floating popup menu is associated with this main window. Various hypertext utilities can be invoked by selecting an entry in this menu. Currently, the utilities supported are: Search by boolean query, Hierarchical index, Fish-eye index [Furnas, 861, and a simple editorial tool for editing a special type of LIMs which have a pre-defined format. The following subsections describes each of these in more details.

4.6.2 Hypertext navigation utilities

There are several ways in which the user can access the information in the hyperbase:

  1. By following referential links:
    This is achieved by doubling clicking on an anchor (delimited by { and } in the AID.

  2. By following hierarchical links:
    There are two index displays in this system. The hierarchical index (Fig. 7) gives a list of children's LIM title of the currently displayed LIM. Selecting an entry in this list will bring up the text of the selected child. The user can traverse up the hierarchical tree by clicking on the Parent button. Clicking on the Root button will bring the user back to the root of the tree.

    Figure 7

    Figure 7: The hierarchial index

    The shortcomings of this index are that we cannot see more than one level of LIM titles at a time. The fish-eye index (Figure 8) [Furnas, 861 is provided to overcome this problem. This index display lets the user have a variable resolution view of the hierarchical tree structure by incorporating the concept of resolution order. With zero order, the tree consists of the ancestry list from the current LIM to the root of the tree (ie. root, ....., grandparent, parent, current LIM). With first order, the tree is augmented by including the immediate children of all LIMs in the zeroth order tree. This can be generalised recursively to any order greater than 0.

    Figure 8

    Figure 8: The fish-eye index

  3. By performing a search:
    A search window (Figure 9) is provided for the user to perform key words or key phrase search. Boolean search queries can be easily constructed by typing in words, clicking on boolean operators buttons or selecting from alphabetically listed key phrases in the hyperbase. The system then searches for LIMs which satisfy the search query and the results are displayed as a list of LIM tides. By selecting an entry in this result list, the corresponding LIM will be displayed in the AID.

    Figure 9

    Figure 9: The search window

4.6.3 Hypertext editing facility

In the Australian Heritage Commission Demonstrator project, there is a special category of LIMs called Type Profile. Type profiles contain description of specific information types in the knowledge domain. This information is structured into a template format so that comparison amongst different profiles can be performed easily and uniformly. With this standard format, the author of type profiles need only to fill in a proforma relating to a specific class of types. A mechanism to create, update and delete type profiles is included in the system.

There is a main window for the type profile related functions (Fig. 10). It consists of a functions panel and a type profile active display area (TPAID). Two templates, which correspond to two classes of types in the system are provided in this version. Subsections in the template can be edited one at a time and the resulting type profile will be displayed in TPAID. While editing a subsection, the user can type in words and make link to LIM currently displayed in AID. Operation of cut and paste from AID into type profile is not provided because this will cause information redundancy in the system.

Figure 10

Figure 10: The type profile main window

5.0 Discussion, future work and conclusion

5.1 Discussion

The HDT attempts to capture the semantics during the hypertext construction phrase by providing an environment in which humans can efficiently incorporate domain knowledge into the hypertext component identification process. Commercially, this tool can be customised to work with different applications because it is generic. Although we have not conducted any quantitative evaluations on the benefits of this toolkit during hypermedia system construction, those who have used it report quite confidently that the toolkit has provided valuable assistance. In our future projects, we will investigate and evaluate quantitatively the benefit achievable with this toolkit.

5.2 Future directions

The next stage of the toolkit development schedule is nearing completion. At the end of January 1992, the basic shell will be completed to guide the user through the above mentioned process in an online interactive mode. We will expand upon these facilities and explore the use of various algorithms to enhance the ability of the tool in suggesting the "best" candidates as hypermedia components.

5.2 Conclusion

In this paper, we have shown an effective and efficient methodology for converting paper based text into a format suitable for hypermedia systems. We have also highlighted the Hyperbase Developer's Toolkit functionalities which assist the human in this conversion process. If hypersystems are to become widely accepted, the cost of production must be reduced. Currently, we believe the only viable method for achieving this is to assist the human in this conversion process. In the future, as hypermedia systems become more commonly available, people will create hyper-documents directly within this environment. Although work on hypermedia authoring systems is currently being conducted worldwide, there will always be a need to incorporate into hypermedia systems, information archives which were created prior to the birth of hypersystems.


Abel, D., Ackland, R., Cameron, M., Smith, D., Walker, G. and Yap, K. (1991). EDSS: A prototype for the next generation of spatial information systems. AURISA '91.

Bernstein, M. (1990). An apprentice that discovers hypertext links. In A. Rizk et al (eds), Hypertext: Concepts, Sytems and Applications. Cambridge University Press, Cambridge.

Clitherow, P., Riecken, D. and Miller, M. (1989). VISAR: A system for inference and navigation in hypertext. Hypertext '89, Pittsburgh, Nov 1989.

Frisse, M. (1988). From text to hypertext. Byte, October, 247-253.

Frisse, M. (1988). Searching for information in a hypertext medical handbook. Communications of the ACM, 31(7, July), 880-886.

Furnas, G. W. (1986). Generalised fish-eye views. CHI'86 Proceedings, 16-23. Boston, MA.

Furuta, R., Plaisant, C. and Schneidermann, B. (1989). A spectrum of automatic hypertext construction. Hypermedia, 1(2), 179-195.

Glushko, R. J. (1989). Design issues for multi-documents hypertexts. Hypertext '89, Pittsburgh, Nov 1989.

Hayes, P. and Pepper, J. (1989). Towards an integrated maintenance advisor. Hypertext '89, 119-127. Pittsburgh, Nov 1989.

ISO 8613 (1989). Information Processing - Text and Office Systems - Office Document Architecture (ODA) and Interchange Format, 1989.

ISO 8879 (1986). Information Processing - Tools and Office Systems - Standard Generalised Markup Language (SGML), 1986.

Lenat, D. B. (1986). CYC: Using common sense knowledge to overcome brittleness and knowledge acquisition bottlenecks. AI Magazine,, 6.

Lenat, D. B. and Guha, R. V. (1989). Building Large Knowledge Databases. Addison-Wesley.

Niblett, T. and van Hoff, A. (1989). Programmed hypertext and SGML. Sept 1989, The Turing Institute.

Parsaye, K., Chignell, M., Khoshafian, S. and Wong, H. (1989). Intelligent Databases: Object Oriented, Deductive, Hypermedia Technologies. New York: Wiley and Sons.

Raymond, D. and Tompa, F. (1987). Hypertext and the New Oxford Dictionary. Hypertext '87 Proceedings, 143-154. Chapel Hill, North Carolina.

Raymond, D. and Tompa, F. (1988). Hypertext and the New Oxford Dictionary. Communications of the ACM, 31(7), 871-879.

Salton, G. (1988). Automatic text indexing using complex identifiers. Proceedings ACM Conference on Document Processing Systems, Santa Fe, New Mexico.

Thom, J. A., Kent, A. J. and Sacks-Davis, R. (1990). A post-relational query language. Technical Report #17, Royal Melbourne Institute of Technology.

Zobel, J., Wilkinson, R., Thom, J. A., Mackie, E., Sacks-Davis, R., Kent, A. J. and Fuller, M. (1991). An architecture for hyperbase systems. Paper given at The First Australian Multimedia, Communications, Applications and Technology Workshop.

Authors: John Robertson and Kai Foong
Knowledge and Information Navigation Project, Knowledge Based Systems
Division of Information Technology, CSIRO, Australia

Contact: John Robertson robertso@syd.dit.csiro.au
Phone: (61) (02) 8879496 Fax: (61) (02) 8887787

Please cite as: Robertson, J. and Foong, K. (1992). The hyperbase developer's toolkit. In Promaco Conventions (Ed.), Proceedings of the International Interactive Multimedia Symposium, 393-407. Perth, Western Australia, 27-31 January. Promaco Conventions. http://www.aset.org.au/confs/iims/1992/robertson.html

[ IIMS 92 contents ] [ IIMS Main ] [ ASET home ]
This URL: http://www.aset.org.au/confs/iims/1992/robertson.html
© 1992 Promaco Conventions. Reproduced by permission. Last revision: 5 Apr 2004. Editor: Roger Atkinson
Previous URL 2 Apr 2000 to 30 Sep 2002: http://cleo.murdoch.edu.au/gen/aset/confs/iims/92/robertson.html