Multidimensional data ordering

• US 6,460,026 B1
• Filed: 03/30/1999
• Issued: 10/01/2002
• Est. Priority Date: 03/30/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pasumansky, Mosha
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/281,053
• Time in Patent Office: 1,281 Days
• Field of Search: 707/1-10, 707/101, 707/103, 707/104, 707/530, 345/424, 345/425, 345/426
• US Class Current: 707/737
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method, apparatus, software and data structure is disclosed for more efficient mapping of three dimensional data to linear storage mediums. These embodiments provide that multidimensional space is divided into volumes based on the priority of levels of one or more dimensions. Spatial to linear mapping is then applied to the multidimensional data such that records in the same volume will be close to each other. According to another aspect, a data structure is provided wherein data from a multidimensional space is stored in a one-dimensional space in a storage medium in accordance with the above-described method.

Claims

1. A method for storing multidimensionally organized data in a one-dimensional space in a storage medium, the multidimensionally-organized data having a first number of dimensions and comprising a plurality of cells, each of the cells being identifiable by a number of attributes equal to the first number, each of the attributes corresponding to one of the dimensions, the method comprising:

dividing the multidimensionally-organized data into two or more volumes based on a priority of at least two levels of at least one dimension of the multidimensionally-organized data, each of said levels representing a grouping of cells among the range of cells of the attribute that corresponds to said one dimension; and

storing data from the multidimensional space in the storage medium with the data from each volume clustered together.

2. A method according to claim 1 wherein a dimension includes one or more levels.

3. A method according to claim 1 wherein the data in each volume is clustered according to a simple ordering.

4. A method according to claim 1 wherein the data in each volume is clustered according to an ordering of greater than one order.

5. A method according to claim 1 wherein the data in each volume is clustered according to an ordering selected from the group:

the z-curve, Gray coding and Hilbert ordering.

6. An on-line analytical processing system wherein multidimensionally-organized data is stored in a one-dimensional space in a storage medium, the multidimensionally-organized data having a first number of dimensions and comprising a plurality of cells, each of the cells being identifiable by a number of attributes equal to the first number, each of the attributes corresponding to one of the dimensions, the multidimensionally-organized data divided into two or more volumes based on a priority of at least two levels of at least one dimension of the multidimensionally-organized data, each of said levels representing a grouping of cells among the range of cells of the attribute that corresponds to said one dimension, the multidimensionally-organized data stored in the storage medium with the data from each volume clustered together.

7. A system according to claim 6 wherein the processing system includes software operative to automatically adjust the priorities of levels based on actual queries presented to the system.

8. A system according to claim 6 wherein the data in each volume is clustered according to a simple ordering.

9. A system according to claim 6 wherein the data in each volume is clustered according to an ordering of greater than one order.

10. A system according to claim 6 wherein the data in each volume is clustered according to an ordering selected from the group:

the z-curve, Gray coding and Hilbert ordering.

11. A data structure wherein multidimensionally-organized data is stored in a one dimensional space in a storage medium, the multidimensionally-organized data having a first number of dimensions and comprising a plurality of cells, each of the cells being identifiable by a number of attributes equal to the first number, each of the attributes corresponding to one of the dimensions, the multidimensionally-organized data divided into two or more volumes based on a hierarchy of members of at least one dimension of the multidimensionally-organized data, the multidimensionally-organized data stored in the storage medium with the data from each volume clustered together.

12. A data structure according to claim 11 wherein the data in each volume is clustered according to a simple ordering.

13. A data structure according to claim 11 wherein the data in each volume is clustered according to an ordering of greater than one order.

14. A data structure according to claim 11 wherein the data in each volume is clustered according to an ordering selected from the group:

the z-curve, Gray coding and Hilbert ordering.

15. An on-line analytical processing system comprising:

a client;

a server;

a relational database;

a multidimensional data store;

wherein the client is connected to the server, and the server is connected to the relational data base; and

the server including software operative on the server for storing data obtained from the relational database in the multidimensional data store, wherein multidimensionally-organized data to be accessed by the server is stored in a one-dimensional space in a storage medium, the multidimensionally-organized data having a first number of dimensions and comprising a plurality of cells, each of the cells being identifiable by a number of attributes equal to the first number, each of the attributes corresponding to one of the dimensions, the multidimensionally-organized data divided into two or more volumes based on a priority of at least two levels of at least one dimension of the multidimensionally-organized data, each of said levels representing a grouping of cells among the range of cells of the attribute that corresponds to said one dimension, the multidimensionally-organized data stored in the storage medium with the data from each volume clustered together.

16. A system according to claim 15 wherein the processing system includes software operative to automatically adjust the priority of levels based on actual queries presented to the system.

17. A computer program encoded in a computer readable medium, the computer program operative on a suitably configured computer for mapping multidimensionally-organized data to a one-dimensional space in a storage medium, the multidimensionally-organized data having a first number of dimensions and comprising a plurality of cells, each of the cells being identifiable by a number of attributes equal to the first number, each of the attributes corresponding to one of the dimensions, the computer program operative to divide the multidimensionally-organized data into two or more volumes based on a priority of at least two levels of at least one dimension of the multidimensionally-organized data, each of said levels representing a grouping of cells among the range of cells of the attribute that corresponds to said one dimension, and to store the multidimensionally-organized data stored in the storage medium with the data from each volume clustered together.

18. A computer program according to claim 17 wherein the computer program is further operative to automatically adjust the priority of levels of a dimension based on actual queries presented to the system.