Patent US5359724A successfully refreshed from Google Patents.
US5359724A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for storing and retrieving multi-dimensional data in computer memory
Assignee: Oracle International Corp
•
Filing: 1992-03-30
•
Granted: 1994-10-25
•
Expires: 2012-03-30
Abstract
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.
Inventors
- 👤 Robert J. Earle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 16:28
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0207; G06F40/00; G06F40/10; G06F40/166; G06F40/177; G06F40/18; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
228 words
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.
Claim 2
Independent Claim
228 words
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.
Claim 3
Dependent Claim
38 words
The method of claim 1 wherein the step of inserting a pointer to each data block further comprises the step of selecting the manner in which the cells in the first portion of memory are to be organized.
Claim 4
Dependent Claim
30 words
The method of claim 1 wherein the first portion of memory is a block pointer array which contains all possible combinations of the members of the first group of dimensions.
Claim 5
Dependent Claim
32 words
The method of claim 1 wherein the first portion of memory is a binary tree containing only those combinations of the members of the first group of dimensions for which data exists.
Claim 6
Dependent Claim
49 words
The method of claim 1 further comprising the step of selecting an order for the dimensions and their members, and wherein the step of creating a plurality of data blocks further comprises ordering the cells in each data block in the same order established for the dimensions and members.
Claim 7
Dependent Claim
35 words
The method of claim 5 wherein the step of selecting an order for the dimensions and their members comprises the step of creating an outline of the dimensions and their members in the desired order.
Claim 8
Dependent Claim
37 words
The method of claim 5 wherein the step of allocating a second portion of memory further comprises arranging the cells contained in each block in an order corresponding to the order of the dimensions and their members.
Claim 9
Dependent Claim
55 words
The method of claim 7 wherein the multi-dimensional data is organized in a regular pattern, and the step of storing the data further comprises the step of recognizing the pattern in which the data is organized and inserting each unit of data into the corresponding cell in the corresponding data block based upon that pattern.
Claim 10
Independent Claim
241 words
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.
Claim 11
Independent Claim
241 words
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.
Claim 12
Dependent Claim
26 words
The apparatus of claim 9 further comprising means for selecting the manner in which the cells in the first portion of memory are to be organized.
Claim 13
Dependent Claim
30 words
The apparatus of claim 9 wherein the first portion of memory is a block pointer array which contains all possible combinations of the members of the first group of dimensions.
Claim 14
Dependent Claim
32 words
The apparatus of claim 9 wherein the first portion of memory is a binary tree containing only those combinations of the members of the first group of dimensions for which data exists.
Claim 15
Dependent Claim
48 words
The apparatus of claim 9 further comprising means for selecting an order for the dimensions and their members, and wherein the means for creating a plurality of data blocks further comprises ordering the cells in each data block in the same order established for the dimensions and members.
Claim 16
Dependent Claim
34 words
The apparatus of claim 13 wherein the step of selecting an order for the dimensions and their members comprises means for creating an outline of the dimensions and their members in the desired order.
Claim 17
Dependent Claim
39 words
The apparatus of claim 13 wherein the means for allocating a second portion of memory further comprises means for arranging the cells contained in each block in an order corresponding to the order of the dimensions and their members.
Claim 18
Dependent Claim
55 words
The apparatus of claim 15 wherein the multi-dimensional data is organized in a regular pattern, and the means for storing the data further comprises the means for recognizing the pattern in which the data is organized and inserting each unit of data into the corresponding cell in the corresponding data block based upon that pattern.
Claim 19
Independent Claim
207 words
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.
Claim 20
Independent Claim
207 words
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.
Claim 21
Independent Claim
237 words
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.
Claim 22
Independent Claim
237 words
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.
Claim 23
Independent Claim
209 words
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.
Claim 24
Independent Claim
209 words
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.
References Cited (Backward Citations)
US3624616A
Cited
US4051551A
Cited
US4313159A
Cited
US4570236A
Cited
US4809156A
Cited
US5055998A
Cited
US5130924A
Cited
US5247632A
Cited
US5257365A
Cited
US5280547A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-24 | 1998-04-25 | 1998-10-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-24 | 2002-04-25 | 2002-10-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-24 | 2006-04-25 | 2006-10-25 | $7700.00 | Window Closed / Lapsed |