Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-29
2003-11-25
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06654761
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to controlling which part of a body of node-link data is in memory.
BACKGROUND AND SUMMARY OF THE INVENTION
Netscape Navigator is a web browser that saves data about a number of recently visited web pages, making it possible to view the saved pages without accessing them through the web. A user can navigate through the saved pages by following links between them or by providing other navigation signals, such as by clicking on “Next” and “Back” buttons in the page frame presented by the browser. When a space limit is reached, previously saved pages are deleted to make room for newly visited pages.
Koike, H. and Yoshihara, H., “Fractal Approaches for Visualizing Huge Hierarchies”,
Proceedings of the
1993
IEEE Symposium on Visual Languages,
Bergen, Norway, Aug. 24-27, 1993, pp. 55-60, disclose how fractal-based methods of information display can control the number of displayed nodes of a huge hierarchical structure. Fractal views calculate the degree of importance of each node and decide which node should be displayed or erased by comparing each node's value with a threshold. Once the threshold is set, the number of displayed nodes is constant, to keep the system's response time, and possibly the cognitive load, constant.
Matsuura, T., Taniguchi, K., Masuda, S., and Nakamura, T., “A Graph Editor for Large Trees with Browsing and Zooming Capabilities”,
Systems and Computers in Japan,
Vol. 24, No. 8, 1993, pp. 35-46, disclose a library program which allows direct manipulation of a large tree on a display. Because of screen size limitations, the disclosed program displays both an outline of a tree and details of one or more parts of the tree. The user can use a mouse to move the selected region that is displayed in detail.
Beaudet et al., U.S. Pat. No. 5,515,487, disclose selective display of portions of graphics by expanding and collapsing nodes in trees, directed acyclic graphs, and cyclic graphs.
Windows NT Explorer is a program that can be used to see the hierarchy of folders on a disk drive. Some folders are presented with plus signs (+), and if the user does a mouse click on a plus sign, more folders will be displayed.
The invention addresses problems in storing in memory a body of data defining a node-link structure, referred to herein as “node-link data”. In a simple case, all the node-link data defining a structure can be stored in memory, including additional data for presenting all or part of the structure. But this technique is not adequate in many situations.
One situation that requires a different technique is when node-link data defining a large or complex structure are greater than the available memory space. Another is when node-link data are not all concurrently available, due, for example, to low speed retrieval from a remote source or to modifications occurring elsewhere in parts of the data.
The invention provides techniques that alleviate these problems in storing node-link structures. The techniques control which part of node-link data defining a structure is in memory. In performing one of a series of iterations, each of which includes automatically traversing a set of elements in the node-link structure;, each of the techniques modifies which part of node-link data is in the memory so that the part of node-link data in the memory is likely to define the set of elements that will be traversed by the next iteration.
Each iteration in the series could be any operation that accesses data relating to elements within node-link data defining the structure. Each iteration could, for example, prepare and present a representation of the node-link structure. Other examples of operations that can automatically traverse elements include display operations such as layout, mapping, and painting; other operations that obtain positions of elements in a space; search or retrieval operations; operations that obtain data characterizing the structure, such as by scanning the elements of the structure; operations that make decisions based upon or relating to the structure by analyzing its elements; and so forth.
In modifying which part of node-link data is in memory, the iteration can determine whether to remove any of the node-link data from memory. Upon determining to do so, the iteration can apply a criterion to determine which part to remove. For example, each iteration can receive a navigation signal, and the criterion can be a navigation history criterion. More generally, the criterion can select an element that is least recently traversed, such as from a list of nodes defined by the part of node-link data in memory, with the nodes ordered within the list according to how recently each node has been traversed.
In modifying which part of node-link data is in memory, the iteration can also determine whether any of the elements traversed by the iteration have children that are not defined by the part of node-link data in memory. For example, the techniques can access uncreated children data that indicate, for each node defined by the part of node-link data in memory, whether the node has children that are not defined by the part of the node-link data in memory. If the iteration's set of elements includes an element with undefined children, the iteration can determine to modify the part of node-link data in memory to define the undefined children.
The part of node-link data in memory can include a node element representing each node in the iteration's set of elements, and the part can be modified by adding an additional node element representing a node that is not in the set of elements. Similarly, an additional link element can be added representing a link to the added node. Further, the part of node-link data in memory can include at least one node element representing a node that is not in the iteration's set of elements, and the part can be modified by deleting at least one such node element. Similarly, for each deleted node element, at least one link element can be deleted that represents a link to or from the represented node.
The techniques can be implemented in a system with memory for storing node-link data and a processor for controlling which part of the node-link data is in memory. The techniques can also be implemented in an article of manufacture with a storage medium storing instruction data for execution by a processor. The techniques can also be implemented in a method of transferring instruction data between two machines.
The new techniques are advantageous because they make it possible to load a very large node-link structure incrementally as well as to unload and reload parts of the structure as necessary. The new techniques can accomplish these objectives even though the part of the node-link data in memory can occupy no more than a fixed amount of memory. Furthermore, the techniques can apply criteria based on user input indicating interest in different elements of the structure. As a result, in an implementation in which a user provides navigation signals requesting that selected elements of the node-link structure be displayed, the part of the structure in memory is likely to include the elements the user will select for display.
Another advantage is that the new techniques can be combined with and used to implement cacheing and prefetching of node-link data defining a structure.
Yet further advantages arise because less data is transferred in and out of memory, and because data transfer occurs only when necessary. As a result, the initial display of a large node-link structure can be presented much more quickly, and less computation is necessary to present the node-link structure.
In comparison with conventional cacheing techniques, such as the Netscape web page cacheing techniques described above, the new techniques can be implemented to provide a more easily understood representation of the node-link structure. Although the new techniques may be applied to the same types of underlying node-link structures as conventional techniques, the new techniques can be implemented
Lamping John O.
Rao Ramana B.
Tenev Tichomir G.
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Inxight Software, Inc.
Ly Anh
Vu Kim
LandOfFree
Controlling which part of data defining a node-link... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Controlling which part of data defining a node-link..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Controlling which part of data defining a node-link... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3177761