Method and apparatus for generating a hypertext-based content menu using an open hierarchical data structure

[0002] This application is based on Provisional Application No. 60/046,920 entitled “Method and Apparatus for Generating Nested HTML Link Menu Files Using An Open Hierarchical Data Structure”, filed May 16, 1997.

[0003] The present invention relates to computer software used to organize informatin on a Web site, and in particular, it relates to an end-user access method, identified as a content menu, that is generated by an authoring system that produces linked hypertext list menu files by merging hypertext program code like HTML with menu data managed by an open hierarchical data structure.

[0004] The conventional use of hypertext links in Web site design makes information-rich sites unnecessarily deep. This forces end-users to navigate in a trial and error fashion to locate relevant information. More direct access methods, such as a table of contents or a search engine, exist but these prior art methods present their own set of limitations. Tables of contents can only provide very broad overviews of sites because they cannot handle the detail, and search engines have a “black box” approach that hides content from end-users and requires them to know what they should ask for.

[0005] On a corporate Intranet network with content on multiple servers, the scope and supply detailed information is significantly greater and makes end-user access on this type of Web site even more challenging. End-user services, like a directory assistance, site map, or site index, attempt to scale themselves to the level of detail but, once again, limitations with the underlying technology limit their effectiveness.

[0006] For instance, these access services are either built and maintained by hand, or they are based on hierarchical structures that have mutually exclusive paths. While these structures are well suited to handle details, they are inadequate because they cannot cross reference. At the same time, the more flexible hand-coded access methods that easily represent cross links run into major problems when the links and references get too numerous or complex.

[0007] Tabb et. al. (Feb. 11, 1997 U.S. Pat. No. 5,603,025) disclose the means to produce cross-indexed hypertext documents that enable end-users to drill-down to investigate details. Meske et. al. (Jun. 25, 1996) also disclose the means to generate links that cross reference a set of information files. Both of these disclosures use HTML links to produce and maintain a set of linked files that enable end-users to access detailed information. However, since both of these methods depend solely upon their own document file structures they cannot be used in a more general way as end-user access tools.

[0008] Zellweger (May 13, 1997 U.S. Pat. No. 5,630,125) discloses the means to employ an open hierarchical data structure to organize and manage detailed information about a collection of information. When used with the disclosed authoring system, the structure generates a content menu that supports an extensive set of cross references. Advances brought about by the interactive authoring make it fairly easy to build and maintain the complete network of menu paths, and end-users find it easy to navigate its nested list menus and find what they need.

[0009] The Zellweger disclosure addresses both stand-alone and client-server environments but is does not disclose how to generate menu files for a content menu that can overcome performance issues related to client-server networks like the World Wide Web. The authoring system in the prior art generated a single menu file that contained all the nested lists in a content menu. In a stand-alone desktop setting, the invention optimizes response time by fetching data for each list menu from its own storage device. Yet, in a client-server setting, the overhead associated with requesting and transmitting data for each menu list from a remote source on a network, makes this list-by-list retrieval method extremely inefficient, particularly when the succession involves a series of short list menus.

[0010] The present disclosure shows how to overcome this problem by generating a series of hypertext menu files that consolidate a series of short, nested list menus into a single file that downloads to the client computer. As the end-user navigates down a content menu the present disclosure also shows how to link one of these menu files to another and how to regulate the overall size of these files. These teachings enable menu developers to benchmark different sets of menu files in order to identify an optimal download file size.

[0011] When a content menu has been optimized for a client-server network, as disclosed by this invention, there are a number of unintended benefits. First, the content menu provides an alternative way to access Web pages that has a direct impact on Web sit design. Until now developers had to use “link pages” to furnish page access that produces artificially deep Web site layouts. Second, the menu organizes details on a group of closely related information so end-users can easily compare one unit to another using a single list menu. This allows end-users to pinpoint target information on a Web site, and thereby avoid unnecessary trial and error navigation. Third, information providers get much more information about an end-user's navigating path compared to Web page tracking methods disclosed by Graber et. al. (Jan. 27, 1998, U.S. Pat. No. 5,712,979) and Graber et. al. (May 10, 1998 U.S. Pat. No. 5,517,860) because the provider has overall control of the entire menu path.

[0012] It is a general object of the present invention to provide a method and apparatus for an authoring system means that can be used to generate and maintain hypertext files that can serve as a content menu on a Web site.

[0013] One object of the present invention is to provide the software means for building and maintaining a series of nested link menus derived from an open hierarchical data structure implemented in a hypertext language, like HTML, that is recognized by browser software on a client computer.

[0014] Another object of the present invention is to enable Web site developers to select how and when hypertext files are generated so they can configure a content menu application that performs well on a client server network.

