Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-07-28
2002-03-12
Mizrahi, Diane D. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S216000, C709S223000, C709S239000
Reexamination Certificate
active
06356902
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the storage, retrieval and organization of multimedia objects in a distributed and federate fashion. These multimedia objects may contain synchronized audio and video information, audio and video in unsynchronized form, general data and executable codes. The storage method used enables scalability and allows efficient managing, naming and administering of multimedia objects in a heterogeneous manner. The present invention relates to a storage method for enhancing retrieval of multimedia objects by minimizing the amount of memory, which the search algorithm must, traversed during data retrieval and storage.
2. Description of the Prior Art
Data processing systems often utilize “trees” structure for data storage. A “tree” structure is a structure containing a “root” node and a plurality number of “tree” and “leaf” nodes in which there is only one path between any nodes in the tree. In a tree structure, the “root” node is in the highest level, the “tree” nodes are in an intermediate level and the leaf nodes are in a lowest level. The tree structure may be an efficient way that provides a hierarchy for large segments of data and retrieving specific segment of data. Segments of data are stored in the nodes of the tree structure.
In the case of a 3 level tree structure, the tree structure consists of a “root” node as a first level, a second level of tree nodes and a third level of “leaf” nodes. To store data in this tree structure, main data segment can be stored in the “root” node and some other sub-data stored in the “tree” nodes. Another sets of nodes under each “tree” nodes are further categorized into “leaf” nodes of the respective “tree” nodes. In order for storage and retrieval of data segment in a tree structure, the tree structure is traversed. To allow traversal nodes in the tree structure where the data segments reside, each node in the tree structure must carry sufficient pointer information for the memory location of lower layer “tree” nodes or “leafs” nodes. The pointer information is referred to as the link of the nodes. For the “root” node and each “tree” node in a tree structure, there must be N number of memory pointers to register the location of each node at a lower layer which contains N number “tree” or “leaf” nodes. As a consequence, there is a tendency for the “root” node and “tree” nodes in a tree structure of arbitrary size in terms of nodes to have a limited number of “tree” or “leaf” nodes for the adjacent level of nodes.
While other some tree structure requires a “balanced” structure, that is, a tree structure in which all but the bottom nodes are completely filled. It could be possible to map an “unbalanced” tree structure to a balanced tree structure by introducing null nodes into the “balanced” tree structure By doing this, redundancy is introduced. Introducing null nodes has a harmful effect on the memory size requirement of virtual memory data processing systems, wherein fixed-length blocks of memory often referred to as “page” are utilized. Each node of a tree memory in a virtual memory may result in none continuous storage of nodes because of redundant nodes being introduced. In the virtual memory, this may result in a page fault, if “paging” is utilized, which greatly increase the amount of time required to retrieve data within a tree structure.
To represent a tree structure in a graph node, as discussed in “Data Structure and Algorithm Analysis in C″, Benjamin/Cummings publishing Co., Inc, 1993, requires 2 memory pointers to store the location of 'sibling” and “child” node. Sibling node is a node in the same level while “child” node is a node in a lower level of the tree structure. Using 2 pointers allows allocation of memory of the “leaf” nodes to be located in non-adjacent memory location. Again this has a deleterious effect on the paging scheme used in the virtual memory as described in the preceding paragraph.
SUMMARY OF THE INVENTION
The present invention provides a method of providing an efficient data storage and data retrieval while retaining the hierarchy of a tree, eliminating the problem of conventional branches to facilitate searching and to improve multimedia objects retrieval by preventing the problem of page faults which may encountered during traversing from occurring.
The present invention provides an improved method of solving the problem encountered in managing and allocating pointer memory of “root” node and each “tree” node for adjacent level of “leaf” nodes and “tree” nodes in a multilevel tree structure. In conventional methods, more than 2 memory pointers are required for each “tree” node to retain the hierarchical structure of a tree. The present invention uses a single pointer memory location to store the location of next node while still retaining a substantial amount of information of the tree structure.
The present invention also provides a method for preventing multimedia objects from random fragmentation found during storing and retrieving data fragmented in segments of smaller pieces of data of unequal size in the case where each data segment has a strong coupling which can be best represented in a hierarchical form.
The present invention provides means to reduce the complexity of a tree structure by decomposing a highly complex and unmanageable tree structure into a highly manageable format that aids in retrieval of multimedia objects that are strongly coupled or data that are related with minimal memory paging fault.
This invention provides an improved method and system for enhancing data retrieval and storage in a multilevel tree structure by significantly reducing the required amount of time and memory that must be traversed during data retrieval and data storage for both depth-first and breath-first search.
To resolve the problems outlined in the above section, the invented method and system provides means of decomposing a tree structure of any arbitrary form into a graph map with either breath or depth coupling by mapping nodes of the tree structure into nodes with a single vertex; means of organizing the nodes in the graph map into page memory to improve paging during data retrieval; means to traverse efficiently with minimal paging fault for data or multimedia objects with strong coupling; means of traversing in depth-first search in a depth coupled graph map without page fault using an efficient traversing algorithm; and means of traversing in a breadth-first search in a breadth coupled graph map without page fault using an efficient traversing algorithm.
Storage of multimedia objects organized in a hierarchical ordered tree nodes is efficiently performed by decomposing the tree nodes organized in a conventional tree structure into graph nodes with a single-link to register location of graph nodes which is a representative of child tree nodes. The multimedia objects organized in a series of single-link graph nodes can then be stored in a distributed and federated manner providing a system for managing and administering the multimedia objects. The graph nodes are compacted into page memory based on either a depth coupled or breadth coupled multimedia objects to minimized paging fault during multimedia objects retrieval. To enable fast retrieval of the multimedia objects organized in a sequence of graph nodes, a depth-first and breadth-first algorithm is designed to enable fast retrieval and browsing of the specific multimedia objects stored in page memory as graph nodes.
As used herein, the use of the terms “federated” or “federated manner” refer to a manner whereby multimedia objects organized as different branches of a tree structure are managed by different entities. In other words, “federated” refers to a structure where different entities manage different branches or parts of a tree structure. As used herein, the use of the phrases “distributed” or “distributed manner” refer to a manner whereby the different parts or branches of a tree structure (i.e. multimedia objects organized into a tree with logical inter-c
Chen Jianfeng
Ng Kok Leong
Tan Pek Yew
Matsushita Electric - Industrial Co., Ltd.
Mizrahi Diane D.
LandOfFree
Method and system for storage and retrieval of multimedia... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for storage and retrieval of multimedia..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for storage and retrieval of multimedia... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840152