(12) United States Patent
`Jones et al.
`
`US006199098B1
`US 6,199,098 B1
`Mar. 6, 2001
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR
`PROVIDING AN EXPANDABLE,
`HIERARCHICAL INDEX IN A
`HYPERTEXTUAL, CLIENT-SERVER
`ENVIRONMENT
`
`(75) Inventors: Kirsten Lynn Jones; Katherine Ellis
`Weber, both of San Jose, CA (US)
`
`(73) Assignee: Silicon Graphics, Inc., Mountain View,
`CA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 08/606,364
`(22) Filed:
`Feb. 23, 1996
`
`(51) Int. Cl.7 ................................................. .. G06F 15/163
`(52) us. Cl. ........................ .. 709/203; 709/310; 707/501;
`707/513; 707/514
`(58) Field of Search ............................. .. 395/200.01, 776;
`707/501, 513, 514; 709/203, 310
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,495,607 * 2/1996 Pisello et a1. ........................ .. 707/10
`5,572,643 * 11/1996 Judson ............................... .. 709/218
`5,625,781 * 4/1997 Cline et a1. ........................ .. 345/335
`
`OTHER PUBLICATIONS
`
`Berners—Lee, Tim, et al., “The World—Wide Web,” Commu
`nications of the ACM, Aug. 1994, vol. 37, No. 8.
`PutZ, Steve, “Interactive Information Services Using
`World—Wide Web Hypertext,” Computer Networks and
`ISDN Systems, Nov. 1994, vol. 27, No. 2.
`Perrochon, Louis, “Translation Servers: Gateways Between
`Stateless and Stateful Information Systems,” Institut fur
`Informationssysteme, Eth Zurich.
`
`(List continued on next page.)
`Primary Examiner—William M. Treat
`(74) Attorney, Agent, or Firm—Staas & Halsey LLP
`
`(57)
`
`ABSTRACT
`
`Amethod and apparatus are provided for navigating through
`electronically stored information using an expandable, hier
`archical index or TOC, in a hypertextual client-server net
`work environment such as the World Wide Web. The client
`server network comprises at least one client computer
`coupled by network link to at least one server computer. In
`accordance with the invention, a publisher of the TOC
`provides to the server a digital speci?cation of the TOC,
`de?ning the TOC as a plurality of hierarchically related
`nodes. In a preferred feature of the invention, the digital
`speci?cation includes a unique name, a display label, and a
`hierarchial level for each node of the TOC, and an optional
`target URL for each leaf node of the TOC. Using a browser
`program or the like at the client computer, an end-user
`transmits a network request including an address path to the
`server. Upon receiving the network request, and based upon
`the address path and the digital speci?cation, the server
`dynamically generates a network page specifying display of
`a hierarchical portion of the TOC entries. This network page
`is transmitted from the server to the client, for display to the
`end-user. In another feature of the present invention, when
`the server dynamically generates the network page, it
`assignes a path address as a hypertextual link for one or
`more of the TOC nodes in the hierarchical portion of the
`TOC to be displayed. The path address speci?es a modi?ed
`display status for the TOC entries that are hierarchical
`descendants of the at least one TOC entry. In this way, the
`present invention can preferably be used to provide an
`interactively expandable TOC in a client-server environ
`ment. When an end-user, utiliZing a browser of the client,
`interactively selects one of the currently displayed TOC
`nodes, the assigned hypetextual link will automatically be
`transmitted to the server as part of a new network request,
`and will cause the server to dynamically generate a new
`network page specifying a modi?ed display status for TOC
`nodes that are hierarchical descendants of the selected node,
`thus effectively expanding or contracting the TOC hierarchy
`beneath the selected node. In this way, the TOC hierarchy
`can interactively be expanded or contracted in an incremen
`tal fashion, with the current display state of the TOC being
`represented in portions of each hypertext path address.
`
`11 Claims, 8 Drawing Sheets
`
`matwoxk. 1m:
`
`(HTML pzge>
`145
`
`001
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`US 6,199,098 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Wolf, Gary, “Steve Jobs: The Next Insanely Great Thing,”
`Wired Magazine, Feb. 1996.
`Sarah Baker, “Mosaic—sur?ng at Home and Abroad”, Pro
`ceedings of the 22ndACM SIG UCCS Conference on User
`Services, pp. 159—163, 1994.*
`Mukherjea et al., “Visualizing the World—Wide Web With the
`Navigational
`VieW
`Builder,”
`Technical
`Report
`GIT—GVU—95—09, Graphics, Visualization and Usability
`Center, College of Computing, Georgia Institute of Tech
`nology, Mar. 1995, 14 pages.*
`Mukherjea et al., “Visualizing Complex Hyperrnedia Net
`Works through Multiple Hierarchical VieWs”, Technical
`Report GIT—GVU—95—08, Graphic, Visualization and
`Usability Center, College of Computing, Georgia Institute of
`Technology, Mar. 1995, 7 pages.*
`Ayers et al., “Using Graphic HIstory in BroWsing the World
`Wide Web”, Technical Report GIT—GVU—95—12, Graphics,
`Visualization and Usability Center, College of Computing,
`Georgia Institute of Technology, May 1995, pp. 1—14.*
`Jakob, Nielsen, “The Art of Navigating Through Hypertext”,
`Communications oftheACIl/I, vol. 33, No. 3, Mar. 1990, pp.
`297—310.*
`
`Frank G. Halasz, “Re?ections on Notecards: Seven Issues
`for the Next Generation of Hyperrnedia Systerns”, Commu
`nications of the ACIVI, vol. 31, No. 7, Jul. 1988, pp.
`836—852.*
`al., “Case Study. Visualizing Internet
`Gershon et
`Resources”, Proceedings. Information Ifisualization, IEEE,
`Oct. 30—31, 1995, pp. 122—128, 151.*
`Eick et al., “Visualizing the Internet: Putting the User in the
`Driver’s Seat”, Proceedings: Visualization ’95, IEEE, Oct.
`29—Nov. 3, 1995, pp. 416—421.*
`Mitchell et al., “Case Study: Fishing for Information on the
`Internet”, Proceedings. Information Ifisualization, IEEE,
`Oct. 30—31, 1995, pp. 105—111, 149.*
`Hendley et al., “Case Study. Narcissus: Visualizing Infor
`mation”, Proceedings. Information Visualization, IEEE,
`Oct. 30—31, 1995, pp. 90—96, 146.*
`K. AndreWs, “Case Study. Visualizing Cyberspace: Infor
`rnation Visualization in the Harmony Internet BroWser”,
`Proceedings. Information Ifisualization, IEEE, Oct. 30—31,
`1995, pp. 97—104, 147—148.*
`
`* cited by exarniner
`
`002
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 1 0f 8
`
`US 6,199,098 B1
`
`FIG. 1A
`-=-| Netscape: Support and Services at Silicon Graphics
`File Edit View Go Bookmarks Options Directory
`
`?nd
`—?
`a"
`©
`Find
`W
`t
`0%
`Flelocad
`E?ck
`/
`Netsite: I http: / /maelstrom. csd/nifnav . cgi/
`ll What's New IHIWhats Cool ||ll Handbook |||| Net Search ]||| Net Directory IlllWeloome ||
`
`Finding Support Resources
`We've organized the SGI Support Information available via the web in several different w
`help you find the information you want as easily as possible. Let us know what you think!
`By Topic ~ ~ By Task ~ ~ By Type
`
`mm 120 ---------
`
`[3M
`SEEM
`CUM ___________ __:
`
`'
`
`003
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 2 0f 8
`
`US 6,199,098 B1
`
`FIG. 1B
`'=-| Netscape: Support‘ and Services at Silicon Graphics
`File Edit View Go Bookmarks Options Directory
`Open % Prmt I
`9
`It %
`Home
`Reload
`Netsite; I http: / / maelstrom. csd/niftnav/niftnav . cgi/top’ic/HVWO
`H Whats New "What's Cool |||| HandbooklIIl Net Search III] Net Directory IIIIWeIoome II
`
`
`
`<30 Back
`
`.
`
`Find
`
`/110
`
`help you tind the intormation'ylou want as easily as possible. Let us know what you think!
`
`Bv Tonic ~ ~ Bv Task ~ ~ Bv Tvoe
`
`@ Hardware 120
`
`_ _ _ _ _ - _ _ _ _ _ _,
`
`[3 Systems
`5
`[3W
`[:1 Boards/Cards
`@125
`
`U Disks
`
`U TaQe Drives
`[3 IndyCam
`
`QM 130
`[j Graghics
`
`C] Multimedia
`
`004
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 3 0f 8
`
`US 6,199,098 B1
`
`FIG. 1C
`=1 Netscape: Suppon‘ and Services at Silicon Graphics
`File Edit View Go Bookmarks Options Directory
`' g 00 ‘
`%
`Open
`
`Emmi-1:
`
`110
`
`a
`a
`'
`Pnnl
`Find
`’ /
`Netsitej I http: / /maelstrom. csd/niftnav/niftnav . cgi/topic /HW/SW#0
`ll Whats NevTlIlNVhat's Cool "II HandbooYlIll Net Searcr?lllNet Directory IIIh/Veloome H
`‘3 Hardware 120
`[3 In General
`
`-------- '1
`
`'
`
`125
`
`[3 Systems
`[j Microprocessors
`Q Boards/Cards
`[312%
`U Tape Drives
`
`C] lndyCam
`
`--------
`
`a Software 130
`
`E] In General [j Ooeratinq Systems/Desktops [3 Applications _______
`
`
`
`
`
`
`
`C] Software Development
`
`C] Standards
`[:1 Graphics
`C] Multimedia
`
`135
`
`.......... -E
`
`005
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 4 0f 8
`
`US 6,199,098 B1
`
`FIG. 1D
`
`l=t Netscape: Support and Services at Silicon Graphics
`File Edit View 60 Bookmarks Options Directory
`
`55-?
`Print
`
`[CPU
`Find
`
`Netsi’tej http: / / maelstrom. csd/niftnav/niftnav . cgi/topic/IflW/SW/HMWO
`
`What's New IIIIWhat‘s Cool |||| Handbook Ill Net Search IHI Net Directory ||||Welo0me 1|
`
`mm 120
`
`_________ -_
`
`@MLQ 130
`
`
`
`[3W ......... [j Ooeratinq Svstems/Desktops
`
`E
`
`:
`
`ritetmcm
`[3 Software Development
`
`i135
`
`_L
`CD
`_
`
`[3 Standards
`
`......... _.
`
`
`
`Qmrm [plum
`
`_________
`
`006
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 5 0f 8
`
`US 6,199,098 B1
`
`FIG. 1E
`1:1] Netscape: Support and Services at Silicon Graphics
`File Edit View Go Bookmarks Options Directory
`
`@ Reglgd
`
`Netsite: Ihttp://mae1str0mcsd/ni?rrtav/nt?navogt/topic/sw/sWST'D/swS'IDvRii?
`II Whats Newil ll What's Cool [III Handbook ||l| Net Search llilNet Directory ||||We|oome]|
`
`[110
`
`'
`
`B Hardware 120
`
`a Software 130
`
`--------
`
`I
`
`Q In General
`
`--------
`
`Q Ooeratind Svstems/Desktoos l
`
`
`
`m Agglications [3 Software Development
`
`135
`
`'
`
`@ Standards
`
`am
`White Pagers 140
`
`[j OQGHGL
`E] Ogenlnventor
`
`.........
`
`[j Graghics
`[3 Multimedia
`
`007
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 6 0f 8
`
`US 6,199,098 B1
`
`Display
`Monitor
`
`i
`CPU, storage, and
`system software 130 1
`
`- - _ - _ - n _ _ - u - w - - n - - _ _J
`
`5 Browser 120
`
`a
`
`network link
`135
`
`<HTM|_ page>
`145
`
`<HTI'P requesb
`140
`
`r - - — - - — - - - - - - - - - - I
`
`r - - - - - - - - - — - - — — - - - - - -l
`
`5 Definition File 190
`
`:system software 170
`
`008
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 7 0f 8
`
`US 6,199,098 B1
`
`FIG. 3
`300w CREATE STRUCTURE
`DEFINITION FILE
`
`I
`310x CREATE CGI SCRIPT
`
`II
`320 x TFIANSMIT HTTP
`REQUEST
`
`II
`3301 EXECUTE SCRIPT, CREATE
`NEW WEB PAGE
`
`II
`340 \ TRANSMIT NEW WEB
`PAGE TO CLIENT
`
`350\
`
`II
`DISPLAY NEW
`WEB PAGE
`
`360w
`
`II
`EXECUTE SCRIPT,
`GENERATE WEB PAGE
`
`370
`
`LEAF NODE
`
`USER SELECTS:
`
`II
`
`FIETFIIEVE NON-TOC
`INFORMATION
`
`NON-LEAF NODE
`
`009
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`U.S. Patent
`
`Mar. 6, 2001
`
`Sheet 8 0f 8
`
`US 6,199,098 B1
`
`FIG. 4
`400 A PROCESS PATH_INFO:
`SET llDEEPEST LEVEL": 1
`
`GET NEXT NODE IN SDF
`
`NO
`
`THE NODE
`OPEN?
`
`440 ’\
`
`ADD TO OPEN LIST
`
`V
`445“ INCREASE "DEEPEST LEVEL"
`
`ADD LABEL TO WEB PAGE
`
`T
`465 “ GENERATE URL, ADD TO WEB PAGE
`
`010
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`US 6,199,098 B1
`
`1
`METHOD AND APPARATUS FOR
`PROVIDING AN EXPANDABLE,
`HIERARCHICAL INDEX IN A
`HYPERTEXTUAL, CLIENT-SERVER
`ENVIRONMENT
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer technology for
`navigating through electronically stored information using a
`hierarchical index or table of contents, in a hypertextual
`client-server netWork environment such as the World Wide
`Web.
`
`BACKGROUND
`
`Navigation is one of the primary interface challenges for
`information providers. If an information structure is not easy
`to navigate, the user may become frustrated and move on
`Without ?nding the desired data. There are at least tWo major
`paradigms for navigating through on-line information. The
`?rst, keyWord searching, is relatively easy to support in a
`typical client-server environment, such as the World Wide
`Web. The other, hierarchical index broWsing, is far more
`challenging to implement satisfactorily in a client-server
`netWork environment like the World Wide Web.
`By hierarchical index broWsing, We refer to providing
`interactive access to information through a hierarchical,
`tree-like, incrementally expandable table-of-contents
`(“TOC”). The expandable TOC is displayed to users on a
`computer screen, and as each node Within the TOC is
`interactively selected or activated by a user, the next level of
`information for that node is shoWn indented, directly beloW
`its “parent” node. Selected portions of the TOC hierarchy are
`thus expanded While maintaining the context of the rest of
`the tree. In this Way, users can explore selected portions of
`the TOC in greater detail, While maintaining the larger
`context of the overall structure. Ultimately, interactive selec
`tion by the user of a leaf node at the loWest level of hierarchy
`Within the TOC Will typically cause an associated document
`or set of information to be displayed for the user. The
`navigational paradigm of hierarchical index broWsing has
`been commonly used in a Wide variety of personal computer
`applications, but until noW has not been successfully real
`iZed in a client-server netWork environment like the World
`Wide Web, as Will be explained beloW.
`The World Wide Web (“the Web”) is a voluminous
`collection of hypertextually linked documents and informa
`tion distributed across Wide-area netWorks. The Web effec
`tively unites a diverse body of heterogeneous computers,
`alloWing the computers to exchange information using a
`standardiZed document language knoWn as HTML (the
`“HyperText Mark-up Language”). Each computer that is
`part of the Web can access an HTML document located
`elseWhere Within the Web basically in the folloWing manner:
`the computer seeking access runs a standard “broWser”
`program, Which formulates a request encoded in HTTP (the
`“Hypertext Transfer Protocol”) for accessing a desired net
`Work document, and transmits that request across a netWork
`to the computer on Which the document is stored. At the
`heart of the HTTP request is a URL (or “Uniform Resource
`Locator”), Which is essentially an address path identifying
`the computer Which hosts the desired document, and also
`identifying the document to that host computer. The host
`computer receives and parses the HTTP request, and
`responds by transmitting a copy of the document to the
`requesting computer. Assuming the document is Written in
`standard HTML, the recipient computer’s broWser Will
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`cause the document to be displayed appropriately on the
`recipient computer, even though the recipient and host
`computers may in fact represent heterogeneous computer
`platforms. In traditional client-server terminology, the com
`puter running the broWser program and issuing the request
`is the “client,” While the computer hosting the document and
`servicing the request for access is the “server.” For more
`information about the Web, see for example T. Berners-Lee,
`R. Cailliau, A. Loutonen, H. F. Nielsen, and A. Secret, “The
`World Wide Web,” Communications of theACM, vol. 37(8),
`August 1994.
`On the Web, effective navigational tools are of critical
`importance and value. HoWever, until noW, there has been no
`satisfactory implementation of hierarchical index broWsing
`for computer environments like the Web. Broadly speaking,
`that is because supporting an incrementally expandable,
`tree-like TOC requires some mechanism to capture and keep
`track of the current state of the TOC (i.e., Which nodes are
`currently expanded and Which are not). HoWever, uniform
`protocols like HTTP and HTML are generally stateless;
`indeed, they are intentionally simplistic, in order to better
`unify a diverse body of heterogeneous computers.
`Therefore, the conventional Wisdom has been that the
`limited, stateless environment of HTML and HTTP are not
`suitable for implementing more sophisticated navigational
`facilities such as true hierarchical index broWsing.
`Several navigational facilities have been developed in a
`compromise effort to capture at least some of the bene?ts of
`hierarchical index broWsing. One common approach is the
`“limited context” solution, Which Works as folloWs. When a
`node Within the hierarchical TOC is selected or activated, a
`neW page is displayed, containing only the information
`pertaining to that selected node. The node path information
`is often displayed at the top of the page, in an effort to
`maintain some contextual information for the current node.
`Nonetheless, this solution ultimately causes a context shift
`for the user, forcing the user into a restricted vieW of the
`overall TOC by removing relationships to other nodes at
`higher levels. This solution also requires separate pages to
`be maintained for each node and sub-node on the server. In
`another prior art solution, the “single-open” solution, users
`are alloWed to expand a single, selected node, While other
`Wise maintaining the original TOC structure in the display.
`HoWever, When a second node at the same level is selected,
`the ?rst node collapses. This unexpected behavior causes
`undesirable confusion, since there is no user-intuitive reason
`for imposing a limitation on the number of open nodes.
`Rather, the “single open” imitation is caused by the under
`lying implementation. One static page specifying the display
`of an expanded node is created for each node in the table of
`contents, and an appropriate one of those pages must be
`selected in response to the user’s interactive selection of
`TOC nodes. Thus, in order to support multiple open nodes
`using this prior art approach, the number of prede?ned static
`pages required Would increase logarithmically, Which Would
`be unWieldy and impractical for even relatively simple TOC
`hierarchies.
`Client-server broWsers that support more complex pro
`gramming languages like Java (from Sun Microsystems)
`may eventually alloW information providers to offer their
`users full-featured user interfaces comparable to those noW
`available in personal computer environments. HoWever,
`unless and until a language like Java becomes standard for
`all broWsers, netWorked communities like the Web must
`Work Within the limitations of existing, stateless broWsers, or
`else forfeit the bene?t of universal information access Within
`their community. Indeed, some visionaries in the ?eld have
`
`011
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`US 6,199,098 B1
`
`3
`argued forcefully against efforts to replace current browsers
`With more complicated and poWerful programming
`languages, on the grounds that universal compatibility for
`information exchange should not be compromised. Accord
`ing to this vieW, the simplicity of current broWsers is at the
`same time their greatest strength.
`What is needed is a methodology that provides true
`hierarchical index broWsing of hypertextual client-server
`documents, Without abandoning the simplicity of current
`broWsers and markup languages. Stated differently, What is
`needed is a practical implementation of hierarchical index
`broWsing in a current client-server environment like the
`Web, such that hierarchical TOC context is fully maintained
`at all levels for the user, Without requiring adjustments to
`standard netWork broWsers and Without adding unexpected,
`unWanted behaviors.
`
`SUMMARY OF THE INVENTION
`The present invention provides a method and apparatus
`for navigating through electronically stored information
`using an expandable, hierarchical index or TOC, in a hyper
`textual client-server netWork environment such as the World
`Wide Web. The client-server netWork comprises at least one
`client computer coupled by netWork link to at least one
`server computer. In accordance With the invention, a pub
`lisher of the TOC provides to the server a digital speci?ca
`tion of the TOC, de?ning the TOC as a plurality of hierar
`chically related nodes. In a preferred feature of the
`invention, the digital speci?cation includes a unique name,
`a display label, and a hierarchial level for each node of the
`TOC, and an optional target URL for each leaf node of the
`TOC. Using a broWser program or the like at the client
`computer, an end-user transmits a netWork request including
`an address path to the server. Upon receiving the netWork
`request, and based upon the address path and the digital
`speci?cation, the server dynamically generates a netWork
`page specifying display of a hierarchical portion of the TOC
`entries. This netWork page is transmitted from the server to
`the client, for display to the end-user.
`In another feature of the present invention, When the
`server dynamically generates the netWork page, it assignes
`a path address as a hypertextual link for one or more of the
`TOC nodes in the hierarchical portion of the TOC to be
`displayed. The path address speci?es a modi?ed display
`status for the TOC entries that are hierarchical descendants
`of the at least one TOC entry. In this Way, the present
`invention can preferably be used to provide an interactively
`expandable TOC in a client-server environment. When an
`end-user, utiliZing a broWser of the client, interactively
`selects one of the currently displayed TOC nodes, the
`assigned hypertextual link Will automatically be transmitted
`to the server as part of a neW netWork request, and Will cause
`the server to dynamically generate a neW netWork page
`specifying a modi?ed display status for TOC nodes that are
`hierarchical descendants of the selected node. In this Way,
`the TOC hierarchy can interactively be expanded or con
`tracted in an incremental fashion, With the current display
`state of the TOC being represented in portions of each
`hypertext path address.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1A illustrates the display of an expandable TOC,
`With a display state in Which all top-level nodes of the TOC
`are closed.
`FIG. 1B illustrates the display of an expandable TOC,
`With a display state in Which one of the top-level nodes of
`the TOC has been opened.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`4
`FIG. 1C illustrates the display of an expandable TOC,
`With a display state in Which another one of the top-level
`nodes of the TOC has been opened.
`FIG. 1D illustrates the display of an expandable TOC,
`With a display state in Which the ?rst one of the top-level
`nodes to be opened has noW been closed, While the second
`one remains open.
`FIG. 1E illustrates the display of an expandable TOC,
`With a display state in Which an open node is expanded
`several levels deeper.
`FIG. 2 is a high level architectural vieW of a preferred
`embodiment for the present invention.
`FIG. 3 is a How diagram of the major tasks performed in
`a preferred embodiment for the present invention.
`FIG. 4 is a How diagram of a preferred algorithm for
`dynamically generating Web pages for an expandable hier
`archical TOC, in accordance With the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A. De?nitional Note
`Herein We use the term “table of contents” (or “TOC”) in
`its broadest, most inclusive sense. Of course one example of
`a TOC is a traditional table of contents for a book or
`reference document, Which might be structured in chapters,
`subchapters, and sections, etc. But equally included in the
`term “table of contents” or “TOC” for our purposes is any
`hierarchically structured table or index describing the con
`tents of any document or collection of information.
`B. End-User Perspective
`Apreferred embodiment of the present invention supports
`implementing an incrementally expandable table of contents
`(“TOC”) in a client-server netWork environment like the
`Web. We begin our description With an illustration of What
`this advantageous capability looks like from the perspective
`of an end-user.
`FIG. 1A illustrates the display contents of a typical
`end-user computer screen, Wherein a standard Web broWser
`(such as Netscape’s Navigator product, or the XMosaic
`broWser available from NCSA and Spyglass) has been used
`to access a Web site con?gured in accordance With a
`preferred embodiment of the present invention. In this
`example, the Web site is located at a netWork address de?ned
`by the URL “http://maelstrom.csd/niftnav/niftnav.cgi/”,
`shoWn in URL WindoW 110. In other Words, as those of
`ordinary skill in the art Will readily recogniZe, the site is
`located at a netWork server machine identi?ed as
`maelstrom.csd, While the remainder of the URL provides an
`address path that the “maelstrom.csd” server uses to identify
`the site. The display of FIG. 1A includes TOC 100, a table
`of contents for an on-line Customer Support library. Cur
`rently shoWn is the top hierarchical level for that TOC.
`TOC 100 is, in accordance With the present invention,
`expandable at the end-user’s request. For example if the
`end-user uses a cursor control device or the like to “select”
`“HardWare” entry 120, then the end-user’s broWser Will
`automatically formulate an HTTP request using the hyper
`text link that is internally assigned to “HardWare” entry 120
`by the HTML code for the Web page being displayed, as
`those of ordinary skill in the art Well knoW. In accordance
`With the present invention, the response Will be transmitted
`to the end-user’s broWser as a neW Web page specifying a
`display as shoWn in FIG. 1B. As shoWn in that ?gure,
`HardWare entry 120 has noW been “opened” in the display,
`revealing the level of hierarchy directly beloW HardWare
`entry 120 in the table of contents (i.e., the hierarchical
`“children” 125 of HardWare entry 120). We refer to this
`
`012
`
`ServiceNow, Inc.'s
`Exhibit No. 1003
`
`

`
`US 6,199,098 B1
`
`5
`modi?ed, expanded display of the TOC as another display
`“state” for the TOC. In general, a display “state” of the TOC
`speci?es which entries (or “nodes”) within the TOC hierar
`chy are “open” and reveal their children, and which nodes
`are “closed” and conceal their children. In the display state
`of FIG. 1B, Hardware node 120 is open, while the other
`TOC nodes are all closed.
`The end-user can continue to incrementally expand and/or
`contract the hierarchical display of the table of contents.
`Thus FIG. 1c illustrates what the end-user sees if he or she
`“selects” Software entry 1330 from the display of FIG. 1B. In
`the Web page shown in FIG. 1C, the display state of the TOC
`is similar to that shown in FIG. 1B, except it has been
`modi?ed so as to open Software node 130, revealing and
`displaying that node’s hierarchical children 135. The display
`state of FIG. 1C is otherwise the same as for FIG. 1B, e.g.,
`Hardware node 120 remains open. Next, FIG. 1D shows that
`if the end-user selects Hardware entry 120 from the display
`of FIG. 1C, then the display state is again incrementally
`modi?ed, this time “closing” Hardware node 120 and con
`cealing children 125 while Software node 130 remains open.
`FIG. 1E re?ects expansion by the end-user of Software node
`130 down through several levels of hierarchy, ultimately
`revealing leaf node 140 labeled “White Papers” which
`provides a direct hypertextual link to relevant information
`located elsewhere on the Web. The TOC display state of
`FIG. IE is otherwise unchanged. This incremental expan
`sion and contraction of a hierarchical TOC’s display state is
`in marked contrast to prior art efforts in this area, as
`discussed above in the Background section.
`C. Overview of Architecture and Methodology
`FIG. 2 provides a high level architectural view of a
`preferred embodiment for implementing the present inven
`tion. End-user utiliZes client computer 100, and standard
`browser program 120 executing thereon, to request, retrieve,
`and display network documents, e.g.,Web pages. Each
`request by client computer 100 for retrieval of a network
`document is formulated in accordance with the network
`protocol, e.g., HTTP, and transmitted by browser 120 across
`network communications link 1335 to server computer 150.
`Server computer 150 receives HTTP requests such as
`request 140 and processes them using HTTP server software
`160, e.g., standard network server software. In addition, in
`accordance with the present invention, server computer 150
`uses script program 180 to process requests involving an
`expandable table of contents. Script program 180 in turn
`references structure de?nition ?le 190, which de?nes the
`overall hierarchical structure of a given TOC; script 180 also
`references portions of the address path making up HTTP
`request 140, to extract information about the current display
`state of the TOC. UtiliZing structure de?nition ?le 190 and
`portions of HTTP request 140, script program 180 dynami
`cally generates HTML Web page 145 specifying a hierar
`chical TOC display re?ecting the currently desired display
`state. Script program 180 can then cause server software 160
`to transmit a copy of Web page 145 back to client computer
`100 and browser program 120, for display on monitor 110.
`FIG. 3 is a How diagram of the major tasks performed in
`a preferred embodiment for the present invention. At step
`300, the user who wishes to publish a TOC for navigating
`on-line information creates structure de?nition ?le 190,
`thereby specifying a hierarchical structure for the TOC. The
`details of structure de?nition ?le 190 are described herein in
`a later section. At step 310, the publisher user prepares script
`program 180 (preferably a CGI script) for dynamically
`generating Web pages representing the expanding or con
`tracting TOC, as discussed in detail below. At step 320, the
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`end-user of client computer 100 uses standard HTML
`browser 120 to formulate HTTP request 140 and transmit
`that request to server computer 150. HTTP request 140
`includes a URL addressing script program 180, plus
`(optionally) additional ?elds which encode a current hier
`archical display state as described below. These additional
`?elds are preferably stored by server 150 in the “PATHi
`INFO” variable, and so we sometimes refer herein to this
`information as “PATHiINFO” information.
`Responsive to step 320, at step 330 script 180 is run by
`server 150. The script dynamically generates new web page
`145 specifying display of the TOC. As explained in much
`greater detail below, the script examines structure de?nition
`?le 190 along with the PATHiINFO information from
`HTTP request 140 in order to determine which TOC nodes
`should be displayed. TOC nodes to be displayed are
`included by script 180 as entries in the new web page. For
`example, the top level nodes in the TOC, as identi?ed in the
`structure de?nition ?le, are always displayed; traversing
`through the TOC hierarchy, each node’s children are dis
`played if and only if the node is in “open” state. As explained
`below, the PATHiINFO information encodes the “open” or
`“closed” state of each node; for example, each non-leaf node
`is closed, unless the name of that node appears once in
`PATHiINFO in which case that node is opened. At step
`340, server 150 passes new web page 145 to client browser
`120, and at step 350 browser 120 causes display of the new
`web page for the end-user on monitor 110.
`Note that in order to allow incremental expansion of the
`TOC hierarchy by the client user in an interactive fashion, at
`step 330 script 180 encodes each non-leaf node in the new
`web page with a hypertext link that encodes the current
`display state of the TOC but with the “open/closed” status of
`the linked node toggled (i.e., reversed). In other words, the
`display state is encoded such that if the client browser selects
`a non-leaf node within the TOC, the effect will be to transmit
`a URL to the server as HTTP request 140 that effectively
`requests a toggling of that node’s current open/closed state,
`without affecting the open/closed state of any other nodes in
`the TOC. (Leaf nodes are always just hypertextually linked
`to their destination path.) Thus, FIG. 3 indicates that at
`decision point 370, if the end-user interactively selects a
`non-leaf node of the TOC, the How of control returns to step
`320, wherein the URL transmitted by the browser will be the
`URL assigned as a hypertext link to the selected non-leaf
`node, subsequently causing a toggling of that node’s open/
`closed display state. This process is repeatable and may be
`iterated so as to incrementally expand and contract the TOC
`display for as long as the end-user desires. If instead the
`end-user clicks on a leaf node at decision point 370, then the
`network information hypertextually linked to that leaf nod