[0015] One object of the present invention is to provide the means to specify the size of an output hypertext file so the authoring system can generate one or more nested lists to the same file, instead of using the prior method of one list per file, and thereby reduce overall network traffic.

[0016] Another object of the present invention is to enable Web site developers to select when hypertext files are generated so they can configure a content menu application that uses dynamic menu data.

[0017] One object of the present invention is to provide the means to enable end-users to navigate through a succession of hypertext list menus to locate detailed information and thereby avoid unnecessary trial and error navigation on a Web site.

[0018] Another object of the present invention is to provide the software means to enable information providers to track end-user navigation of a content menu.

[0019] The objects of the present invention are attained by providing the methods and apparatus of a menu authoring system that generates nested list menus in tow or more hypertext files that serve as a content menu on a Web site. The authoring system merges menu data stored in an open hierarchical data structure with elements of a hypertext language to produce hypertext files that contain one or more nested list menus per file. Web site developers use the authoring system to create menu paths to individual pages, and end-users navigate these paths to locate relevant information. The authoring system in the present invention supports special settings associated with the output hypertext files that enable the menu developer to specify how and when these files are generated to improve sever response, reduce network traffic, or track end-user navigation.

[0020] FIG. 1 depicts the client server apparatus of the network in the present invention.

[0021] FIG. 2 depicts the user interface of the content menu in the present invention.

[0022] FIG. 3 depicts the relationship of the authoring system, the hypertext files it generates, and the browser software that reads these files.

[0023] FIG. 4 (prior art) depicts the open hierarchical data structure employed by the authoring system to store and retrieve menu data used for the content menu.

[0024] FIG. 5 depicts a database structure used to represent nodes in the open hierarchical data structure.

[0025] FIG. 6 depicts the record structure of an alternative storage format for nodes in an open hierarchical data structure.

[0026] FIG. 7 depicts the user interface of the authoring system used to configure the output hypertext files that contain the list menus.

[0027] FIGS. 8athrough 8cdepict the components of a hypertext file and the list menus generated by the present invention.

[0028] FIGS. 9athrough 9ddepict the flow charts of an embodiment of the program logic of software in the present invention used to generate compiled hypertext files that are stored on a server computer.

[0029] FIG. 10 depicts the flow chart of the program logic used to generate an HTML list menu file at runtime.

[0030] FIG. 11 depicts the flow chart of the server CGI script used to generate a runtime hypertext file that tracks end-user navigation on a content menu.

[0031] The client server apparatus of the present invention is depicted in FIG. 1. The server computer 15 contains an operating system, a database management system, and communications software, as well as the hypertext files generated by the present invention. The client computer 12 has its own operating system and communication software and is linked electronically to the server computer 15. The client computer 12 includes end-user input devices like keyboard 14 and output devices like a display monitor 10. Browser software, like Netscape, is installed on the client computer 12 and requests hypertext files stored on server computer 15 to generate a user interface on the display monitor 10. The server computer 15 downloads the file over the network to fulfill this request.

[0032] FIG. 2 depicts the user interface 22 on the monitor apparatus 10 of the client computer 12. In the preferred embodiment of the present invention the user interface 22 includes a list frame 24 and an object frame 25. The list frame 24 displays the HTML list menus that constitute the content menu generated by the present invention. Each list menu includes one or more list items that link to another HTML list menu or to an information object. End-users navigate these nested list menus to reach information on a Web page that is displayed in the object frame 25. Alternative embodiments of the present invention use one or more frames to display content list menus and information objects.

[0033] Each list menu includes a title and navigation commands. The list title corresponds to the list item selected in the last list menu. The navigation commands, found directly under the title, and at the end of a long scrolling list, include links to the Web site home page, top of the content menu, and a prior list. Depending on when the hypertext files were generated, the prior list either links to the last menu visited in a runtime file, or to a primary parent list in a compiled file.

[0034] FIG. 3 depicts the three major components of the present invention. These include the authoring system 26, the hypertext files 27 that the authoring system 26 produces, and a commercially available browser 28. The authoring system 26 includes the interactive software tools and utilities used to build and maintain menu data in an open hierarchical data structure. The authoring system 26, in the present invention, allows a menu developer to select when a hypertext file 27 is generated, at runtime when the client browser software requests it, or as part of a general distribution release.

[0035] In a general distribution release, the authoring system 26 generates or compiles one or more hypertext files that represent all the lists in a structure 29 in FIG. 4. The complete set of compiled files are stored on the server computer 15 and represent static menu values that do not change over time, that is from one release to the next. The alternative file output, a runtime HTML file, represents dynamic menu values that change whenever changes are made to the open hierarchical structure or its data.

