Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-05-28
2002-12-17
Hong, Stephen S. (Department: 2176)
Data processing: database and file management or data structures
Database design
Data structure types
C707S960000, C345S215000, C345S215000
Reexamination Certificate
active
06496842
ABSTRACT:
BACKGROUND
This invention relates to a user interface for navigating a set of information arranged hierarchically, even a very large set.
In a typical hierarchy or “tree” of nodes, each “node” is connected to zero or more “child” nodes and to one “parent” node, except for one “root” node which has no parent.
Hierarchies are common in data processing. Often a hierarchy provides a clear way to organize a large amount of information so that a user can find a particular piece of information. Generally, a user “navigates” a tree by iteratively viewing descriptions of a selected node's neighboring nodes and selecting one of the neighbors until the sought information is found.
A user navigates the Windows file system hierarchy, for example, by iteratively viewing a directory—the file names and subdirectory names are these neighbors' “descriptions”—then selecting a neighboring directory to view, until the sought file is found. Windows offers multiple user interfaces for the viewing/selection process: a file-selection dialog in applications; successive directory views starting with “My Computer”; a “tree view” in Windows Explorer; and even a command line shell which permits displaying and changing the “current” directory.
Other, richer user interfaces for presenting and navigating hierarchies have been proposed. Some, such as “cone trees”, attempt to represent much of a hierarchy using 3D effects to convey relationships on a crowded display. Several use “focus+context” techniques; that is, the portion of the hierarchy upon which the user is currently focused, such as a current directory, is presented in full, and portions further from this focus are presented with progressively less detail. This can be achieved by wrapping a 2D representation of the tree about a curved surface and shading parts of the view away from the focus (these two techniques create a “fish-eye lens” effect), by fractal techniques, or by nesting boxes so that rectangles representing child nodes fill the rectangle representing the parent (“tree-maps”). Some techniques depict the nodes as objects in a 3D landscape, with more distant nodes appearing smaller.
As for navigation, a theme which is common from “tree view” to “tree-maps” is to detect user input selecting a node (as by a mouse click “on” the node) and redraw the view of the hierarchy with the selected node as the new “focus”. A few user interfaces portray the change in views with an animated sequence of intermediate views to suggest an object-like persistence. Some user interfaces, e.g. the 3D landscapes, allow a mode of navigation where the hierarchy view changes continuously, suggesting flight over the landscape.
Hierarchically organized information is ubiquitous. Computer file systems, dictionaries, indexes, tables of contents, and XML documents are hierarchical. The functions available in some applications are organized hierarchically in menus. On the web, many portals and retail sites are organized hierarchically. Web sites are not constrained to be hierarchical, but, again, hierarchy is a clear way to organize large amounts of information.
SUMMARY
In general, in one aspect, the invention features identifying a hierarchy position in a space defined by a hierarchy of nodes. The space has at least two dimensions. Each node is uniquely identifiable within the space by values in the respective dimensions, including a node level identifying the node's hierarchy level and a node-in-level identifying the node uniquely among nodes in that level. The hierarchy position is identified by position values in the same dimensions. Position values need not correspond to actual node level or node-in-level values.
Implementations of the invention may include one or more of the following features.
The position values may include depth value and position-within-level values both in the form of non-integral numbers. The position-within-level value may include a node-in-level value identifying one node plus a floating-point number representing an offset of the position from that node. The hierarchy position may be used to identify a focus of a user's view of the hierarchy.
In general, in another aspect, the invention features displaying representations of nodes of a hierarchy in a space on a display, each node representation fully occupying a subspace within the space, and allocating the space entirely to the subspaces.
Implementations of the invention may include one or more of the following features. The nodes are organized in levels in the hierarchy and the space is allocated among the levels so that one level is fully represented in a dimension of the display that corresponds to changing levels. The levels of the hierarchy above and below the one level are at least partially represented. Each of the levels is represented as a band in the space. Nodes represented in one band have a parent-child relationship with nodes represented in an adjacent band. Within a band, space is allocated so that the subspace of a parent has the same dimension along the band as the sum of the dimensions of its children along the adjacent band.
In general, in another aspect, the invention features rendering a container associated with the node and a representation of information associated with the node. The container has dimensions that change with an amount of space dynamically allocated to the node based on a changing focus in the hierarchy. The representation has unchanging dimensions. The container and the representation are drawn on a display. When the focus changes, the container is re-rendered with updated dimensions and drawn on the display. Without re-rendering, the rendered representation is recopied to a new location.
In implementations of the invention, the drawn container indicates the node's position in the hierarchy and its relationship to nearby nodes, and the representation includes graphics or text or both.
In general, in another aspect, information is received indicating a displacement of a user input device within a two-dimensional frame of reference. Displacement in at least one of the dimensions is translated to a rate of change of a hierarchy position used to identify a focus of a user's view of the hierarchy.
In general, in another aspect, the invention features displaying a representation of a portion of a hierarchy of nodes to a user. Each node may have associated an action to be performed by an application, the action being other than navigation of the hierarchy. A user navigates in the displayed representation of the portion of the hierarchy by using a first type of action. The user triggers the action associated with a displayed node of the hierarchy by invoking the node using a second type of action.
In implementations of the invention, the first type of action may be dragging and the second type of action may be clicking.
In general, in another aspect of the invention an emulation of a return-to-center input device enables a user to navigate the hierarchy. The user manipulates a non-return-to-center input device to indicate an intended manipulation of the emulation for purposes of navigating the hierarchy. The user's manipulation is treated as a manipulation of the return-to-center input device.
Implementations of the invention may include one or more of the following features. The non-return-to-center input device is a computer mouse, trackball, or pad. The return-to-center input device is a joystick. The emulation includes rendering the device on a display. The response to the user manipulation is to change a focus position in the hierarchy. The focus position is changed by periodically adding a focus increment vector to a focus position, the focus increment vector being a function of the vector by which the emulated controller is displaced from its center or rest position. The user manipulates the non-return-to-center controller in a single dragging action to view an arbitrarily large hierarchy of nodes. The function is nonlinear to permit the user to vary navigation velocity over a wide two-dimensional range.
In anoth
Fish & Richardson P.C.
Hong Stephen S.
Huynh Conglac
Survol Interactive Technologies
LandOfFree
Navigating heirarchically organized information does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Navigating heirarchically organized information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Navigating heirarchically organized information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2997556