US5970496A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for storing information in a computer system memory using hierarchical data node relationships
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-09-12
•
Granted: 1999-10-19
•
Expires: 2016-09-12
Abstract
Abstract A method, system, and data structure for storing information in a computer system memory using a directed acyclic graph structure having related data nodes. Any node can "own" other nodes in hierarchical relationships. Data is stored in a file structure with (1) a heap for storing chunks or nodes of data in memory locations, and (2) an index containing information about the relationships between nodes. Each node is referenced and accessed by information stored in the index. Each ownership relationship between nodes is referenced uniquely by the triple consisting of the identification of the parent node, the identification of the child node and a child identification value. The inclusion of a child identification value in the triple allows a node to be a child of another node a multiplicity of times. The index is a table of entries, one entry for each node. Each entry contains the identifier of the node and, if there are relationships with other nodes, a list of one or more references to child nodes. A data file constructed in accordance with the invention allows hierarchical data structures, multiple use of the same data, and cross-ownership of data, resulting in more efficient usage of memory.
Inventors
- 👤 Gary Shon Katzenberger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 20:12
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9024; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
111 words
A method for storing and presenting information in a computer system, comprising the steps of: creating a plurality of data nodes defining frame data playable or displayable on a user interface; storing instances of data nodes in a data file in a computer memory; linking the stored instances of the data nodes in a directed acyclic graph structure defining a plurality of parent and child objects in which each child object is linked to a plurality of parent objects; and displaying or playing the frame data on the user interface such that the stored instance of each child object is displayed or played in association with more than one parent object.
Claim 2
Independent Claim
111 words
A method for storing and presenting information in a computer system, comprising the steps of: creating a plurality of data nodes defining frame data playable or displayable on a user interface; storing instances of data nodes in a data file in a computer memory; linking the stored instances of the data nodes in a directed acyclic graph structure defining a plurality of parent and child objects in which each child object is linked to a plurality of parent objects; and displaying or playing the frame data on the user interface such that the stored instance of each child object is displayed or played in association with more than one parent object.
Claim 3
Dependent Claim
39 words
The method of claim 1, wherein the frame data comprises an element selected from the group consisting essentially of a picture, a representation of a three-dimensional object, a sound, a text string, a video, a sprite, and alphanumeric data.
Claim 4
Dependent Claim
30 words
The method of claim 2, wherein the data file comprises: a header for storing file information; a heap comprising a plurality of segments containing the frame data; and an index.
Claim 5
Dependent Claim
45 words
The method of claim 3, wherein the file information includes a version number, an address of the index storing a representation of the directed acyclic graph, a file type, a file length, an origination application type, a date of creation, and a date of modification.
Claim 6
Dependent Claim
38 words
The method of claim 3, further comprising a free map segment comprising a plurality of data entries selected from the group comprising pointers to free segments in the heap, and information stating the size of the free segments.
Claim 7
Dependent Claim
57 words
The method of claim 3, wherein the index comprises a two-dimensional array having a plurality rows, wherein each row corresponds to an associated one of the data nodes and comprises: a first column containing chunk attributes for the associated data node; and a second column comprising a list of child objects linked to the associated data node.
Claim 8
Dependent Claim
46 words
The method of claim 6, wherein chunk attributes are selected from the group consisting essentially of a chunk type, a chunk number, an offset, a length, a lower status flag, a number of children, a number of parent, a data compression flag, and run time ID.
Claim 9
Dependent Claim
29 words
The method of claim 6, wherein the child object list contains attributes selected from the group consisting essentially of a chunk type, a chunk number, and a child ID.
Claim 10
Dependent Claim
84 words
The method of claim 6, further comprising steps for carrying out a create object operation for adding a new parent and/or child object to the data file, comprising the steps of: allocating a block of memory in the heap for storing information associated with the new object; creating a new row in the index for the new object; storing chunk attributes for the new object in the new index row; and storing the information associated with the new object in the block of memory.
Claim 11
Dependent Claim
82 words
The method of claim 6, further comprising steps for carrying out an add parent/child relationship to the data file, comprising the steps of: locating a row in the index associated with a parent object for the parent/child relationship; creating an entry in the child list for the parent object identifying a child object for the parent/child relationship; incrementing a child object counter in the index for the parent object; and incrementing a parent object counter in the index for the child object.
Claim 12
Dependent Claim
111 words
The method of claim 6, further comprising steps for carrying out a delete object operation for deleting an object in the data file, comprising the steps of: locating a row in the index associated with the object to be deleted; examining a parent object counter associated with the object to be deleted, and in response to the parent object counter being non zero, recursively deleting a parent/child relationship and decrementing the parent object counter for object to be deleted until the parent object counter is equal to zero; and in response to the parent object counter being zero, deleting the row in the index associated with the object to be deleted.
Claim 13
Dependent Claim
162 words
The method of claim 6, further comprising the steps for carrying out a clone object operation for duplicating objects and their hierarchical relationships from a source file to a destination file without utilizing preexisting objects in the destination file, comprising the steps of: determining whether an entry for an object to be cloned exists in the index of the destination file; in response to determining that an entry for the object to be cloned exists in the index of the destination file, establishing a different entry in the index of the destination file for the object to be cloned; in response to determining that no entry for the object to be cloned exists in the index of the destination file, utilizing the entry in the index of the source file associated with the object to be cloned; and performing a create object operation to add information corresponding to the object in to be cloned as a new object in the destination file.
Claim 14
Dependent Claim
55 words
The method of claim 12, wherein the step for carrying out a create object operation comprises the steps of: allocating a contiguous block of memory in the destination file; creating a new entry in the index for the new object in the destination file; storing attributes associated with the object in the new entry index.
Claim 15
Dependent Claim
31 words
The method of claim 13, further comprising the steps of carrying out in the destination file the cloning operation recursively for each child object associated with the object to be cloned.
Claim 16
Dependent Claim
39 words
The method of claim 13, further comprising the steps of determining whether an object to be cloned has previously been copied during the cloning operation, and if it has, using the previously created copy in establishing the hierarchical relationship.
Claim 17
Dependent Claim
177 words
The method of claim 6, further comprising the step for carrying out a copy operation for duplicating objects and their hierarchical relationships from a source file to a destination file utilizing at least one preexisting objects in the destination file, comprising the steps of: examining the value of a run time ID attribute associated with the object to be copied; establishing a unique run time ID attribute if the object to be copied does not have a run time ID attributes; if the object has a run time ID attribute, examining the run time ID attribute in the destination file to determine whether the object to be copied corresponds to a preexisting object in the destination file; in response to a determination that the object to be copied corresponds to the preexisting object in the destination file, utilizing the preexisting object as the copy; in response to a determination that there is no corresponding preexisting object in the destination file, executing steps for cloning the object to be copied from the source file to the destination file.
References Cited (Backward Citations)
US5310349A
Cited
US5430870A
Cited
US5640556A
Cited
US5613134A
Cited
US5621874A
Cited
US5742821A
Cited
US5704017A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-18 | 2003-04-19 | 2003-10-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-18 | 2007-04-19 | 2007-10-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-18 | 2011-04-19 | 2011-10-19 | $7700.00 | Window Closed / Lapsed |