[0036] The present invention uses an open hierarchical data structure, a prior art, to manage the network of hypertext links that constitute a content menu. This structure, depicted in FIG. 4 as 29, enables one or more paths to the same Web page object, and thereby represents multiple ways of looking up the same piece of information.

[0037] Generational terms, such as parent and child, are used to describe how structural elements relate to one another. For example, the flow in this structure goes from the root node 30 to a leaf node, lets say 52, so a parent node represents a predecessor, and a child node represents a successor. In structure 29, a parent node can only have one child but a child can have more than one parent. Each node in structure 29 corresponds to an item in a list menu. Arcs or pointers show how each item relates to another. Sibling pointers connect a item to a list, and child pointers link an item in one list to another or to a Web page at the end of a path.

[0038] The preferred embodiment of the present invention represents nodes in structure 29 in a database structure 60 depicted in FIG. 5. Each row element in structure 60 represents node information associated with a node in the open hierarchical data structure 29. This includes a unique id number in column field 61, a topic representing a list item in 62, a code in 63 used to analyze a selection made in an end-user's navigation path, and the number of child nodes in the next list in 69. Mem 67 stores the amount of file memory required for the current node's successor list. Each list is ordered by the sibling 66, and child 65 stores the node id of the first item in a successor list. Parent 64 stores the node id of the primary parent of the current list; all other parent nodes are considered step parents.

[0039] An alternative embodiment of the present invention stores node information in a second in a predetermined file format. Node records are ordered by lists and their respective generations. FIG. 6 depicts the record structure for this file format. Some fields, like node 61, topic 62, sibling 66, mem 67, level 68, and kids 69, directly correspond to database structure 60. In addition, the record structure also includes address information fields on the file location of the parent list in 71 and the successor list in 72. These fields enable the alternative file format to serve as a more efficient retrieval method on a server, compared to a database management system that requires significantly more i/o overhead to locate target data records.

[0040] The HTML Configuration Window 73 in the authoring system 26, depicted in FIG. 7, enables content menu developers to configure output hypertext files 27. This includes text fields that enable developers to include header information such as the developer's name, company, phone number, and copyright information, and so on. It also includes text fields to collect information on the Web site's home page URL, and how to configure the default menu and object frames.

[0041] Next, developers use radio buttons to indicate when the hypertext files 27 are generated, at runtime or compiled prior to distribution, and how they will be used, for multiple lists or for tracking end-user navigation. When the multiple list option is selected, the developer can also specify an optimal hypertext file size generated by the authoring system 26. This setting enables the system to output one or more smaller nested menu lists to the same file and thereby reduce network traffic on the server and improve response time on client computer 12.

[0042] FIGS. 8athrough 8cshow the components of the HTML hypertext file 27 generated by the authoring system 26. FIG. 8adepicts the major source code components of a hypertext HTML file 27. This includes file header block 74 and file trailer HTML tags 76, and one or more list menus 75. Detailed information supplied by the developer in the HTML configuration window 73 is used to produce comment lines in the file header and produce navigation links used in the list menu.

[0043] In the present invention, each hypertext file contains one or more list menus 75. FIG. 8bdepicts the significant parts of the list menu 75. Each list menu 75 includes an anchor line 77 for the list menu, a list title line 78, and navigation links 79 to the top of the content menu, to the home page, and to a prior list menu. Next comes one or more list item lines 80. This is all followed by line 81 that includes hypertext tags that mark the end of a list block.

[0044] Each list item 80, illustrated in FIG. 8c,consists of fixed length segments 80 of hypertext and variable length segments. The link field 82 and the item string 62 represent variable length fields. The authoring system 26 uses the node 61 to generate and manage links that connect to anchors in the current file and to other URLs.

[0045] FIGS. 9athrough 9ddepict flow charts of the software means of the present invention used to set menu generation variables, and output complied hypertext files 27. FIG. 9adepicts the main program driver entered at 83. First, the routine checks if the multiple lists radio button was selected by the developer. If it was not selected the routine sets file_size to the computed header_size, and returns control at 88 to the next event. Otherwise, the authoring system 26 computes the amount of memory required for each list by calling ComputeListSize 90 at 84. Next, it calls AssignFiles 100 at 85 to assign file locations to each node in structure 29. And finally, if the developer selected Compiled HTML Server Files routine 83 calls GenerateHTMLFiles at 86 and returns event control at 88.

