Method and apparatus for storing and retrieving multi-dimensional data in computer memory
First Claim
1. A method of storing multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, in computer memory, comprising:
- selecting a first group of a number of dimensions and a second group of a number of dimensions;
allocating a first portion of memory which contains cells corresponding to combinations of the members of the first group of dimensions;
allocating a second portion of memory which contains a plurality of data blocks, each containing cells corresponding to combinations of the members of the second group of dimensions, wherein each data block corresponds to a different combination of the first group of dimensions, and the size of the data blocks depends upon the dimensions selected and the number of members in each;
storing each unit of data in the data block which corresponds to the combination of members of the first group of dimensions which identifies that unit of data, and in the location within that data block which corresponds to the combination of members of the second group of dimensions which identifies that unit of data; and
inserting a pointer to each data block corresponding to a particular combination of members of the first group of dimensions in the cell in the first portion of memory which corresponds to the same combination of members of the first group of dimensions.
5 Assignments
0 Petitions
Reexaminations
Accused Products
Abstract
A method and apparatus for storing and retrieving multi-dimensional data in which a multi-level data structure is defined wherein one level contains those dimensions chosen by the user to result in dense data and the other level contains the remaining sparse data combinations. The dense dimensions specified in any given case are used to determine the basic block size used to store information. The remaining sparse dimensions are used to create the upper level structure which is used to point to the block which contains the desired information. Depending upon the sparseness of the data, different types of upper level structure may be used. Both the variable data block size and the choice of pointer structure may be used to balance the memory required against the speed of retrieval. Once the data structure is created, the data in the data blocks, and the pointers in one type of upper level pointer structure, may be retrieved by simple calculation of the offset of the desired cell in memory rather than requiring a search.
-
Citations
19 Claims
-
1. A method of storing multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, in computer memory, comprising:
-
selecting a first group of a number of dimensions and a second group of a number of dimensions; allocating a first portion of memory which contains cells corresponding to combinations of the members of the first group of dimensions; allocating a second portion of memory which contains a plurality of data blocks, each containing cells corresponding to combinations of the members of the second group of dimensions, wherein each data block corresponds to a different combination of the first group of dimensions, and the size of the data blocks depends upon the dimensions selected and the number of members in each; storing each unit of data in the data block which corresponds to the combination of members of the first group of dimensions which identifies that unit of data, and in the location within that data block which corresponds to the combination of members of the second group of dimensions which identifies that unit of data; and inserting a pointer to each data block corresponding to a particular combination of members of the first group of dimensions in the cell in the first portion of memory which corresponds to the same combination of members of the first group of dimensions. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An apparatus for storing multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, in computer memory, comprising:
-
input means for selecting a first group of a number of dimensions and a second group of a number of dimensions; means for allocating a first portion of memory which contains cells corresponding to combinations of the members of the first group of dimensions; means for allocating a second portion of memory which contains a plurality of data blocks, each of which contains cells corresponding to combinations of members of the second group of dimensions, and wherein each data block corresponds to a different combination of the first group of dimensions, and the size of the data blocks depends upon the dimensions selected and the number of members in each; means for storing each unit of data in the data block which corresponds to the combination of members of the first group of dimensions which identifies that unit of data, and in the location within that data block which corresponds to the combination of members of the second group of dimensions which identifies that unit of data; and means for inserting a pointer to each data block corresponding to a particular combination of members of the first group of dimensions in the cell in the first portion of memory which corresponds to the same combination of members of the first group of dimensions. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. An apparatus for retrieving multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, comprising:
-
memory means containing the multi-dimensional data, in which a first portion of the memory contains cells corresponding to combinations of the members of a first group of one or more of the dimensions and a second portion of the memory contains a plurality of data blocks, each having cells corresponding to combinations of the members of a second group of one or more of the remaining dimensions, and wherein the cells in the first portion of memory contain pointers to the data blocks which correspond to the combinations of the members of the first group of dimensions represented by the cells; input means for receiving input signals from a user which indicate the members of the dimensions of the data desired by the user; and processing means responsive to the input signals for calculating the location of the cell in the first portion of memory containing the pointer to the block of data which contains the desired data, then calculating which cell within the block of data indicated by the pointer contains the data, and retrieving the data from the indicated cell.
-
-
18. An apparatus for allowing a plurality of users to retrieve multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, comprising:
-
memory means containing the multi-dimensional data, in which a first portion of the memory contains cells corresponding to combinations of the members of a first group of one or more of the dimensions and a second portion of the memory contains a plurality of data blocks, each having cells corresponding to combinations of the members of a second group of one or more of the remaining dimensions, and wherein the cells in the first portion of memory contain pointers to the data blocks which correspond to the combinations of the members of the first group of dimensions represented by the cells; a plurality of input means for receiving input signals from users which indicate the members of the dimensions of the data desired by the users; a plurality of processing means responsive to the input signals for generating command signals; server means responsive to the command signals from the plurality of processing means for calculating the location of the cell in the first portion of memory containing the pointer to the block of data which contains the data desired by each user, then calculating which cell within the block of data indicated by the pointer contains the data, and retrieving the data from the indicated cell.
-
-
19. A method of retrieving multi-dimensional data, each unit of which is identified by one or more members of each of a plurality of dimensions, and which is stored in memory in which a first portion of the memory contains cells corresponding to combinations of the members of a first group of one or more of the dimensions and a second portion of the memory contains a plurality of data blocks, each having cells corresponding to combinations of the members of a second group of one or more of the remaining dimensions, and wherein the cells in the first portion of memory contain pointers to the data blocks which correspond to the combinations of the members of the first group of dimensions represented by the cells, comprising:
-
means for receiving input signals from a user which indicate the members of the dimensions of the data desired by the user; means for calculating from the input signals the location of the cell in the first portion of memory containing the pointer to the block of data which contains the desired data; means for calculating from the input signals which cell within the block of data indicated by the pointer contains the desired data; and retrieving the data from the indicated cell.
-
Specification