Navigating heirarchically organized information

• US 6,496,842 B1
• Filed: 05/28/1999
• Issued: 12/17/2002
• Est. Priority Date: 05/28/1999
• Status: Expired due to Term

• Current Assignee: Stanley Lyness
• Original Assignee: Survol Interactive Technologies
• Inventors: Lyness, Stanley W.
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US09/322,720
• Time in Patent Office: 1,299 Days
• Field of Search: 707/514, 707/907, 345/356, 345/357, 345/848-854
• US Class Current: 715/206
• CPC Class Codes: G06F 16/168 Details of user interfaces specifically adapted to file systems, e.g. browsing and visualisation, 2d or 3d GUIs query results presentation G06F16/156
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus

Abstract

Hierarchies are navigated easily through a user interface that is continuous in its presentation of node information and may be implemented using a small display space.

Claims

1. A method comprising

identifying a position in a space associated with a hierarchy of nodes, each of the nodes being uniquely identifiable within the hierarchy by a node level value identifying the node'"'"'s level in the hierarchy and a node-in-level value identifying the node'"'"'s location uniquely among nodes in that level,

the space associated with the hierarchy of nodes having at least two dimensions, the position in the space being identified by a depth value comprising the node level value and an offset from that node level value and a position-in-level value comprising the node-in-level value and an offset from the node-in-level value.

2. The method of claim 1 in which the depth value offset comprises a non-integral number.

3. The method of claim 1 in which the position-in-level value offset comprises a non-integral number.

4. The method of claim 3 in which the position-in-level value comprises a node-in-level value identifying one node plus a floating-point number representing an offset of the position from that node.

5. The method of claim 1 further comprising using the position in the space to identify a focus of a user'"'"'s view of the hierarchy.

9. The method of claim 1 or 6 also comprising

an area that provides a navigational interface that permits continuous navigation, based on a user'"'"'s continuous activation of a user interface device, of a hierarchy of nodes, the interface displaying information about a portion that is less than all of the hierarchy at one time, the portion changing apparently continuously in response to the user'"'"'s continuous activation of the user interface device.

10. The method of claim 9 in which the nodes comprise links to web pages.

12. The method of claim 1, 6, or 11 also comprising

for a node in the hierarchy of nodes, rendering an outline and a representation of node-specific information, the outline having dimensions that change with an amount of space dynamically allocated to the node based on a changing focus in the hierarchy, the representation having unchanging dimensions,

drawing the outline and the representation on a display, and when the focus changes,

re-rendering the outline with updated dimensions, and

without re-rendering, copying the rendered representation to a new location.

13. The method of claim 12 in which the drawn container indicates the node'"'"'s position in the hierarchy and its relationship to nearby nodes.

14. The method of claim 13 in which the representation includes graphics or text or both.

15. The method of claim 1, 6, or 11 also comprising

receiving information indicating current displacement of a user input device within a two-dimensional frame of reference from a zero position, and

translating the received information indicating the current displacement in at least one of the dimensions to a rate of change of position of a user'"'"'s focus in a display of a portion of the hierarchy.

16. The method of claim 15 in which one dimension represents a depth in the hierarchy and the other dimension represents position-in-level.

19. The method of claim 1, 6, or 11 also comprising

displaying a representation of a portion of the hierarchy of nodes,

providing a software emulation of a return-to-center input device for enabling a user to navigate the hierarchy, and

in response to the user manipulating a non-return-to-center input device to indicate an intended manipulation of the emulation for navigating the hierarchy, treating the user'"'"'s manipulation as a manipulation of the return-to-center input deice.

20. The method of claim 19 in which the non-return-to-center input device comprises a computer mouse, trackball, or pad.

21. The method of claim 19 in which the return-to-center input device comprises a joystick.

22. The method of claim 19 in which the emulation includes rendering the device on a display.

23. The method of claim 19 in which the response to the user manipulation is to change a focus position in the hierarchy.

24. The method of claim 23 in which 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.

25. The method of claim 24 in which the function is nonlinear to permit the user to vary navigation velocity over a wide two-dimensional range.

26. The method of claim 19 in which the user manipulating the non-return-to-center controller in a single dragging action enables the user to view an arbitrarily large hierarchy of nodes.

27. The method of claim 1, 6, or 11 also comprising

at a client device, displaying information about a portion of the hierarchy of nodes, the portion changing as a focus position changes,

fetching, from a server, as a result of no user interaction other than navigation, information about portions of the hierarchy that are approaching view, including information not previously fetched about descendant nodes of currently displayed nodes, and

representing each node as the displayed portion of the hierarchy changes to include the node.

28. The method of claim 1, 6, or 11 also comprising

receiving at a server a request from a client for information about the hierarchy,

in response to the request, providing to the client information about only a portion but not all of the hierarchy, the portion including references to information about other portions of the hierarchy, and

