`
`Ever discovered after weeks of working on a software problem
`that your colleague downthe hall solved it months ago?
`What you probably needed was a system like this.
`
`
`A Browsing Approach
`
`to Documentation
`
`Yvan Leclerc, Steven W. Zucker, and Denis Leclerc, MeGill University
`
`There are those who would argue that the OS/360 six-foot
`shelf of manuals represents verbal diarrhea, that
`the very
`voluminosity of manuals represents a new kind of incompre-
`hensibility. And there is some truth in that.
`Frederick P. Brooks, Jr.!
`
`As Brooks implies above, the sheer volume of informa-
`tion required for research facilities to function makesthat
`self-same information both difficult to retrieve and dif-
`ficult to comprehend. His response to this Catch-22situa-
`tion (in the case of the [BM 360) was to compilea carefully
`organized set of manuals through which specific informa-
`tion such as the details of a programming language or the
`parameters of a subroutine could be easily found.
`While the time-honored technique of manually search-
`ing through extensive indexes does adequately allow for
`the retrieval of such information, it does notlend itself to
`the simple andleisurely discovery of that information. In
`other words,itis difficult to browse throughthe informa-
`tion in order to discover just whatis or is not available.
`Computerized documentation systems such as the VAX/
`VMS HELPfacilityoffer more flexibility in their infor-
`mation retrieval capabilities than hard-copy manuals, but
`they are not particularly well-suited to browsing either,
`The purposeofthis article is to describe one experimentin
`the design of adocumentation system that provides mech-
`anisms for both needs—retrieval and comprehension,
`The decision to design and implement a documentation
`system with browsing capabilities was made when we
`noticed that many membersof our laboratory’ tended to
`“reinvent the wheel’’ by needlessly duplicating the efforts
`of others in the laboratory. Even though these previous
`efforts were documented in various ways, most people
`were unaware that a particular topic (e.g., fast Fourier
`transforms or pseudocoloring of images) had even been
`explored by another member of the laboratory. Even
`
`“The McGill Universiy Computer Vision and Graphics Laboratory.
`
`fewer knew precisely what that other member had done.
`Also, wheneverit was known that a particular topic had
`been investigated by a particular person, the originalin-
`vestigator spent considerable time explaining exactly
`where the documentation for the topic was to be found
`and in furnishing generalinformation about the topic.
`We hoped that providing a documentation system thai
`allowed people to both discoyer and quickly retrieve in-
`formation about
`the resources of the laboratory (re-
`sources such as software and hardware documentation,
`technical reports, etc.) would alleviate the above prob-
`lems. (It is also our experience that these information dis-
`semination problems are not unique to our laboratory. In
`fact, they are more often the rule than the exception.)
`
`System design
`
`the primary goal of our browsing
`As stated above,
`system was to provide a means for browsing through
`and/or quickly retrieving information about the labor-
`alory's resources. Our needs, however, dictated that the
`implementation, and especially the maintenance, of the
`system require a minimum of manpower and on-line
`storage,
`
`Accessibility, Since executable programs are an impor-
`tant part of the resources ofthe laboratory, we felt that,
`ideally, the documentation system should be accessible
`from within other programs and that other programs
`should be accessible from within the documentation
`system. For example, the former might be useful when
`editing a program (e.g., to find the parameters of an ex-
`ternal subroutine) and the latter would allowa person to
`discover what programsareavailable without leaving the
`environmentof the documentation system. Both capabil-
`ities are provided in our current implementation.
`
`(OE-9162/K2(0600-004650.75 & 19K? IEEE
`
`COMPUTER
`
`(cid:20)
`
`PETITIONERS - EXHIBIT 1012
`PETITIONERS- EXHIBIT 1012
`
`IPR2022-00217
`
`IPR2022-00217
`
`

`

`Information organization. A capability for browsing
`requires both an appropriate presentation of individual
`items of information and an organizational context to
`facilitate the browsing. The first need was met by naming
`each item of information explicitly so that it could be
`retrieved immediately onceits name was located. In other
`words, each item of information, be it an executabie pro-
`gram or some form of text, was assigned one or more
`keywords. The second need was met by making each entry
`short—short enoughto allow a large numberof them to
`fit on one page of a normal display terminal—and these
`keywords were then embedded in a structure whosecate-
`gory names were also keywords.
`is, a
`We chose a multiple-parent hierarchy (that
`directed acyclic graph with a single root node) as the
`structural organization of the keywords. We did this
`because of the simplicity and flexibility of this type of
`organization. A strict hierarchy was considered too in-
`flexible because it forces each keyword entry to be placed
`in a specific category. This oftenleads to difficulties both
`in searching andin categorizing information. At the same
`time, an arbitrary network of keywords, although quite
`flexible, is difficult for a person to grasp and follow. The
`compromise of a hierarchy with multiple parents allows
`items of information to be found through multiple paths,
`yet it
`is simple enough that traversal of the graph is
`natural.
`
`Thus, for example, a general-purpose image-displaying
`program can be categorized under both IMAGE PRO-
`CESSING and GRAPHICS using a multiple-parent
`hierarchy, rather than under just one or the other as
`would be necessary with a strict hierarchy. Asa result, the
`program can be found moreeasily, especially if the person
`searching for the program is not really sure where it
`belongs.
`
`Human interface. One constraint on our design of the
`humaninterface to the browsing system was the require-
`mentthat it be usable from astandard video terminal with
`minimal graphic capabilities. Inspired by the standard
`Lisp pretty-printed form ofdisplayinglists, we chose the
`indented form of displaying a hierarchy illustrated in
`Figure 1. The desire for quicktraversalof the graph led to
`single keystroke commands, whicharelisted at the bot-
`tom of the screen as a reminderto the user.
`Figure 2 illustrates the initial display of the browsing
`system. The design of the human interface was also in-
`spired,in part, by an application of the Zog system?"4 to
`browsing through books and technical reports.‘ In fact, a
`version of the browsing system could have been im-
`plemented in Zog, but
`this conflicted with our
`re-
`quirementsfor simplicity of implementation andefficien-
`cy of computation. Interested readers can find further
`details of the issues of a documentretrieval language in
`Gebhartand Stellmacher.® Note that only one level of the
`hierarchy is initially visible in Figure 2, althoughellipses
`indicate that further levels exist. This is to simplify the
`user’s initial view of the system, but the display can be
`changed to view up to four levels of the hierarchy
`simultaneously. If the displayed hierarchy does notfit
`
`$1.4
`
`$1.2
`
`Si.1.1
`
`81.1.2
`
`$1.21
`
`81,22
`
`$1.23
`
`Figure 1. (a) A small hierarchy. (6) The same hierarchy
`displayed in the Indented form used In the browsing
`system.
`
`Press ‘'i'’ for information.
`
`| L
`
`(a)
`locate next page run sons top
`
`Separation of organization and information. The
`hierarchy of keywords described above is kept
`in a
`separate network file, with the information associated
`with each keyword pointed to byfile names. The network
`file basically contains a doubly linked list of variable
`length records containing the keyword name,the associ-
`ated file name, and pointers to the fathers and sonsofthe
`keyword. The simplicity of this structure is possible
`primarily because the text information is kept separate
`ATEST ENTRIES. . .
`from the organization.
`AREAS OF RESEARCH...
`There are other important advantagesin storing the in-
`SUPPORTED SOFTWARE. .
`AVAILABLE HARDWARE. . .
`formation separately from the hierarchy:
`REPORTS & THESES...
`DEMONSTRATION PROGRAMS...
`.
`(1) Once a keyword has been entered for a particular
`PEOPLE POINTERS. .
`item of information, the information can be updated by
`SUGGESTION BOX ,
`the person responsible without
`the intervention of a
`“‘librarian.”’
`(2) Information need not be modified in any way to be
`incorporated into the browsing system.
`(3) The information can be created independently of
`the system without the need for special editors, thereby
`reducing the implementation cost.
`(4) Since informationis not stored explicitly, the struc-
`ture is relatively small and can be quickly and efficiently
`traversed by the system, allowing quick traversal of the
`graph bythe user.
`
`back exit father generations help information
`
`Figure 2. Theinitial display of the browsing system. The
`ellipses following the keywordsindicate that the keyword
`has sons. Attached to each of these keywordsIs an ar-
`bitrary text file, which can be retrieved by moving the
`pointer (currently pointing to the topmost keyword)to the
`appropriate keyword and then pressing “I.” The set of
`available commands are listed at the bottom of the
`screen,
`
`June 1982
`
`47
`
`(cid:21)
`
`

`

`SUPPORTED SOFTWARE
`|
`CHARACTER STRING MANIPULATION
`DISCARDING TRAILING BLANKS
`FILE NAME MANIPULATION
`FREE FORMAT DECODING...
`KEYWORD MATCHING
`TRANSLATING CASES
`CVAGL UTILITY PROGRAMS
`DISPLAY
`PRETTY__PRINT
`SCANNER
`TEST PATTERN GENERATOR
`TYPE_VIDEO
`GRAPHICS
`.
`PROGRAMS.
`SUBROUTINES.
`HUMAN ENGINEERING AIDS
`KEYWORD MATCHING INPUT STREAM
`VIDEO TERMINAL OUTPUT
`IMAGE PROCESSING
`PROGRAMS
`SUBROUTINES
`SYSTEM UTILITIES
`back exit father generations help information
`
`Figure 3. Twolevels of the keyword “SUPPORTED SOFT-
`WARE.” The “MORE...” indicates that the two levels
`could not fit completely on the screen. This display was
`obtained by using the “generations” command preceded
`by the number“2.” (Optional numeric arguments,as for
`the “generations” command, appear after the “‘n =” of
`the top line of the display.)
`
`completely on the screen, the user can scroll the display up
`or down.
`
`Figure 3 illustrates a case in which twolevels of a hier-
`archy are displayed simultaneously, while Figure 4 shows
`the displayed hierarchy scrolled dawn several
`lines.
`(Figure 4 also illustrates the multiple-parent hierarchy
`
`locate next page run sons top
`“Thesé commands have an optional numeric: argument entered prior to the command.
`
`Add
`Back
`Create
`Delete
`“downarrow’!
`Exit
`Father
`Generations
`Help
`Information
`Kill link
`Locate
`Modify
`Next
`Page
`Quit
`Run
`Sons
`Top
`“uparrow'*
`Update
`9
`
`- Add the Input node to the network as the son of the *—"' node.
`- Move the '’—"* back. one page (22 lines) when passible
`- Create a new node(call this the Input node).
`~ Delete the '‘—"* node andall nodesisolated by this deletion,
`* Move the *— °° downwards (when not available, use linefeed)
`- Exit from the program, saving all modifications ina new file,
`~ Go to the father (super-category) of the current node.
`* Specifies depth of subcategories seen simultaneously. Max (4).
`- Print this message,
`~ Print the information associated with the *'—°’ node,
`~ Kill (delete) the tink from the Input node to the “‘—'' node
`- Search for the first match of the specified string in the net.
`~ Modity the **—"" node and makeit the new Input node.
`~ Searchfor the next match of the string in the net.
`- Move the '"—"" forward one page (22 lines) when possible.
`~ Exit from the program without creating a newfile,
`- Run the program associated with the “'—‘' node.
`~ List the sons (subcategories) of the ‘*—"" pode,
`~ Go to the top of the tree.
`* Move the **—"' upwards (when notavailable, use backspace).
`~ Update the network file,
`~ Print the namesof the files associated with the ‘‘~"' node.
`
`Figure 5. Asummary of the commandsavailable in the browsingeditor.
`Note thatall of the commandsofthe browsing system are also com-
`mands of the browsingeditor.
`
`48
`
`(cid:22)
`
`locate next page run sons top
`
`SUPPORTED SOFTWARE
`TRANSLATING CASES
`CVAGL UTILITY PROGRAMS
`DISPLAY
`PRETTY__PRINT
`SCANNER
`TEST PATTERN GENERATOR
`TYPE_VIDEO.
`GRAPHICS
`PROGRAMS. . .
`SUBROUTINES. .-
`HUMAN ENGINEERING AIDS
`KEYWORD MATCHING INPUT STREAM
`VIDEO TERMINAL OUTPUT...
`IMAGE PROCESSING
`PROGRAMS...
`SUBROUTINES, .
`SYSTEM UTILITIES
`COMMAND LANGUAGE INTERPRETER
`VIDEO TERMINAL OUTPUT
`MCG__TERM__TYPE
`NEW__PAGE
`PRINT__HELP. . .
`-
`back exil father generations help intormation
`
`Figure 4. Twolevels of the keyword “SUPPORTED SOFT-
`WARE”scrolled downseverallines. Noticethat the arrow
`now points to the keyword “PRINT_HELP” and that the
`system is indicating that more of the hierarchy can be
`displayed by the two symbols “MORE...”
`
`the keyword ‘‘VIDEO TERMINAL
`concept;
`OUTPUT” is a son of both ‘SUPPORTED SOFT-
`WARE" and ‘HUMAN ENGINEERING AIDS.”’)
`The user moves down the hierarchy by moving the
`pointer (in the top left-hand corner of Figure 2) up or
`downon the screen to the desired keyword, typing “‘s"' to
`view its sons. The user can move upthehierarchyonelevel
`al atime (retracing his or her stepsdown the hierarchy), or
`can movedirectly back to the top. The user can also locate
`a specific keyword byentering either a full keywordorits
`abbreviation. The browsing system then searches for the
`first matching keyword from the top ofthe hierarchy(us-
`ing a depth-first search). If the matched keywordis not
`the one the user wanted, he or she can force the system to
`go on to the next match.
`Once the user has placed the pointer at an appropriate
`keyword, the associated information can be displayed on
`the screen or the associated program run. The user can
`always return to the browsing system via a control
`character, giving him or her the freedom to experiment.
`
`Creating and modifying a network. Any user cancreate
`and modify a personal browsing network, although a
`passwordis required to modify the (default) system net-
`work, A different program is used for this, one that is a
`superset of the normal browsing system, In other words,
`every commandin the browsing system is also available in
`the browsing editor, along with extra commands to
`create, insert, delete, and modify keyword entries.
`There are two required steps for creating a new entry.
`First, a new nodeis created, specifying the keyword name
`and the associated text and/or executablefile name(s).
`
`COMPUTER
`
`

`

`References
`
`Second, the new nodeis added to the network as the son
`of one or more other nodes. Once anode has been entered,
`its keyword name and/orfile name can be modified andit
`1, F. P. Brooks, Jr., The Mythical Man-Month—Essays on
`Software Engineering, Addison-Wesley, Reading, Mass.,
`can be moved about the networkat will by removing and
`1975, p. 134.
`addinglinks fromit to other nodes. Figure5lists the com-
`2.
`“WAX/VMS Command Language User's Guide,"
`mandsavailable for doing this in the browsingeditor.
`AA—DO023B-TE, Digital Equipment Corporation,
`The approach weused in building the system network
`Maynard, Mass., 1980.
`was to proceed from the abstract to the concrete. The top
`3. G. Robertson, A. Newell, and K. Ramakrishna, ‘‘ZOG: A
`level of the hierarchy is the most abstract, representing
`Man-Machine Communication Philosophy,’’ Carnegie-
`various points of view that a user might have whenenter-
`Mellon University Technical Report, Carnegie-Mellon
`ing the system. For example, a personinterested in seeing
`University, Pittsburgh, Pa., Aug. 5, 1977.
`the type of research carried on in the laboratory might
`4. G. Robertson, D. McCracken, and A. Newell, ‘‘The ZOG
`start searching through the “‘AREAS OF RESEARCH”’
`Approach to Man-Machine Communication,’ Carnegie-
`Mellon University Technical Report, Carnegie-Mellon
`keyword; a visitor to the laboratory might first search
`University, Pittsburgh, Pa., Oct. 23, 1979.
`through the
`“‘DEMONSTRATION PROGRAMS”
`5. M.S. Foxand A.J. Palay, “‘The BROWSESystem, PartI:
`keyword to get a glimpse of the current work; while a
`An Introduction,’ Computer Science Department,
`veteran user might be more inclined to start with the
`Carnegie-Mellon University Technical Report, Carnegie-
`**L ATEST ENTRIES” keyword to see what has recently
`Mellon University, Pittsburgh, Pa., 1979.
`been added to the network.
`6. F. Gebhart and I. Stellmacher,
`‘‘Design Criteria for
`As a user moves down the hierarchy, the keywords
`Documentation Retrieval Languages,"’ J. Am. Soc. Infor-
`becomeincreasingly more specific, with the lowest-level
`mation Science, Vol. 29, No. 4, July 1978, pp. 191-199.
`keywords typically pointing to programs, subroutine
`sources,
`technical
`reports, etc. The multiple-parent
`feature of the system was used extensively to allow
`keywords to be found through a variety of paths, easing
`the discovery of information by the user.
`
`Conclusions
`
`The browsing system has been implemented as de-
`scribed in this article. To date, it has been used primarily,
`though notexclusively, to documentsoftware developed
`in our laboratory. This has been done in conjunction with
`a prior commitmentto the use of a standard header page
`preceding every piece of software created in our labratory.
`Thus, for the mostpart, the browsing system is pointing to
`files starting with a standard header page, which makes for
`a consistent view of the available software.
`The system has been very helpfulin alleviating needless
`duplication of effort by providing a meansfor discover-
`ing, in a simple manner, what other people have done.
`And, perhaps more importantly, the development and
`maintenance costs were quite reasonable (two to three
`man-monthsfor designing and implementing the system,
`with another man-month for organizing the information
`in the network), demonstrating the feasibility of im-
`plementing useful documentation systemsat areasonable
`cost. When these costs are compared with the time that
`our expert users no longer have to expend to simply
`disseminate information, the investment seems eminently
`worthwhile. In short, the system is working as planned.
`
`
`
`
`* Yvan G. Leclere is currently working
`toward a PhD in thefield of computervi-
`_ sion at McGill University. His research in-
` terests include computer vision, the char-
`acterization of local vs. global computa-
`tions, and cooperative processing. Other
`academic interests include the general
`study of humanintelligence (from both the
`& ».
`;
`2 af » psychological and artificial
`intelligence
`: A
`points of view), and the human engineer-
`ing of computer systems.
`Leclere received the M. Eng. and B. Eng. degrees in electrical
`engineering from McGill University in 1980 and 1977, respec-
`tively, He is currently a student memberof the IEEE and ACM.
`
`Steven W. Zucker is currently an associate
`professor in the DepartmentofElectrical
`Engineering, McGill University, Mon-
`treal, P.Q., Canada and is codirector of
`the Computer Vision and Graphics Lab-
`oratory there. His research interests in-
`clude computer vision, human perception,
`'_ andartificial intelligence. He received the
`cc 2— BS degree in electrical engineering from
`
`_ Carnegie-Mellon University in 1969, and
`¥
`i
`the MS and PhDdegrees in biomedical engineering from Drexel
`University, Philadelphia, in 1972 and 1975, respectively.
`From 1974 to 1976 he was a research associate at the Picture
`Processing Laboratory, Computer Science Center, University of
`Maryland, College Park.
`Zucker is a member of Sigma Xi, ACM, and the IEEE.
`
`Acknowledgments
`
`The authors are grateful to John Mohammed, David
`Kashtan, Harold Hubschman, and Peter Sanderfortheir
`help in designing the browsing system, and for their
`critical commentsand helpful suggestions concerningthis
`article.
`This research was supported in part by NSERC grant
`number A4470 andin part by the Quebec Department of
`Education.
`
`
`
`Denis Leclerc is currently in the master’s
`degree program in computer science at
`McGill University, working in the program-
`ming languages area. Heis also working
`part-time at Bell Northern Research on a
`text-to-speech conversion system. His re-
`_
`search interests are programming lan-
`_ guages, compiler optimization, and natural
`language understanding. He received the
`BSc degree in mathematics and computer
`science from McGill University in 1980.
`
`June 1982
`
`49
`
`(cid:23)
`
`