1.1 Field of the Invention
The present invention relates to means and a method executable by a computer system for navigation within a tree structure with leaf nodes representing arbitrary types of objects, i.e. of related data treated as a unit.
1.2 Description and Disadvantages of Prior Art
xe2x80x9cThe Information Agexe2x80x9d, a fairly commonly heard expression these days, but one whose consequences seem to be ignored as frequently as it is used. There is no denying the fact that we are in the midst of a long term explosion of information that shows no signs of slowing down, or even accelerating less forcefully. The questions this fact raises are many, but one of the most significant, if not the most significant, is the question of organisation.
The Information Age has lived up to it""s promise of xe2x80x9cinformation at our fingertipsxe2x80x9d, but the sheer volume of the information available makes it nearly impossible to find any given set of specific information, much less navigate intelligently through the constantly growing sea of data. The additional question of attempting to somehow display information about the relations between various items, and the context of the item, adds still another level of complexity. When we start to look at large collections of related data, with additional information about context and relations (xe2x80x9cComplex Knowledge Structuresxe2x80x9d)., one enters a territory even less navigable than the raw dataxe2x80x94the additional information should help us understand the raw facts, but again the sheer amount of information overloads us and renders the putative assistance of context a hindrance.
The computer is that tool, and it has become the main ally in the quest to force some sort of order, or structure, onto the apparently endless chaotic mass of information. When one starts looking at new ways to order and present data using computers, then the question becomes one of ergonomics. To wit, how do we organise and display these complex knowledge structures so that humans can navigate through them with ease, find what they are looking for, and generally make sense of the information in context? How do we select appropriate data from the mass of information, and once we have found it, how do we allow the user to interact with it?
Based on this background the display of large amounts of information has been an active area of research in a diversity of areas since decades now. Work on man-machine interfaces, information retrieval, graph layout, cognitive science, virtual realityxe2x80x94each area concentrates on certain aspects or principles of the problem. Within the context of knowledge management, one has to deal with a widespread spectrum of information types: raw texts, structured texts, annotated information, partly automatically generated information entities, which obey yet unknown structural rules, relational and hierarchical meta information. Hence, the capabilities of information browsers or navigators can be measured by the degree they are able to handle some of the most important expectations like:
to display partly structured information of varying size
to ease the perception of the ordering of the information
to allow for interactive exploration of information spaces
To put it in different words: in this context where we discuss a mixture of human-edited information carriers (written text) and machine-generated structures (object hierarchies, descriptive labels i.e. xe2x80x9ctermsxe2x80x9d), an information structure becomes only valuable by perception, not per se. The question remaining is: which aspects of this mixed information might be stressed to achieve optimal perception. In the following, we compare some recent work in cognitive science, graph layout, information retrieval and knowledge management by their respective modalities.
Y. Arens and E. Hovy, How to Describe What? Towards a Theory of Modality Utilization, Meeting of Cognitive Science Society, Cambridge, Mass Cognitive Science Society, p. 487-494, August 1990 describe a theory of modality utilization where they distinguish between three aspects of an information entity: the inner properties of the object, the properties of the class the object belongs to and the properties of a selected set of objects, i.e. the information to be discussed and residing in current focus.
These three aspects can be found in different designs of tree and graph browsers, graphical query languages, graphical information retrieval front ends, and general multimedia information systems. Prior to a more detailed analysis one can expect that all implemented systems will most radically differ by the chosen paradigm for their means of interactive exploration of information structures.
Information retrieval (IR) front ends like GUIDO and VIBE, proposed by Robert R. Korfhage and Kai A. Olsen, Information Display: Control of Visual Representations, Workshop on Visual Languages, IEEE Computer Society, p. 56-61, October 1991, provide a pre-structured information space to visualize document/document and document/term binary relations. The space is defined by (query) terms which span a certain geometry (e.g. a diamond-shaped panel with triangular segments). Document representations (small rectangles) are positioned to the segment where they have the greatest overlap with terms owning this segments Hierarchical information is hardly displayed for the sake of a conceptual strict layout paradigm. On the other hand it is well known that hierarchical organization approaches belong to the most powerful classification concepts conforming to a large extend with human way of thinking.
IR-system graphical user interface (GUI) designs based upon a 3D-space mostly concentrate on the display of the hierarchical aspect of information only. Systems using Cone-Trees, refer for instance to George G. Robertson and Jock D. Mackinlay and Stuart K. Card, Cone Trees: Animated 3D Visualizations of Hierarchical Information, Proceedings of ACM CHI""91 Conference on Human Factors in Computing Systems, p. 189-194, 1991, map term/document and other hierarchical relational information directly to a 3D layout algorithm. Interactive graphical operations like zoom and rotate provide means to gain an overview and inspect details. The design is centered around the user, who has to explore the (3D) space. As consequence and deficiency, the cognitive load is typically very high if one has to identify and compare properties for a certain set of objects.
Another specific technique suggested for the representation of complex knowledge structures, beloging to the same class exploiting the 3D space, is that of using the properties of hyperbolic geometry to provide a view that contains both an inherent focus (channelling user attention to some current node) and a context, i.e. information about the relationship between the current node and other nodes in the system, by navigating through a network of nodes.
Arbitrary data structures like entity-relationship models are typically mapped to axe2x80x94more or lessxe2x80x94specialized graph- or tree layout algorithm. The semantics of the relations is mapped to certain aspects of the graph layout. In GraphLog, refer for instance to Stuart K. Card and George G. Robertson and Jock D. Mackinlay, The Information Visualizer, An Information Workspace, Proceedings of ACM CHI""91 Conference on Humanfactors in Computing Systems, p. 181-188, 1991, one can even formulate structural/semantic queries by drawing objects, thus the user of this system works upon his own conceptual model of the underlying semantics. However, this paradigm lacks means to express the vague semantics and relationships that is buried within the objects under consideration (eg the topic of a text item, or the relatedness of two documents).
Hypertext-based systems interpret structural information (the hyperlinks) in a different way. Each hyper link represents an explicit relation (based upon topic, annotation, part-of etc. information) between different information entities. The layout of the global structure in systems like NoteCards, refer for instance to C. Foss, Effective Browsing in Hypertext Systems, Conference of RIAO, p. 82-98, 1988, is optimized to ease the interactive exploration and editing of the hyper space, since this is the intended usage. A drawback of browsing through hyperlinked information is the accompanying sense of disorientation as often reported by users. Two rather whimsically named problems that arise from navigation in hypertext have been identified: the xe2x80x9cEmbedded Digression Problemxe2x80x9d, and xe2x80x9cThe Art Museum Phenomenonxe2x80x9d. The xe2x80x9cEmbedded Digression Problemxe2x80x9d embraces the difficulties which arise from the multiplicity of choice offered by most hypertexts. Users may delve into a richly connected network of information which may serve to distract them from their chosen path and cause them to lose their place in the document. Alternatively, users may forget to return from a digression or forget to follow a path they had planned earlier. The xe2x80x9cArt Museum Phenomenonxe2x80x9d refers to a group of problems associated with learning through browsing. Browsing is an open and exploratory information-seeking activity which involves scanning and tracing ideas from one node to another in an often vague and non-specific manner. The non-directive nature of browsing means that users may often wander through a hypertext without stopping to study or think about the ideas the document presents. Consequently, users may be unable to recognise which nodes have been visited, or which parts of the exploration space remain to be seen.
Tree- and graph-layout algorithms, as described by K. Sugiyama and K. Misue, Visualization of structural information Automatic drawing of Compound Digraphs, IEEE Transactions on Systems, Man and Cybernetics, 21(4) p. 876-892, July/August 1991 for instance, typically concentrate on either global optimization (number of crossing links, space, distance) of conflicting properties of the overall graph layout. Or they must not violate one layout criteria (e.g. no crossing links for circuit design), but have to sacrifice other. Both variants exhibit that these algorithms are mainly designed to overcome technical shortcuts (like limitation of presentation space for instance), but must not be considered the core design of an information exploring environment.
Returning to the theory of xe2x80x9cmodality utilizationxe2x80x9d, one can conclude that none of the discussed system designs covers all three aspects of an information object in a unique way. Bringing interactivity between visualized structures and a user into the game shows even more drawbacks and confirms the need for a display design with a radical different technique.
The invention is based on the objective to improve the visualization of large and complex object structures and the interactive navigation of users within such environments. More particularly the invention is based on the objective to provide above improvements in the context of complex hierarchical organized object structures allowing the user to detect and gain new insights in the relationship between the objects and at the same time allowing to focus only on those aspects of the objects the user is really interested in.
The objectives of the invention are solved by the independent claims. Further advantageous arrangements and embodiments of the invention are set forth in the respective subclaims.
The invention teaches a method executable by a computer system for navigation within a tree-structure. The tree-structure comprises at least one leaf-node said leaf-node representing an object and the tree structure comprises at least one non-leaf-node. According to the invention a travel point representation step is suggested, wherein after selection of at least one non-leaf node as travel point only the path and non-leaf nodes in said tree structure from said travel point to the root of said tree structure is represented in a tree view area. Moreover the complete sub-tree of said travel point is represented in said tree view area. In addition or alternatively after selection of said travel point, a travel box is represented for said travel point, said travel box representing object identifications of all objects of all leaf nodes in said sub tree of said travel point.
The proposed method supports the hierarchical organization approaches from which it is known that it represents one of the most powerful classification concepts conforming to a large extend with human way of thinking. For this organization principal an approach is proposed which on one side significantly reduces the amount of displayed data and which on the other side significantly enriches the displayed data. The amount of displayed data is significantly decreased as the tree structure between a travel point and the root of the tree is reduced to the path between them. The amount of displayed data is significantly enriched as the complete sub-tree below a travel point is collapsed to a xe2x80x9cflatxe2x80x9d structure comprising all leaves of the sub-tree of a certain travel point. Therefore below a travel point an object centered view is introduced. The non-hierarchical data display has the advantage that the user is always presented with all of the objects at the leaves under a certain node in the hierarchical tree. Thus the relationship between the basic objects and the structural position within the collection is always exposed. The user gets a much better impression for the xe2x80x9csimilarityxe2x80x9d of objects and their relationship to other objects by this unique display method easing the perception of the ordering of the information. In terms of modality utilization the xe2x80x9cproperties of the classxe2x80x9d an object belongs to and the xe2x80x9cproperties of a selected set of objectxe2x80x9d reside in a common focus. Only the data the user is really interested in is displayedxe2x80x94the non-selected branches of the tree are folded away and only the direct path to the root is displayed.
Additional advantages are accomplished if said leaf-node is associated with object-attributes of the objects and if the non-leaf-node is associated with the object-attributes of all leaf-nodes of the sub-tree of the non-leaf-node. Within said travel box at least one object-attribute of said travel point is represented in said travel-point-representation-step. The travel point is marked visually in said travel-point-representation-step.
Therefore the travel boxes provide a xe2x80x9csecond dimensionxe2x80x9d to view in parallel on the object structure. This second dimension is a xe2x80x9ccontent orientedxe2x80x9d view as the attributes related to the semantic and contents of the objects are displayed. In terms of modality utilization the xe2x80x9cinner propertiesxe2x80x9d of the displayed objects are unveiled. This approach allows a user to explore huge object (for example documents) collections and learn about their structure. The user can gain insights from different perspectives on the data.
Additional advantages are accomplished by an upward-navigation-step, wherein, after selection of a parent-node of a current travel point, the travel-point-representation-step is performed with said parent-node as new travel point. In a downward-navigation-step, after selection of a child-node of a current travel point, the travel-point-representation-step is performed with said child-node as new travel point. The parent-node and the child-nodes are selectable in the tree-view-area, and/or in said travel box by selection of an upward-control-element and downward-control-element respectively. A direct child-node of the travel point is selectable in the travel box by selection of one of the following: an object-identification or an object-attribute together with the selection of a downward-control-element.
These features provide a user with dynamic navigation capabilities operating in two dimensions. Navigation on object level is possible from the travel boxes and navigation with respect to the position within the hierarchical structure is also possible. Within a travel box a branch in the tree can be followed down to the leaves via a particular object, independent of the depth of the object in the tree. This can lead to new insights about the overall structure of the collection and the grouping of the objects. Within the hierarchical structure the travel points can be moved and the tree expands and partially collapses respectively. Navigation on either way (object level or tree hierarchy) causes both views to be dynamically updated, thus both views are dynamically related and offer a flexible and easy to access overview over the data. The user can explore huge object collections and learn about their structure in a very interactive and at the same time easy to handle manner. The user can gain insights from different perspectives on the data and navigate according to the position in the tree, attributes or the objects themselves, each navigation step being reflected on several levels. This new browsing technology is a key to evolving technology areas such as Knowledge Management and Content Management, where a user has to deal with automatically generated hierarchies. Learning about their structure in a short time and evaluating their content becomes more and more important.
Additional advantages are accomplished by a navigation-initialization-step. After selection of an object-attribute either from an attribute-list-area, showing one or more object-attributes of said tree-structure, or from said travel box, the navigation-initialization-step determines the non-leaf-nodes being the direct parent-nodes of leaf-nodes associated with said selected object-attribute. It selects the determined non-leaf-nodes as travel points and performs the travel-point-representation-step for said travel points.
Thus the proposed attribute list area provides a xe2x80x9cthird dimensionxe2x80x9d for navigation to a user. The attribute list serves as a selection list to access the leaves of the hierarchy, i.e. the objects. Only those leaves are displayed which satisfy the select criteria. The attribute list is extendible by various search criteria, sort criteria etc. The data is presented in a clear and easy to access manner. Only the information a user is interested in is displayed as he can choose the entry point to the data from the attribute list. Ideally all attributes of all objects of the whole tree structure are presented in the attribute list area.
Additional advantages are accomplished by storing a travel-point-identification during navigation in the tree-structure in a history-record. By means of a history-navigation-step, wherein, after selection of a history-control-element in the travel box, the previous travel point with respect to said history-record is used for performing the travel-point-representation-step.
Due to this history function the user has the option to go back the same path within the hierarchy he came, or follow new paths.
Additional advantages are accomplished if the objects represent documents and/or the object-attributes are lexical-affinities (refer to the description below for an understanding of lexical affinities according to the state of the art) of the document and if the object-attributes are ranked according to the frequency of occurrence of said lexical-affinities.
Based on an aggregation of these features a navigator results representing a powerful tool for exploration of data spaces originating in the technology area of information mining.