[0046] The ComputeListSize routine 90 depicted in FIG. 9b.Routine 90 uses a FILO (First In, Last Out) stack to visit each node in structure 29 to compute memory requirements for each list. In loop 92, routine 90 progresses down the structure and pushes each node on the stack. When the end of a path is reached, routine 90 initializes list_size and iterates through each list item by popping nodes off the FIFO (First In, First Out) stack in loop 94. When a parent node is reached, routine 90 sets its mem 67 to list_size. If the parent node is a root node then program control returns to the calling routine at 98, otherwise it flows to loop 96 to set more node mem 67 values.

[0047] Next, the main routine 83 calls routine 100 to assign a file number to each node in the structure. Routine 100, depicted in FIG. 9c,uses a FIFO queue to visit each node in structure 29. If he children's list menu memory requirements are less than te optimum file_size set by the developer in window 73, routine 100 drops into loop 104 to push each child node on the FIFO queue and set file field 70. When the last sibling node is reached the routine pops the first node off the FIFO queue. If the queue returns a node, loop 102 is activated and the new node size is checked. When the cumulative memory size is greater than file_size then control flows through loop 106 where size is set to zero and file_number is set to the current node 61. Once again, control flows through loop 104 until the queue is empty.

[0048] At 86, in the main program driver, the authoring system 26 calls routine 110, depicted in FIG. 9d,to generate the compiled hypertext files 27 stored on the server computer 15. First, routine 110 sets current (file) variable, creates a new file, outputs source code 74 corresponding to the HTML file header. Next, starting at 112 and with loop 116 routine 110 outputs hypertext source code for each list menu associated with the current file variable. Routine 110 uses a FIFO queue to progress down each successive generation of lists. When a node's file 70 differs from current, routine 110 generates source code 76 that corresponds to trailer code, closes the open file, and creates a new file and opens it via loop 117. Otherwise, loop 118 is taken and routine 110 adds another list menu to the current file.

[0049] At 112 the routine generates hypertext source code for a list header that includes an anchor line 77, a list title line 78, and navigation commands 79. The argument for the NAME tag on anchor line 77 is derived by concatenating “F” with the current node id. The list title line 77 is generated by using the topic 62, and previous menu from the node's parent value in 64.

[0050] Next, loop 116 generates one or more list items for each node linked by sibling value in 66. If the node's mem field 67 is zero then routine 110 generates a list item 80 at 113 that has a link to an information object URL by concatenating the child field 65 with “.HTM”, i.e. “A.HTM”. Otherwise, the routine checks the node's file field 70. If this value corresponds to current the routine generates a list item 80 with a link to a location at the current file at 113 by concatenating “#F” with the child value in 65. Otherwise, the routine generates a list item 80 at 115 by concatenating “F” with the file field 70 with “.HTM#F” along with the child field 65, i.e. “F44.HTM#F130.

[0051] FIG. 10 depicts the flow chart of the program logic used to generate a hypertext list menu file on demand at runtime on a server. The calling routine, a Common Gateway Interface (CGI) script file depicted in FIG. 11, passes the node id of the selected list item. Loop 122 generates one or more list menus according to file_size set by the developer and how the developer intends to use the file. If the file is intended to track end-user navigation or the optimum file size was not set, only one list menu is generated per file.

[0052] Loop 124 is responsible for generating source code for each list item. Here subroutines 125, 126, and 127 first check if end-user tracking was set. If tracking was not set these subroutines call their respective counterparts 113, 114, or 115. Otherwise these subroutines generate a URL that refers to a CGI script on the server computer 15 that includes node 61 and time stamp parameter,

[0053] HREF=“http://arborway.com/cgi-bin/selected.pl?node=24+time=150530. Alternative ways to pass node and time stamp parameters to a CGI script on a server exists, and subroutines 125, 126, and 127 can be modified to accommodate these alternatives.

[0054] And now FIG. 11 depicts the program logic of the CGI script file on server computer 15 used to track end-user navigation. On entry, routine 130 gets client identification information at 131 from the environment variables or from arguments passed to the CGI script. Next, at 132 routine 130 gets the node and time stamp arguments. The routine calculates lapse_time at 134 by subtracting the time stamp from the current time on the server computer 15. At 135 the client identification information, selected node, and lapse time are added to a database that stores a record for each list item selected in a content menu. The set of records are used in conjunction with end-user tags in field 63 to analyze navigation paths. At 135 routine 130 calls generateOndemand routine 120 with the node 61 as parameter to generate a list menu, and then redirects the server to send new file to the client computer 12.

[0055] This concludes the description of an embodiment of the invention. The foregoing description of the embodiment of the invention has been presented for the purpose of illustration and description. It is not intended to be exhaustive or limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. The scope of the present invention is not intended to be limited by this detailed description, but rather by the claims appended hereto.