Rob Kremer, kremer@cpsc.ucalgary.ca
This chapter briefly surveys some of the literature relating to the design of Accord. Shared interaction is a prime topic of the CSCW literature, but Accord also draws heavily from the hypermedia and hypertext literature as well. Indeed, the hypermedia literature often addresses group use of hypermedia systems, so the two literatures tend to overlap. Furthermore, the concept mapping (or semantic net) literature also contributes significantly to the design.
This section briefly surveys some of the recent CSCW systems. A rough classification is presented based on synchronicity and locality, target domain, control of social protocols, and media support. It will form an infrastructure in which to place Accord.
One of the most salient attributes of CSCW systems is the interaction modes that they support. Table 1 describes the four possible interaction modes. Of these, three are of interest: face-to-face meetings, synchronous remote interaction, and asynchronous remote interaction. They are each described below.
In the CSCW context, face-to-face meetings are just the traditional "boardroom" type meetings but with electronic support tools. Electronic meetings can suffer from the same problems and need the same support and preparation as do traditional meetings [Dubs 92].
Some electronic meeting rooms, such as the University of Arizona's electronic meeting room [Nunamaker 91], rely on a trained human facilitator to guide the group though the meeting using a large variety of tools. The University of Arizona's electronic meeting room is primarily aimed at decision support (as opposed to detailed design tasks). Each of its tools are specialized to support some facet of decision making, such as brainstorming or eliminating alternatives. The facilitator is required to choose the tools, synchronize the participants, and start up and shut down the various tools.
Other meeting room applications do not necessarily require a facilitator, and generally do not supply such specialized tools -- tending to be much more generic instead. Cognoter in the Colab at Xerox Palo Alto Research Centre [Stefik 87, Tatar 91] provides both shared and private electronic workspace for up to four participants (see figure 4) and relies primarily on normal social protocols for mediation (see section 2.1.3.). The only tools provided are very generic "whiteboard" drawing and writing tools which can be applied equally well to both decision making and design problems. The Capture Lab at the University of Michigan [Mantei 89] seats up to eight participants in a boardroom-like environment. It provides participants with individual screens on each of their computers, but participants may project their screens on a large shared screen at the front of the room (see figure 5).
Synchronous remote interaction differs from electronic meetings only in that participants are not in the same room. This leads to a considerably different set of problems due to the absence of natural vocal and gestural communication. Examples of synchronous remote interaction systems include shared-view single-user applications, true multi-user applications, shared desktops, and live video windows on the desktop. Many of these applications establish at least an audio connection between participants, and some include full tele-conferencing capabilities; however, full video connection requires high bandwidth communication and is still difficult and expensive to set up.
Synchronous remote interaction applications include Grove [Ellis 91], a group editor; GroupSketch and GroupDraw [Greenberg 92c], group drawing applications; Cantata [Chang 87], Shared X [Garfinkel 89], sharing views of single-user applications; and Rapport [Ensor 89], a multi-media conferencing system.
The prime example of asynchronous interaction CSCW applications is electronic mail systems. E-mail has so far been the only large-scale success of CSCW systems and provides far more than just simple communications: It supports information management and provides a mechanism to support time management and task management activities [Mackay 88]. However, asynchronous interaction encompasses far more than E-mail, as E-mail provides little in the way of shared environment or task focus. Enhanced asynchronous systems include the Andrew Message System [Borenstein 88], which adds multimedia, bulletin boards, "active messages", and incoming message filtering to basic E-mail functionality. Information Lens [Malone 86, Mackay 89], Object Lens [Lai 88] and Oval [Malone 92] form a sequence of systems that provide computational behaviour and structure to the message objects, allowing the user a high degree of control over the objects. Quilt [Leland 88] and PREP [Neuwirth 90] are asynchronous group editors.
CSCW research tends to fall within several different research areas. Management research, such as at the University of Arizona [Nunamaker 91] and the Capture Lab at University of Michigan [Mantei 89], has tended to concentrate on decision support. Educational research, such as Intermedia [Yankelovich 85] and SharedArk [Smith 91], has concentrated on learning through interaction with peers and with instructors. Other research, such as Cognoter [Stefik 87, Tartar 91] and GroupDraw [Greenberg 92c], has concentrated on more generic and collaborative tasks such as design and group writing. Still other research, such as Object Lens [Lai 88] and The Coordinator [Winograd 87], concentrates on group and individual organization and coordination.
These diverse groups reflect different contexts in terms of group size, task type, and social context. Some voting tools in decision support systems allow for hundreds of participants to electronically register their votes; whereas interactive design systems could not be expected to handle this number of participants. On the other hand, large-group decision support systems could not be expected to handle the complexity of a group aircraft design CAD system. Furthermore, the social control and facilitation demands for a large public gathering on a controversial topic are quite different from those needed for a small, tightly knit group of co-authors.
Most CSCW systems cause the group to incur a loss of the normal social protocols that normally occur in face-to-face meetings, such as eye contact, gesturing, and vocal inflections. Therefore, CSCW systems have to compensate in some way for the loss. Current CSCW systems offer a range of support for computer mediated social protocols. Electronic mail has virtually no intrinsic protocol, but relies almost exclusively on normal social protocols. Computer conferencing systems often make use of different classes of users such as chairs, participants, and observers. Shared-view systems using single-user software often offer elaborate floor control systems to pass the single control stream between multiple viewers [Greenberg 90].
Asynchronous CSCW applications can also exert control over social protocols. The Coordinator [Winograd 88, Flores 88] is a system based on speech act theory [Searle 69], [Winograd 87] that tracks electronic "conversations", enabling participants to request lists of obligations they have to others, obligations others have to them, and deadlines. Information Lens [Malone 86], Object Lens [Lai 88] and Oval [Malone 92] are systems that build upon electronic messaging with structured message types, user-programmability, and intelligent agents to support coordination among participants. ConversationBuilder [Kaplan 91] builds on Winograd's and Malone's work to provide flexible conversations based on three kinds of "protocols" -- process protocols, discussion protocols, and transient protocols.
It is interesting to note that CSCW systems can not only restrict social interaction, but can also support interaction that is normally suppressed by normal social protocol. A good example of this is the anonymity offered in some group decision making systems: Anonymity allows lower-ranking individuals in a highly stratified group to have their opinions and ideas presented on an equal footing with those of higher-ranking individuals [Nunamaker 91].
CSCW systems are often media dependent. A large fraction of current real-time CSCW research concentrates on "telepresence" -- giving distant remote participants the illusion of a face-to-face meeting through the use of elaborate video equipment. Examples are Talking Heads [MIT 83] and the "video tunnel" of SharedARK [Smith 91], which make elaborate use of video effects. Most "real-time" systems rely on, or benefit from, at least an audio connection between participants as an auxiliary channel. These include systems that centre around a shared work surface such as GroupDraw and GroupSketch [Greenberg 92c] which provide a shared drawing window, and ClearBoard [Ishii 92] which provides elaborate video overlays on a work surface.
On the other end of the spectrum is simple electronic mail which uses only asynchronous, static text. Asynchronous CSCW applications do not tend to rely heavily on advanced media but may benefit from graphics, voice annotation, video clips, animation, and recorded gesture.
A potentially important aspect of current and future CSCW applications is the use of "intelligent agents". Just as computer games often have the ability to provide electronic "players", CSCW applications may have the ability to provide electronic participants. Electronic participants act as collaborators, facilitators, or servants. One example is Lisa, a participant intelligent agent [Ellis 91]. One can envision a facilitator agent in a conferencing system or servant agents that human participants can dispatch to search complex databases or group discourse histories.
This section is a brief overview of hypermedia system design. There is little distinction here between hypermedia and hypertext since the two can be viewed as being positioned at different points along a continuum of richness of display media.
Hypermedia systems differ from document presentation systems in that users are encouraged to take a non-linear path through the material. Users normally navigate among small chunks of information called nodes via connections called hyperlinks. From the users' point of view, hypermedia systems differ by their presentation of nodes, the kind of navigational tools available, security schemes implemented, extendibility, and tailorability. Hypermedia systems designers must concern themselves with these features as well as design of the database.
As an aside, this section makes use of existing systems to illustrate many of its points. Two systems used in many of these examples are HyperCard [Goodman 87] and Toolbook [Asymetrix 89a, Asymetrix 89b], both of which are programmable systems that include very powerful scripting languages, which allow a knowledgeable author to do almost anything with them. Unfortunately, this property does not make for very good examples, since almost any statement one makes can be contradicted. But these two systems, discounting the scripting languages, are excellent examples of many points. Following the philosophy of Stroustrup [Stroustrup 91] that there is an important difference between supporting a feature and enabling a feature, this section takes a narrow view of HyperCard and Toolbook and ignores the scripting languages and all the power and flexibility that they bring to these systems. The HyperCard and Toolbook examples are all from the point of view of an author who does not know the relevant scripting language (which is not an unlikely case, attesting to the power of these systems).
A hypertext node is the unit of information display. Beyond this, a strict definition of node is elusive, since there seems to exist counter examples for almost any more specific definition. Akscyn [Akscyn 88] in describing hypertext and hypermedia avoids the term node, in favour of units of information:
"Information is "chunked" into small units, variously called notecards, frames, notes, etc. Units may contain textual information. In hypermedia systems, units also contain other forms of information such as video graphics, bit mapped images, sound and animation".
Campbell and Goodman [Campbell 88] define a HAM (Hypertext Abstract Machine) node as containing "... arbitrary data that can be stored as text or as fixed-length binary blocks." Conklin [Conklin 87a] puts nodes in the context of databases and windows:
"The database is a network of textual (and perhaps graphical) nodes which can be thought of as a kind of hyperdocument. Windows on the screen correspond to nodes in the database on a one-to-one basis, and each has a name or title in the window".
None of these definitions truly suffices, but together they convey the general idea. A node is analogous to a page or a small section in a book in that it is a small chunk of information with a referential name, just as a page or a section contains a small chunk of information, and can be referred to by the book's title and page or section number.
Although every hypertext system displays each node in its own window, they vary in how they define the node window. Many of the single user systems such as Hypercard, Toolbook, and Hyperties [Shneiderman 89] restrict display to only one node (or one node per document) at a time. The majority of hypertext systems allow multiple nodes from the same document to be displayed concurrently: examples are EHTS [Wiil 92], Intermedia [Yankelovich 85], and Neptune [Conklin 87, Delisle 86]. KMS [Akscyn 88] is an interesting intermediate example. KMS has fixed size frames (1132x805 pixels) and only two display modes: one node on a full screen or side-by-side display of the left sides of two nodes.
It is generally accepted that hypertext nodes should contain a single idea, and so tend to be small units compared with the usual idea of a file [Conklin 87a]. However, an "idea" is a rather vague notion, and it is unclear how large an idea's textual or graphical expression might be. Nodes are usually comparable in size to a paragraph or a page. It is not clear whether this is a natural boundary or whether it is merely a function of the size and resolution of the current generation of computer display screens. There is considerable debate [Shneiderman 89] about the optimal size of a node. Larger nodes must be scrolled to be viewed, and smaller nodes imply larger networks, which can contribute to navigational problems. One needs to strike a balance between displaying a complete idea in context (with room for annotation) and keeping the node display small enough so as not to intimidate the user with too much information or force the user to search for information within the node (scrolling).
There is little question that any system should present a consistent face to help prevent the user from becoming disoriented. This issue splits hypertext system developers on whether to provide consistently sized node windows or allow the size to change as appropriate for the information contained (which may imply scrolling if there is more information in the node than can be shown on the screen). Existing systems cover almost the entire spectrum of possibilities.
KMS rigidly fixes the node window size to 1132 by 805 pixels, with the display being restricted to showing either only a single whole node or two side-by-side left hand halves [Akscyn 88]. The developers of KMS justify this size as an upper bound on the grounds that scrolling is a very inefficient way of navigating in a database. They justify the size as a lower bound on the grounds that there should be ample room for user annotation.
Hyperties [Shneiderman 89] is a system running on the IBM PC under DOS and uses the entire screen to display each node, with no scrolling allowed.
Toolbook and HyperCard fix the window size for an entire application, but Toolbook allows scrolling within the fixed size, up to a document-imposed limit. HyperCard does not allow scrolling in the node display.
NoteCard [Halasz 88] is a multi-window system that allows the writer to dictate the node window size on a per-node basis. This is the case with most multi-window systems.
Winhelp (the Microsoft Windows 3 help facility) allows the user to change the size of the window. Text fields within the window are stretched and word-wrapped to match the right edge of the window. Furthermore, scroll bars are shown if the information cannot be completely placed within the visible window.
Table 2 summarizes the possibilities and gives examples of each. It is interesting to note that non-scrolling interfaces with dynamic sizing (where the user can resize the window) is inappropriate since parts of the node could be made inaccessible.
Formal, structured data (as opposed to informal, unstructured data in text) associated with a node can be extremely useful for both the user and for computation on the database. There are two notions of formal information associated with a node -- type and attribute. Type is the stronger concept and encompasses the "hard-wired" implementation of the node and completely dictates or restricts the possible uses of the node. It is usually difficult or impossible to modify the type of a node after it is created. Attributes are additional features of nodes that can usually be added or modified throughout a node's lifetime. Attributes are often maintained as lists of attribute/value pairs, as in HAM [Campbell 88] and Toolbook.
Type or attribute information can maintain context and help guide the user when navigating the database (see section 2.2.2.). For example, node types such as "example", "explanation", and "overview" can be extremely useful to the user.
Type and attribute information can also allow the system greater functionality. For instance, some systems such as HAM [Campbell 88] can use attributes to filter out nodes that may be of no interest to the user, such as nodes not having a particular keyword (where a keyword list is an attribute). Much more powerful use can be made of type information. For instance NoteCards [Halasz 88] has three types: graphical browsers, file boxes, and note cards. NoteCards' graphical browsers are extremely powerful views of the database, fileboxes implement a strict hierarchy on the database, and note cards are "blanks" that the author is free to structure in any way. Browsers can be automatically generated and can be used as dialogs for navigation or user modification of the database. File boxes can be used for such tasks as printing linear versions of the document. In contrast to all this, the generality of the third type, note cards, allows for very little automatic system processing. These three NoteCards types are true system-defined types. But NoteCards further allows user-defined subtypes of note cards which could more properly be called attributes and resemble semi-structured nodes (described below). The system can only work with these types in limited ways, and they are primarily used only by the user as information templates.
KMS [Akscyn 88] has only a single, generic node type. EHTS [Wiil 92] has two types: directory and data, which is probably an artifact of it being so closely bound to the Unix file system. IBIS (Issue Based Information System) [Conklin 87b] has three types based on a semantic framework: issues, positions, and arguments. Since IBIS is basically a special-purpose system, it can make use of these three types for considerable database computation. For example, an issue without attached positions is indicative of an incomplete network.
While true node types are generally fixed by the system, attributes are generally extendible by the user. In general, attributes are maintained as lists of attribute/value pairs attached to the node and are not generally used for much beyond searching and filtering except in the case of hypertext languages that have associated programming languages such as HyperCard, Toolbook, and EHTS. HAM (Hypertext Abstract Machine) [Campbell 88] uses typed attribute/value pairs. EHTS also allows typed attribute/value pairs, but they are fixed by the application programmer (author) at compile time.
Node types and attributes are not necessarily reflected in the structure of the information displayed on the node window. Nodes that share common field types and arrangements (text, graphic, video, etc.) are known as semistructured nodes. The concept is best exemplified by Information Lens [Malone 89] and Object Lens [Lai 88] in which users deal with windows divided into typed and untyped fields that help to prompt users for all information to complete an editing or authoring task. For example, sending a request message may entail a user completing a form containing the sender, the receiver, today's date, a deadline date, and the text of the request (see figure 7). The advantages of the imposed structure are:
The user is reminded to supply complete information. For example, the user will not easily forget a deadline date.
The system will be able to at least partially process the node without understanding the semantics of the natural language text. For example, the system can post the request to an electronic calendar at the deadline date if the receiver accepts the request.
Semi-structured nodes are useful for more than just interpersonal communication. Even for single user systems their use is pervasive. Toolbook and HyperCard, even though they are have no concept of typed nodes, still strongly encourage semi-structured nodes: A single background shared by many nodes can contain field objects containing text elements specific to each foreground node. Thus, a background acts like a template for the author to fill in specific information. The advantage is that the user will become familiar with the screen layout. In addition, it facilitates system functionality in that a user may use the structure for queries -- for example, a user may request a report of all "name" and "phone number" fields from a particular background type to produce a phone list.
Navigation refers to the user's means of exploring the database. The "usual" means of navigation in hypertext is through direct links, which are discussed in some detail in this section. However, navigation can also be by database-style search and query, which is discussed in section 2.2.2.2.
Hyperlinks are direct references from one point in the database to another. A link reference (or source) is usually represented as a highlighted piece of text or an icon in the node display. A user traverses a link to the referent (or destination) by some simple command such as a mouse click on the reference. Links are the basic method of navigation in hypertext and, more than anything else, serve to delineate hypertext systems from document browsers.
If a link is viewed as an arrow from a reference (source) point at the tail of the arrow to some referent (destination) point at the head of the arrow, then the objects to which the arrow terminals attach to are the anchor objects.
The reference object may be an entire field, graphic, menu selection, or any object within a node display.
There are many possibilities for the physical appearance of a link reference, but it would be desirable for the link appearance to give the user some clue as to the type or use of the link. Although some graphical browsers attempt to differentiate on link type, there are few systems that actually force the author to differentiate reference appearance in node displays. KMS [Akscyn 88] is a good case study. KMS has two link types: a reference to another node to be displayed on a link traversal, and a reference to another application to be executed on a link traversal. All references appear with small circles to the left of the reference; node references are differentiated from application references by empty circles and filled circles respectively. Furthermore, it is a KMS convention that all annotations begin with an "@". Thus, KMS readers have quick, visual information about both what will happen if a link is followed, and the superficial type of the link. The fact that the "@" convention was developed illustrates the need for visual clues about link type. Boxer [Conklin 87a, diSessa 86] is an interesting example as references are represented by "ports" -- fully functional, miniaturized versions of the complete referent node display (see figure 8).
Hypermedia systems also differ in what constitutes a referent, or referent anchor. Many systems (KMS, Toolbook, HyperCard, NoteCards) directly support only whole nodes as referents. However, some systems, such as Neptune [Conklin 87a, Delisle 86] and Intermedia [Haan 92], offer support for reference to a particular point in the same or another node. A problem with point referents is that some systems store point referents only as an offset from the beginning of the node: If information is inserted before the referent point, then the reference will be to the wrong point in the node. Fortunately, Neptune's referents are icons within the body of a node; Intermedia saves node modification history lists to reconstruct correct referent points from out-of-date offsets.
Some systems allow external referents. KMS offers "links" that execute external applications. Intermedia, being basically a composition of applications, makes external application reference a very natural concept. Systems with associated programming languages, like HyperCard and Toolbook, offer a great deal of flexibility in links, since the author can associate an arbitrary script (program) with the reference object.
Still another possibility is reference to composites. Sometimes a reference is logically connected to some collection of nodes and not to an individual node. The only system found that directly supports this notion is HAM, with its contexts [Campbell 88]; HAM is a hypertext database system only and so does not support an interface (it is the database system used by Neptune). Many systems support composites only informally by referring to the "head" node in a hierarchy. It is unclear exactly how a strong concept of composite reference would be represented on the interface. What happens when a user traverses a link to a composite? All the nodes from the composite suddenly appearing as individual windows on the screen could be very disconcerting to the user. The nodes could all appear as internal children to parent window (as in Boxer). Or, for systems that support user-defined browsers (or views), an overview window could appear containing all the references to all the referent nodes.
Distinct from the notion of composite referent links is the weaker notion of multi-referent links. While composite links refer to a collection of links and the relationships between them, multi-referent links merely have multiple heads anchored in different places. There is not necessarily any interesting relationship between the referent nodes. Multi-referent links are implemented in few systems; however, Intermedia uses them on the grounds that references often occur together and tend to clutter up the display. Intermedia displays a single reference, then displays a pop-up menu with the titles of the multiple referents when the link is traversed.
It is easier to implement one way links than two way links. One way links normally used in HyperCard, Toolbook, and KMS, while two way links are enforced in NLS and FRESS [Conklin 87a]. It should be emphasized that the difference here is in enforcing two way links on all references. The additional difficulty in enforcing and supporting two way links is balanced by the added functionality. Two way links allow users to back trace links, and allow the system to handle problems such as gracefully handling references to nodes that are being deleted. Two way links carry with them the problem of where to put the "back links" in the referent node. Should each node have a special list of "links to"? Or should there be an icon imbedded in the node for each reference?
Many systems maintain links as first-class objects with attributes and types, just as nodes may have attributes and types. Link attributes can be used for:
· filtering, as in HAM where possibilities are limited to only those links matching a particular predicate [Campbell 88],
· search, as in [Garg 88] where keywords are used to produce retrieval sets,
· context clues for the user, as in NoteCards' graphical browser, where various link types are displayed as different arc types [Halasz 88],
· database computation, as in IBIS where link types have semantic meaning [Conklin 87b].
IBIS is particularly interesting example. IBIS is a specialized application to deal with issues, and the types (responds-to, questions, supports, object-to, specializes, generalizes, refers-to, replaces) are chosen to convey specific meaning within that domain (see figure 9). Textnet has over 80 types [Conklin 87a], while CREF has 4 types: references, summarizes, supersedes, precedes [Conklin 87a] corresponding to referential, hierarchical, versional, and linear links, respectively.
One of the most critical attributes of links is that link traversal should be "light weight". That is to say that link traversal should be undertaken lightly and easily by the user. To do this the traversal command must be very simple (in most systems it is just a mouse click), and the traversal should be very fast (less than one second [Conklin 87a], [Shneiderman 89], [Akscyn 88]). However, not all link traversals can really be this fast, especially in systems using distributed databases. Conklin suggests that the look of the link should be suggestive of the speed of the link, although he does not give examples of where this idea is actually used [Conklin 87a]. Another idea used in Hyperties [Shneiderman 89] is to display some summary information about the destination before actually following the link so that the user can better decide whether to traverse the link before he actually does. Hyperties can do this by displaying a 5 to 25 word message at the bottom of the screen with a hotword for the actual link traversal.
A path is a series of links defining a navigation through a hypertext database. Internet and the Electronic Document System implement a path as "NEXT" buttons on each node display that acts as a virtual link to the next node on the path. Exactly where the "NEXT" button leads is dependent on whether the user is a novice, intermediate, or expert [Yankelovich 85]. Paths may be constructed by the author ahead of time or may be defined by the user. For example, the navigation stack used by many systems (e.g.: Hyperties) to allow the user to "go back" is a user-specific path. Apple's Grolier project [Laurel 90] includes an interesting use of paths: User selectable, personified "guides" provide a default path through an American history hypertext database.
Many systems provide bookmarks for readers to mark locations in the database, and later quickly return to them. Typically, the bookmark command allows the user to associate an identifier with the current position in the database. The reader can later choose one of his/her identifiers from a menu to jump to the associated location. The Symbolics Document Editor, Winhelp (Microsoft Windows 3 help facility), and DECwindows Document Browser all provide bookmarks. Bookmarks are usually stored in a separate, user-specific file.
Links are usually fine for general browsing, but readers often consult books (and hypermedia by extension) for specific needs that cannot be predicted in advance by the author [Dvorak 92]. The author, therefore, cannot set hypertext links to cover all the possible ways a reader may be using the material. It follows that a reference hypertext document should provide facilities for search and query.
Further support for providing search and query facilities comes from the fact that readers often can't remember (or just don't know) where a particular piece of information is, but can describe it [Halasz 88].
Content search is the search of the text or attributes of nodes or links that returns a retrieval set of zero or more nodes. Content search can be divided into text body search and keyword search. Structure search is an idea detailed in [Halasz 88]. Structure search is search on the structure, or shape, of the links in the database. An example structure search is "find a node that is indirectly linked to itself by an unbroken chain of 'supports' links", which finds circular arguments. It seems likely that structure search will be too complex for the casual user to handle. I know of no systems that use structure search yet.
Hypermedia objects (nodes and links) must persist beyond the lifetime of the process that created them. There has to be some database in which hypermedia objects are stored for future retrieval. But hypermedia offers certain challenges to database systems (a more extensive discussion is offered in [Ishikawa 92]):
Retrieval must be very fast to encourage the user to follow links without hesitation [Conklin 87a].
The database must be able to store variably sized, complex objects including text, bitmaps and other graphics, sound, and video as well as combinations of these.
The database must be capable of storing hypermedia nodes and links without undue overhead to the author or system implementor.
The last two points need clarification. Hypermedia nodes have the potential to contain large and varied data types within them. Furthermore, nodes may be constantly changed, extended, or annotated. Hypermedia links are not exempt from this problem as links may also contain significant dynamic data and annotations. Hypermedia databases must be able to accommodate potentially huge entries as well as their subsequent changes and growth over time.
From the point of view of the hypermedia author, links must be extremely easy to create, since linking is the essence of hypermedia and should be encouraged by the system. Not to be neglected is the hypermedia system designer and implementor for these are the people who will be selecting the database and will work intimately with it. The designer and implementor should be able to treat persistent objects just like transient (non-persistent) objects. To force the programmer to deal with persistent and transient objects in two different data modeling paradigms is to invite disaster. Besides the obvious cognitive load, the programmer may not even be able to map the complex structures required for advanced applications into the simple models offered by traditional databases. This gap between the rich data models used in object-oriented programming languages and the simple structures representable in conventional database systems has been called the "impedance mismatch" [Joseph 91]. The translation from the programming language's modeling paradigm to the database's modeling paradigm can account for as much as 30% of the code in an application [Joseph 91]. This, and the obvious large potential for error in the translation is sufficient reason to choose a database system that allows for better integration of a programming language with the database system.
The hypermedia system designer is faced with the three basic choices (other than building a database from scratch):
Relational databases
Object oriented databases
Direct use of the file system
Relational databases do not adequately provide for hypermedia [Ishikawa 93], although some hypertext systems, such as WE [Conklin 87a] do manage to use relational databases anyway. Object oriented databases are probably ideal, but the technology is not yet mature.
One very practical approach to the database problem taken by HAM [Campbell 88] is to use the file system provided by the operating system to implement the hypertext database. The file system is used to a much greater extent than, say, normal databases. Each node is saved as a separate file, which incurs the significant overhead of a file open and close with each node access. The advantage of using the file system to this extent is that the file system already has hierarchy and a name space implemented, and allows arbitrary growth of objects (files). Some systems use the reliance on the file system to their advantage -- PlaneText [Conklin 87a] stores nodes as pure text files, and stores all links as file references in a separate file. PlaneText is, therefore, is a very useful tool for tasks such as program source code annotation, since link insertion does not affect the source file.
An interesting possibility is to combine use of the file system and the simplest form of object-oriented databases -- object I/O. Object I/O is not a true database implementation, but uses an object oriented programming language's class hierarchy to implement a method whereby the programming can have arbitrary object networks persist in the file system [Borland 91, Foster 90]. Thus, the hypertext system must establish a name space for coarse-grained objects (to correspond to the file system) but incurs very little overhead for object translation, storage, and retrieval.
In today's world of workstations and distributed processing, centralized, monolithic databases are becoming a thing of the past [Joseph 91]. Shared hypertext systems will be running on separate machines, and large databases need to be distributed among (possibly heterogeneous) machines. KMS uses a completely distributed database based on Unix file servers [Akscyn 88], while HAM solves the problem by not distributing the database but distributing the interface and using a database server (interfaces and the server communicate via a byte stream protocol) [Wiil 92]. The HAM-style distribution scheme has great potential to work in a heterogeneous environment but can make very heavy demands on the server.
Security issues include both data protection and concurrency control.
If it is to be widely used, a shared hypertext system needs to protect the integrity of the data from malicious or accidental corruption. KMS allows the owner (initially the creator) of a node to set public access to "read", "annotate", or "modify" [Akscyn 88]. HAM implements a more elaborate protection scheme where an access control list (ACL) is optionally associated with each object. The ACL contains pairs of groups and access permissions (access, annotate, update and destroy). Individuals gain specific access to the node only if they are members of a group with that specific permission [Akscyn 88].
In general, node contention is not a common occurrence in large hypertext systems. It is rare that two authors happen to be modifying the same node at the same time, because the database is generally large and the node size is quite small. However, any shared hypertext system must address the problem.
Before an element in the database is modified, it must be locked to prevent others from inadvertently overwriting the changes. The question is what constitutes a lockable element? KMS locks a complete node at a time [Akscyn 88]. EHTS provides finer-grained lock resolution, and locks on the bases of attributes (fields) within the node [Wiil 92].
At some point before node or link modification takes place, a user must place a write lock on the object. EHTS node modification requires the user to issue an explicit lock command before making any changes [Wiil 92]. But this is not necessarily required, since the system could automatically issue a lock when the user begins to modify a node. This last strategy entails some interface problems since it may take time to confirm a lock, and if the lock is declined, how is the system to gracefully inform the user that his/her changes must be aborted?
EHTS can optionally inform users when lock-related events occur. Users can choose to be informed when locks occur, when actual updates occur (so they may refresh the node display), when unlocks occur, and when nodes are deleted. Furthermore, users can request the identification of other users who hold particular locks [Wiil 92].
There is also the possibility of not locking nodes at all, but just letting (hopefully rare) conflicts happen. This is the strategy taken by KMS [Akscyn 88]. It is not so foolish as it may sound. KMS implements a branched version space (see section 2.2.5.), that is, when two authors make concurrent updates to a node, two separate new versions of the node are saved. The two authors can later collaborate to merge the two nodes. It is possible that the system itself could check for conflicts in the two updates, and if there are none, it could transparently perform the merge itself. Unfortunately, automatic merges are very difficult to implement, particularly for non-pure-text nodes.
A more fine-grained approach to the concurrency problems is exemplified by GroupDraw [Greenberg 91]. GroupDraw is not a hypertext system, but it easy to see how the concepts could be used in a hypertext system. GroupDraw allows multiple workers, each at their own workstation to share the same "white board" (or node display). All users' cursors are displayed on all users' screens, and each can see the other's updates and object manipulations in "real time". Locking is implemented in an extremely fine grain, so it goes virtually unnoticed by the user. A hypertext system based on this model would be very well received. But such a system would rely on fairly high bandwidth communication -- which may not be available in all situations. A similar system, GroupDesign [Beaudouin-Lafon 92], uses less communication bandwidth by not providing the real-time animation of GroupDraw, but instead providing icons over objects to show locks together with after-the-fact animation.
As hypertext databases evolve, should the changes be tracked? The motivation for storing old versions of objects in the database comes not only from archival interests, but also from the perspective of error recovery, distributed system update conflicts, and internal document compatibility.
The version space of a hypertext database can be linear
or branched. Linear versioning systems maintain a simple
list for each object, with the most recent version at the head,
and progressively older versions following. Branched versioning
is more complex and is used in systems that allow concurrent updates
to objects: more than one concurrent user update to a single object
will generate a split on the version list, one branch for each
version. Because locks cannot always be guaranteed, highly distributed
systems often require branched version spaces. KMS's use of opportunistic
concurrency control forces it to use a branched version space.
Although many interface topics have already been addressed, this section gathers together some interface-related topics that are not covered in other sections: graphical browsers, agents, metaphors, and filters.
Graphical browsers are available in many of the shared hypertext systems (EHTS, Intermedia, Neptune), but are much rarer in the single user systems (HyperCard, Toolbook, Hyperties). A graphical browser is a special node or facility that displays other nodes and their relationships (links). The IBIS discussion shown in figure 9 is an example of a graphical browser. The purpose of graphical browsers is to give users a "map" of their location in the database. However, complete graphs of large databases, especially if they are not well laid out, can be very disorienting themselves (see figure 10). This problem can be mitigated by pre-constructed subsets (assuming a static database), by filters (to reduce the total amount of information on the display), and by fish-eye views [Schaffer 93].
All graphics-based systems can support static graphical browsers, since the author can draw the network and link each icon to the appropriate node. But this entails a lot of work on the author's part, both originally and every time there is a change to the database. Since there is so much work involved, graphical browsers are rarely seen in systems that do not directly support them.
A variation on graphical browsers comes from Intermedia, where there is a special facility to graphically display a node with all the nodes linked to it on the left, and all the nodes it links to on the right [Yankelovich 85].
Automatically generated graphical browsers are notoriously difficult to read, because node placement and grouping usually lack semantic structure, that is, nodes do not get placed in a very meaningful way. Automatic node placement algorithms need to be much better than they are today. EHTS solves the problem by allowing user-specific "layout files" associated with graphical browsers. An individual user can semi-permanently arrange the nodes on a browser to his/her own taste [Wiil 92]. NoteCards' node placement is strictly automatic, but the user may add and delete nodes and edges in the graph [Halasz 88].
NoteCards' graphical browsers offer more power than strictly map viewing. Not only are the node icons shown in the graph active links to the respective nodes, but the users may enter a mode in which they may edit the underlying structure of the network [Halasz 88].
Agents are programs that act as "independent" entities within the computer environment. Here two agent implementations are discussed: guides (personified character agents), and Malone's user created agents (collections of rules).
Guides are personified agents in Apple's Grolier project -- an educational hypertext application on American history [Laurel 90]. Guides were tested in several forms from simple iconic representations to full motion video representation using human actors, but no form had any noticeable advantage over the others. The guides seem most useful to represent specific "points of view" about the events being presented. Guides also provide a "suggested" next node, and thereby implement a path (see section 2.2.2.1.5.) for the user, reducing the user's cognitive load. One can question the generality of such personified entities -- they may be acceptable in an elementary education context, but they may be seen as condescending or "childish" in other contexts.
Information Lens [Malone 89] and its descendants, Object Lens [Lai 88] and Oval [Malone 92] are not primarily hypertext systems, but they do have hypertext capability. They allow the user to create agents, composed of rules, to act when certain events occur, or when they are explicitly called. The agents are composed of collections of simple template-based rules that the end users can write relatively easily. These agents are primarily used for such tasks as screening and sorting electronic mail.
Filters are Boolean expressions that can be explicitly or implicitly specified by the user to hide nodes and/or links from the user's view of the database. By limiting the user's world, filters can work to mitigate the "lost in hyperspace" problem. An example is HAM's "visibility predicates" [Campbell 88] which extract subgraphs from large graphs of nodes. Simpler examples are NLS [Conklin 87a] and most outline processors that can clip levels in a hierarchy. Intermedia can use for filtering the same node and link keywords that it uses for searches [Yankelovich 85].
Most systems are excessively generic: the tools -- nodes, links, composites -- are clearly useful, but are not particularly well suited to any one task or style of use [Halasz 88]. Halasz, writing about NoteCards, gives a good example [Halasz 88]:
"... in a legal application the user might have entities such as cases, briefs, evidence, citations, etc. that need to be filed and interconnected in accordance with a standard set of legal relationships. To the casual user it is not obvious how to do this. Should each case be a text card or a filebox? Should evidence be stored in the same card as the case or in a separate card connected to the case by a link? What type of link?"
It is not clear to the user how to use the tools for a particular task.
Furthermore, the tools are too general for the system to make much semantic use of the information. There are notable exceptions to this, but these are all systems that confine themselves to specific domains. One exceptional example is IBIS [Conklin 87b], whose domain is issues and arguments.
This criticism is largely mitigated by systems that include full programming languages as an integral part of the system. Programmers can make use of the programming language to add domain functionality as needed. These systems include EHTS (Lisp) [Wiil 92], HyperCard (HyperTalk), Toolbook (OpenScript), and KMS [Akscyn 88]. For example, although Toolbook does not support link references to objects on a node or virtual links, these features can easily be added using the OpenScript language. Figure 11 shows the OpenScript text for a "hotwords" imbedded in text. Following these links causes the system to flip to the "bibliography" node, scroll down to the appropriate entry, and highlight it.
Attached to the "hotword":
to handle ButtonUp
send lookUp (text of self) to page References
end ButtonUp
Attached to page References:
to handle lookUp ref
put this page into current
go to page References
search page for ref as word
if "not found" is in sysError then
request """"&ref&""" not found in references" with "OK"
go to current
end if
end lookUp
Unfortunately, the functionality of the programming languages is usually out of reach for the casual user. No general purpose programming language is particularly easy for a non-programmer to use -- no matter how English-like the language designers attempt to make the language. Syntax, conceptual models, and keywords cannot be avoided. However, often the programmer can partially develop an application, providing tools for the casual user to further extend the application. It is easy to see how this is done for the Toolbook/bibliography example just given: the programmer adds code to the system, and users need only copy the hotword script wherever they need it.
Superficially, concept maps are merely two dimensional graphical networks consisting of labeled nodes with directed and/or undirected arcs connecting them. The supposed advantage of concept maps over plain text is that they should intuitively provide a more understandable, and easier-to-grasp description of complex ideas. But why should this be so?
Intuitively, many people resort to drawing diagrams on whiteboards, scrap pieces of paper, or napkins when trying to convey complex or hard-to-explain ideas. These diagrams often resemble concept maps. So here is weak evidence for the usefulness of concept maps.
Concept maps distinguish object types in a much more powerful way than plain text can. The labeled nodes can be differentiated according to type by display attributes such as color, fill pattern, shape, outline line style and color, size, and label font and size. The connecting arcs may be labeled or unlabeled and may be differentiated by type in the same manner as nodes. Typing of information in the subject domain may have a strong influence on understanding.
Concept map arcs can express multiple relationships between pieces of information that could be very hard to express clearly in plain text. Intuitively, labeled or otherwise typed arcs should be much more expressive than unlabeled arcs.
The layout of a concept map can be a powerful indicator of grouping or relatedness of objects within the domain, as well as showing ordering, hierarchy, dominance, containment, etc. Furthermore, layout can give a "gestalt" impression of symmetry, similarity, continuation, parallelism, and information gaps [Lambiotte 89].
Two human learning systems may be at work when observing a concept map: spatial (perceptual and "imagic") and verbal (syntactic and propositional) [Lambiotte 89]. Each system may contribute independently or interactively to processing.
Concept maps appear to be easier to learn, easier to understand, take less time to interpret, and provide a clearer transfer of information than formal textual techniques such as predicate logic [Nosek 90].
While the literature contains little hard evidence to support the contention that concept maps really do contribute significantly to understanding, there appears to be sufficient informal studies, subjective evaluations and prima facie validity to form compelling motivation for using concept maps in CSCW applications. The lack of hard evidence may be attributable to the short time that computer-based concept mapping systems have been generally available. Sufficiently powerful graphical workstations have only recently been available at reasonable cost. Before graphical workstations, concept maps were difficult to develop due to the difficulty and cost of incremental editing on hardcopy.
Lambiotte [Lambiotte 89] gives a taxonomy of map devices which may be summarized as per figure 12. Spatial Location maps include textual lists and tables. Node-based systems use typed nodes and may use links, but these are never typed. Link-based systems use typed links; but if nodes are used at all, they are not typed. Hybrid maps use the full expressiveness of the other three systems: spatial location, node typing, and link typing.
Concept maps have been used in a wide range of fields including education, artificial intelligence, knowledge elicitation, knowledge representation, organizational decision making, argument analysis and overview mapping of hypermedia systems. All these different domains use concept maps in varying degrees of formality. Nodes and links can be very strictly typed and limited to allow complete visual languages fully interpretable by the computer, as in Gaines' visual language interface to the KSSn expert system language [Gaines 91a]. Links are not labeled in this system but the syntax is restricted such that each link has an intrinsic type discernible from its anchor node types. These maps can be freely translated back and forth between the map format and the textual KSSn format, although users are often disappointed by the layout of maps translated from text -- evidence for the importance of spatial layout.
Slightly less formal is gIBIS [Conklin 87b], primarily aimed at the decision making domain, which allows three node types (Issue, Argument and Position) and a limited number of labeled links between them. Link types are also restricted by the types of their anchor nodes. gIBIS maps are not interpreted by machine, but the limited type vocabulary is seen as an aid to human understanding by reduced learning load.
Other systems impose no restriction on node and link type, either not encompassing the notion of type at all or allowing users to extend the type system arbitrarily. These systems are obviously not as amenable to automatic processing, nor can one expect such maps to be particularly meaningful to people who do not share the same type model with the map authors. Nonetheless, free type extension does have a certain appeal -- it is often very difficult to express an idea within a very restricted syntactic framework.
Concept maps support hypermedia applications as the basic node and arc layout exactly map onto hypermedia's node and link paradigm. Concept maps are used as representational views of the nodes in the hyperspace and the links between them. Concept maps are natural graphical browsers of hypermedia. EHTS [Wiil 92], Intermedia [Yankelovich 85], Neptune [Conklin 87a, Delisle 86] and many others all have concept map-like graphical browsers.
Because layout is so important to human understanding [Nosek 90, Lambiotte 89], concept maps should be editable by the users, and not exclusively laid out automatically by the program. In this way, users can create complete or partial views of the hyperspace that suggest the semantics of the knowledge in the hyperspace -- the view is more than the sum of the parts.
Hypermedia and concept maps are a natural combination: Besides being a map of the hyperspace, concept maps are a navigational aid if nodes act as references to the represented nodes (i.e.: the user need only "double click" on the concept map node to display the hypermedia node window). Here concept maps mitigate the "lost in hyperspace" (user disorientation) problem by providing an intuitive "point of reference" for the user.
Furthermore, the concept map can be used as a editing tool on the hyperspace: Changes made to the map are reflected in changes in the hyperspace (for example, "rubber banding" an arc from one map node to another creates a corresponding link in the hyperspace). A problem to be overcome is the intrinsic modality of concept map/hyperspace editing, that is, "Am I editing the view of the hyperspace or the hyperspace itself?" Overly modal systems tend to be disconcerting to users, particularly novice users [Thimbleby 90].
This chapter has briefly reviewed the CSCW, hypermedia, concept mapping literature. CSCW systems are classified by their synchronicity and locality, supported domains, control of social protocols, supported media, and the use of intelligent agents. Hypermedia systems vary on the definition and restriction of nodes, navigational aids, database types, security support, version control, auxiliary interface elements, and extendibility and tailorability. Concept mapping systems can be classified as node-based, link-based, or hybrid systems. They can further be divided on the basis of node and link typing. All three of these domains are closely related: Many hypermedia systems support groups, and concept maps are natural hypermedia browsers.
Chapter 3 will build on this foundation to sketch out the requirements
for Accord.