Method and system for storing sparse data in memory and accessing stored sparse data
OwnerJohn S. Worleyinventor
Life of this patent
Estimating the term…
Loading patent…
OwnerJohn S. Worleyinventor
Estimating the term…
One embodiment of the present invention provides a hierarchical data structure for storing sparse data that can be traversed from root node to data-level node without incurring translation-cache misses. By contrast with currently used hierarchical data structures, the family of hierarchical data structures that represent one embodiment of the present invention employs non-data-level nodes that contain virtual-memory translations rather than memory references. The family of hierarchical data structures that represent one embodiment of the present invention are traversed from root node through successive layers of non-data-level nodes to data-level nodes in a manner similar to traversal of currently used hierarchical data structures. However, in the family of hierarchical data structures that represent one embodiment of the present invention, the address of a next-lower-level node is computed from a base address of the next-lowest level, and the computed address is furnished, along with the virtual-memory translation stored in a higher-level node, in order to access the next-lower-level node.
A method for storing a data entity having an index in a computer within a data structure having multiple node levels, the method comprising:
A method for transforming a hierarchical data structure that includes virtual-memory addresses in a root node and in intermediate level nodes into a computationally efficient hierarchical data structure, the method comprising:
A method for storing data entities in a computer within a data structure having multiple levels of nodes, the method comprising:
A system for storing and retrieving data comprising:
Dependencies are inferred from the claim text.