 |
Description  |
|
|
FIELD OF THE INVENTION
The invention relates to structuring hypermedia documents in a near-optimal
manner, and more particularly to a system for providing a near-optimal
assignment of information to pages and near-optimal page linking for
efficient navigation of the document.
BACKGROUND OF THE INVENTION
Hypermedia documents are computer-based documents that contain text and
graphics on pages that are connected via navigational links or buttons.
Hypermedia documents constitute an alternative to the book that permits
nonsequential access to pages. Embedded hypermedia documents are also
found in many user interfaces, such as aircraft cockpits, power- and
industrial-plant control consoles, information kiosks, automated teller
machines, videocassette recorders, and many other systems. In all such
instances, the problem of designing a hypermedia document involves two key
tasks: assigning information to particular pages, and determining how the
pages are linked. These tasks should be done so as to facilitate the
efficient traversal of the document by users.
For instance, the multifunction display, MFD, in an aircraft cockpit is a
hypermedia document that contains important flight data and controls that
cannot fit on the pilot's control panel. A typical MFD contains 20-100
linked pages of information, ideally linked so that the pilot can quickly
access the information he needs in a wide variety of normal and abnormal
operational situations. Since the information is provided to the pilot on
a single CRT display, it is often with difficulty that a designer of MFDs
can arrive at appropriate content and efficient linkage of the pages of
information presented to the pilot.
In the past, designers have provided such structure and links on an ad hoc
basis in which the structure and links are specified manually. The problem
with such manual procedures is that they are inordinately time-consuming
and often result in grossly non-optimal presentations. For instance, when
more than 100 pages of information are to be displayed, it may take
several man months to create a prototype hypermedia document for use as a
cockpit MFD. Thereafter, the prototype is tested for convenience by the
potential users of the system to ascertain the level of convenience
provided by the prototype, which may then require iterative refinement and
improvement.
Because there are no computer-aided functions that can be applied to the
design of such MFDs, there is often no rigorous accounting for the
relative importance of information or for flexible ordering of the
presentation of information, much less a system for optimizing the
document structure.
This problem is also severe not only for cockpit MFD design, but also the
design of information kiosks like automated teller machines, ATMs, in
which the user must oftentimes page through irrelevant screens to get to
the screen containing information that he currently wants. For instance,
an individual wishing to check his account balance must typically page
through three to four screens to access the information.
Moreover, books are prepared as linear documents in which the paging
sequence is fixed. This type of linear format is nonoptimal, especially
for texts with multiple intrinsic cross references, because the linear
format does not permit the user to be presented with information from
different portions of the book in a different order that is both more
convenient and that provides the information in a customized manner
related to relevance. This and other problems described above are all
hypermedia-document-structuring tasks that are addressed by the Subject
System.
SUMMARY OF THE INVENTION
In accordance with the present invention, a system is provided for
automatically specifying the page content and links between pages for a
hypermedia document. In so doing, the system provides a near-optimal
structure for a given document by reducing the structuring task to the
problem of partitioning a graph with near optimality. In one embodiment,
an analysis is performed to ascertain how the user will access the
information relevant to his task. From this analysis, a list of display
items and numbers that reflect the importance and frequency of movement
between display items on different pages or the same page is mapped onto a
graph: the display items map to nodes in the graph, and the numbers to
cumulatively weighted edges. Each edge in the graph therefore has
associated with it a weight reflecting the desirability of having the two
display items associated with the graph nodes connected by that link on
the same page. The weighting may reflect the criticality of having the
display items on the same page, the frequency with which the display items
are accessed sequentially, and other designer-specified importance
factors.
A modification to the graph is made with the intent of permitting movement
from one display item to another that requires traversal through a page or
pages which do not contain either display item. This is accomplished
through the utilization of additional nodes in the associated graph,
referred to herein as stepping-stone nodes. Each edge in the original
graph, corresponding to a relation between a pair of display items, is
split in two to accommodate the interposition of one or more
stepping-stone nodes. This permits the modified graph to account for
indirect movement from display item to display item via another page
containing neither display item, which is not otherwise captured or
represented by the original single unbroken edge.
After having derived the graph, graph partitioning is accomplished by using
standard graph-partitioning algorithms which results in the assignment of
display items to pages and the establishment of links between the pages.
In one embodiment, the graph is partitioned by one of the most common
partitioning systems, described by Kernighan and Lin in U.S. Pat. No.
3,617,714, incorporated herein by reference. Here, a method of
partitioning the nodes of a graph into sets utilizes constraints on the
maximum number of sets, the maximum number of nodes that can be assigned
to a particular set, and a maximum number of edge connections that can be
made to any one set. This method is utilized to minimize the
interconnection cost of connected nodes in different sets. It has been
found to be useful not only for the design of near-optimal circuit layouts
but also in the computer-aided design of VLSI circuits, networks,
databases, and the organization of distributed and parallel computations.
The result of the application of the graph-partitioning algorithm to the
graph defined by the designer of the hypermedia document is a near-optimal
organization of the document insofar as the optimality criteria specified
by the designer reflect the desired use of the document.
In summary, apparatus is provided for determining the structure of a
hypermedia document containing text and graphics that are to be laid out
on several linked pages. This apparatus includes a system that specifies
the assignment of text and graphics to pages and the links between the
pages via a reduction to graph partitioning and the use of optimization
techniques for graph partitioning. In one embodiment, display items and
relations between these display items are listed along with a measure of
their importance. These factors are captured in terms of numeric weights
for edges between nodes in the associated graph to permit the system to
assign display items to pages, and determine which pages should be linked,
so that a user can move between pages in the most efficient manner. In a
further embodiment, to accommodate limited display area that restricts the
number of display items and page links that can be displayed
simultaneously, the system can take into account multistage page moves
that allow the user to access display items on different pages in sequence
by moving from one page to another via links on other pages, through the
use of "stepping-stone" nodes in the associated graph that record possible
traversal routes in the document that are not represented in other
formulations of the hypermedia-document-layout task.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features of the Subject Invention will be better understood
taken in conjunction with the Detailed Description in conjunction with the
Drawing of which:
FIG. 1 is a diagrammatic representation of a computer screen in which a
page of a hypermedia document is displayed, with the page including a
number of display items arranged thereon, and with buttons each of which
invokes a different navigational link;
FIG. 2 is a block diagram of the Subject System in which tasks from an
operations manual are analyzed as to information/response requirements,
the analysis resulting in both a list of display items and a body of
item-access data that describes the relevant relations between the display
items, utilized by the Subject System for document structuring, with the
list of display items and the item-access data being input to a computer
via a text or graphical interface;
FIG. 3 is a diagrammatic representation of a sample set of graph nodes
depicting display items with identifiers and areas specified for each
display item;
FIG. 4 is a diagrammatic representation of the weighted edges that are
introduced in order to capture a relation between display items, in this
case a sequencing relation;
FIG. 5 is a diagrammatic representation of the graph of FIG. 4 indicating
an additional set of weighted edges introduced in order to capture a
different relation between display items, also including a former edge
whose weight is augmented by the weight associated with this new
sequencing relation;
FIG. 6 is a diagrammatic representation of the weighted edges that are
introduced in order to capture a relation between display items, in this
case a relation indicating that a particular display item should be
directly accessible from all other display items;
FIG. 7 is a diagrammatic representation of the weighted edges that are
introduced in order to capture a relation between display items, in this
case a relation that indicates a conceptual clustering of display items,
which, if possible, are ideally assigned by the Subject System to one
page;
FIG. 8 is the graph of FIG. 4 indicating in addition the required maximum
page size and the area taken up by the standard navigational-link button;
FIG. 9 is a diagrammatic representation of the introduction of
stepping-stone nodes to each edge of the graph of FIG. 8;
FIG. 10 is a diagrammatic representation of a manually derived assignment
of display-item and stepping-stone nodes to pages such that the page size
is not exceeded, resulting in a cut-set cost for the partition of 33;
FIG. 11 is a diagrammatic representation of a computer-generated assignment
of display-item and stepping-stone nodes to pages such that the page size
is not exceeded and such that the cut-set cost is lower than that of FIG.
10 indicating a better solution; and,
FIG. 12 is a diagrammatic representation of an alternative assignment of
display-item and stepping-stone nodes to pages illustrating the existence
of a page without display-item nodes, but with stepping-stone nodes.
DETAILED DESCRIPTION
Referring to FIG. 1, a computer screen 10 for use in many user interfaces,
such as aircraft cockpits, power- and industrial-plant control consoles,
information kiosks, automated teller machines, and videocassette recorders
illustrates the placing of display items 12, 14, 16, and 18, on a page 20
that also includes navigational-link buttons 22, 24, 26, 28, and 30. It
will be appreciated that this screen contains but one page amongst many
presenting information to the user. The information is contained in a
hypermedia document which includes pages of information and a linking
structure that connects the pages. Navigating through the pages is
accomplished by navigation buttons 22-30, in one embodiment, through the
use of touch-screen technology.
The ability to provide a suitable structure for the hypermedia document to
permit ease of navigation and access heretofore was a matter of manual
design, not automatically optimized based on principles of graph
partitioning.
Referring now to FIG. 2, a system 40 for automatically optimizing the
structure of a hypermedia document includes initially extracting tasks
from an operations manual or similar source 42. Once the tasks have been
extracted, a manual information/response analysis is performed at 44 to
identify display items 46 and item-access data 48. Item-access data 48
specifies the nature of the relationship between display items 46, namely
sequencing, direct and immediate accessibility, or conceptual clustering
relationships for which numerical quantities indicate relative importance,
frequency, and criticality.
Having derived the list of display items and the item-access data, graph
partitioning is performed at 50 to assign the display items to pages and
to specify the linkage structure between the pages. The result is a
document structure 52 which is near-optimal with respect to displaying the
information relevant for the tasks identified in the operations manual or
other source. The output of this system is coupled to a display driver
(not shown) which presents pages of information on screen 10 of FIG. 1 in
the manner specified by the document structure. As a result, the Subject
System constitutes a machine for the driving of a display screen with
optimally presented pages of information.
Referring now to FIG. 3, the diagram illustrates the correspondence between
display items and nodes in a graph, nodes which have associated with them
an identifier and a size or area requirement. For instance, display item
B, which has an area requirement of 4, is represented by a graph node 54.
Likewise, node 56 represents display item A having an area requirement of
3. It will be appreciated that the remainder of the nodes represent other
display items and their associated areas.
Referring to FIG. 4, weighted edges 58, 60, 62, and 64 are introduced to
connect nodes 54, 56, 66, 68, and 70 so as to represent an access sequence
B, A, F, E, and D with frequency and criticality 5 and 1 respectively. It
will be noted that the weight for each edge is the product of the
criticality and frequency. In this manner, the cost due to a particular
access sequence of having any connected pair of display items on different
pages is recorded.
Referring now to FIG. 5, a different access sequence, namely C, A, F, and G
is specified by connecting nodes 72, 56, 66, and 74. It will be seen that
a new edge is introduced between nodes 72 and 56 with weight 6
corresponding to a frequency and criticality of 3 and 2 respectively, as
illustrated by edge 76. The edge 78 between nodes 66 and 74 is likewise
introduced and give a weight of 6. The existing edge 60 connecting nodes
56 and 66 has its original weight of 5 augmented by 6 to yield a
cumulative weight of 11. As can be seen, the weights originally
established in information/response analysis 44 are combined into one
number for the graph-partitioning process.
Referring now to FIG. 6, on occasion there will be a requirement that a
given display item, here represented by node 54, must be directly
accessible from any page in the document. This corresponds to a situation
where immediate access to a particular display item is required in a
specialized situation, for instance an aircraft emergency. This is
represented by connecting nodes 72, 70, 68, 66, 74, and 56 to node 54 in
the graph. As can be seen edges 80, 82, 84, 86, and 88 are all given a
high combined criticality and frequency weight, arbitrarily 50 in this
example.
Referring now to FIG. 7, oftentimes it is desirable to require that
conceptually related display items appear on a single page, or a small
number of pages. As can be seen, nodes 66, 68, and 74 represent such a
cluster of display items E, F, and G. This cluster is given a weight of 2.
As can be seen any new edges introduced in this step are given weight 2,
and any existing edges have their respective weights incremented by 2. As
can be seen by the edges 90 connection amongst the clustered nodes is
bi-directional making the cluster fully connected. The result is that if a
partition seeks to separate the nodes that have been so clustered, there
will be a penalty related to each pair of nodes in the cluster that are
assigned to separate pages.
Referring to FIG. 8, and returning to the simpler example of FIG. 5, this
example problem is considered with the following constraints: a maximum
page size of 7 and a uniform navigational-link size of 1. This means that
the sum of the areas associated with all nodes assigned to a page, plus
the area required for all navigational links from that page, must be less
than or equal to 7.
Referring now to FIG. 9, partitioning the graph of FIG. 8 would result in a
document structure in which all pages would be required to contain one or
more display items. This would preclude document structures in which some
pages contain only navigational links. Such document structures are not
uncommon, and are sometimes optimal in the sense that these navigational
links facilitate more efficient access to the data. For example, in a
typical ATM system, the user must traverse a hierarchical menu, that is a
sequence of menu pages containing only navigational-link buttons, before
accessing pages that contain the desired information, such as bank
balances.
As can be seen in FIG. 9, a number of additional nodes, 102, 104, 106, 108,
110, and 112 are interposed on all existing edges in the graph. Moreover,
nodes 116 and 114 are introduced along with edges that connect them to
nodes 54 and 72, which are distinguished by corresponding to the first
display item in an access sequence or to a display item that is specified
as having to be accessible from everywhere in the document.
As can be seen, edges to and from a stepping-stone node have weights
identical to the edges into which the stepping-stone node is interposed.
In effect, the interposition of a stepping-stone node divides the original
edges into two edges. This provides flexibility in assigning nodes to
pages in the subsequent partitioning process. The additional nodes
introduced above are designated stepping-stone nodes because of their
ability to serve as way stations in the process of moving from one display
item to another in the document.
Referring now to FIG. 10, in the graph-partitioning process nodes are
assigned to pages as illustrated. Thus node 54 and 116 are assigned to
page 120, whereas nodes 56, 74, 102, 112, 104, and 106 are assigned to
page 122. Likewise, nodes 66, 68, and 108 are assigned to page 124,
whereas nodes 70, 72, 110, and 114 are assigned to page 126. It will be
noted that to the side of each page is a number reflecting the combined
area of all display-item nodes and navigational links that go off-page. As
can be seen, all pages have a number less than or equal to 7, which is the
maximum allowed page size, noting that the uniform size for
navigational-link nodes is 1.
This partitioning process is accomplished manually for the depicted graph.
In the partitioning process, the degree of optimality achieved is
reflected in the size of the cut set, which is the sum of the weights of
edges that span from one page to another. In the depicted partition, the
cut-set cost is 33, which is the sum of the weights 5, 6, 11, 6, and 5 on
the edges between the pages.
In the Subject System, and as can be seen from FIG. 11, the nodes are
assigned differently through the utilization of any one of a number of
graph-partitioning techniques, the most common of which is the
aforementioned Kernighan-Lin process. Here, the nodes are allocated to
pages 130, 132, 134, 136, and 138. The cut-set cost for this partition is
27, indicating a better partition for the same graph illustrated in FIG.
10. It is noted that the number of pages has increased by 1, nonetheless
resulting in a superior structure for the access of the information
involved. What this partition accomplishes is a better arrangement of
information on five pages than is accomplished manually in four pages.
Referring now to FIG. 12, a partitioning is illustrated in which a
particular page, namely page 140, contains no display-item nodes, but has
been assigned two stepping-stone nodes 102 and 112. This page will
therefore contain a navigational-link button to permit traversal via this
page from pages 142 and 144 to page 146. It will be appreciated that since
the edges emanating from the two stepping-stone nodes 102 and 112 point to
the same display item 56 on page 146, only one navigational-link button is
required on page 140, thus resulting in a total allocated area of 1 for
page 140. This is an example of how one can collapse multiple edges to a
single display-item node or a collection of display-item nodes on one page
that can be referred to collectively. In this case the cut-set cost for
the partition shown is 44, which is inferior to the partitions of FIGS. 10
and 11. However, it will be appreciated that for other graphs optimal or
near-optimal partitions will require pages with no display-item nodes.
A program listing in C for the document-structuring system described above
is appended hereto.
Having above indicated several embodiments of the Subject Invention, it
will occur to those skilled in the art that modifications and alternatives
can be practiced within the spirit of the invention, It is accordingly
intended to define the scope of the invention only as indicated in the
following claims.
##SPC1##
* * * * *
|
|
 |
|
 |
Description |
|