determining the size of the portion to be provided to the client adaptively based on parameters for optimizing communication between the server and the client.

29. The method of claim 28 in which each of the portions comprises a sub-hierarchy of the hierarchy.

30. The method of claim 28 in which the server automatically builds a hierarchy definition portion that is as near as possible in size to a given minimum portion size.

31. The method of claim 28 in which the server generates references to sub-hierarchies and includes them with definitions of nodes of the portion provided.

32. The method of claim 28 in which the server includes hardware or software.

33. The method of claim 28 in wich the server is remote from the client.

34. The method of claim 28 in which the server resides on a different machine, separated by a network, from the machine on which the client resides.

35. The method of claims 1, 6, or 11 in which the nodes comprise links to web pages.

36. The method of claim 1, 6, or 11 in which the hierarchy comprises a hierarchical function menu.

37. The method of claim 1, 6, or 11 in which the hierarchy comprises a hierarchical file system.

38. The method of claim 1, 6, or 11 in which the hierarchy comprises a document encoded in XML or an extension thereof.

39. The method of claim 1, 6, or 11 in which the hierarchy comprises a hierarchical index constructed from a document, list, or table.

40. The method of claim 1, 6, or 11 in which the hierarchy comprises an encoded hierarchy.

41. The method of claim 1, 6, or 11 in which the hierarchy comprises the Dewey Decimal System.

42. The method of claim 1, 6, or 11 in which the hierarchy comprises categorized products.

43. The method of claim 1, 6, or 11 in which the hierarchy comprises postal addresses or other location by geographic region.

44. The method of claim 1, 6, or 11 in which the hierarchy comprises characters belonging to a character set to be selected for text entry.

45. The method of claim 1, 6, or 11 in which the hierarchy comprises a corpus which is not hierarchical in its native form and upon which hierarchy has been imposed using a similarity-seeking technology.

46. The method of claim 1, 6, or 11 also comprising

displaying a portion that is less than all of the hierarchy at a browser,

enabling a user to navigate continuously through levels and nodes of the hierarchy based on a user'"'"'s continuous activation of a user interface device, the portion that is displayed changing apparently continuously with the user'"'"'s continuous activation of the user interface device, and

during navigation delivering portions of the hierarchy from a remote server to the browser in time to enable the continuous navigation.

6. A method comprising

dividing an area on a display into subareas, each position in the area belonging to one of the subareas;

each of the subareas associated with a node in the hierarchy of nodes;

the entire area of each of the subareas representing the associated node at a given time, and

receiving an indication of an action to be taken, the indication being received at any arbitrary position within the area of the display at the given time, the indication being unambiguously associated with the node associated with the subarea that contains the arbitrary position.

7. The method of claim 6 in which the nodes in the hierarchy are organized in levels and at least some of the nodes of one level are fully represented in a direction of the display that corresponds to different levels, and at least some of the nodes of levels of the hierarchy above and below the one level are at least partially represented.

8. The method of claim 7 in which each of the levels is represented as a band of node representations in the area, nodes represented in one band have a parent-child relationship with nodes represented in an adjacent band, and, within a band representing one level, the area is divided so that the subarea allocated to a parent node in that one level has the same extent along the band as the sum of the extents of the subareas in the adjacent band representing another level that are allocated to the children of the parent node.

11. A method comprising

displaying a representation of a portion of a hierarchy of nodes to a user,

enabling a user to vary the portion of the hierarchy that is displayed by performing a first type of user-interface action not directed within the displayed representation of the portion of the hierarchy, the change in the portion of the hierarchy that is displayed being accompanied by a change in the scale at which at least some of the nodes of the portion are displayed,

allowing, by a second type of user-interface action directed within the displayed representation of the portion of the hierarchy, a selection of any node in the portion of the hierarchy of nodes of which a representation is being displayed, and

reporting each selection to an application to invoke node-specific behavior by the application, the node-specific behavior being other than affecting the representation of the hierarchy, and the application being other than the representation and navigation of the hierarchy.

17. A The method of claim 11 in which the first type of action comprises dragging.

18. The method of claim 11 in which the second type of action comprises clicking and releasing.

47. A method comprising

displaying a representation of a portion of a hierarchy of nodes to a user,

enabling a user to vary the portion of the hierarchy displayed and the scale and degree of detail at which any node is represented by a first type of user-interface action performed outside of the displayed representation of the portion of the hierarchy,

allowing, by a second type of user-interface action within the displayed representation of the portion of the hierarchy, the selection of any node in the portion of the hierarchy of nodes of which a representation is being displayed, and

reporting each selection to an application to invoke node-specific behavior in the application, the node-specific behavior being other than affecting the representation of the hierarchy, and the application being other than the representation and navigation of the hierarchy.