HILBERT ORDERING OF MULTIDIMENSIONAL TUPLES WITHIN COMPUTING SYSTEMS

• US 20080140682A1
• Filed: 12/12/2006
• Published: 06/12/2008
• Est. Priority Date: 12/12/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Cognos Incorporated (International Business Machines Corporation)
• Inventors: Hood, David, Grosset, Robin
• Granted Patent: US 9,146,948 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

A system provides multidimensional tuple Hilbert ordering within a linear storage structure to enable more consistent and efficient access to stored multidimensional tuples. The database system comprises a tuple storage module that receives multidimensional data elements, where each multidimensional data element is defined by a plurality of different object types, and where each object is associated with a different dimension within a multidimensional data space. The tuple storage module further forms a respective tuple for each of the multidimensional data elements by mapping each object to an associated reference and applies a Hilbert function to the references of each of the tuples to determine a respective Hilbert ordering for each of the tuples. The system further comprises a linear data storage structure that includes a B-tree for storing the Hilbert ordering.

Claims

1. A method comprising:

receiving multidimensional data elements, where each multidimensional data element is defined by a plurality of different object types, and where each object is associated with a different dimension within a multidimensional data space;

forming a respective tuple for each of the multidimensional data elements by mapping each object to an associated reference;

applying a Hilbert function to two or more of the references of each of the tuples to determine a respective Hilbert ordering for each of the tuples; and

storing the Hilbert orderings to a tree data structure allocated within a linear data storage structure,

wherein the tuples are arranged within the tree data structure in a sorted order such that a retrieval time of the tuples is substantially equal for two or more of the dimensions within the multi-dimensional space.

2. The method of claim 1, wherein applying the Hilbert function comprises applying the Hilbert function to all of the references of the tuple.

3. The method of claim 1, wherein applying the Hilbert function comprises applying the Hilbert function to a subset of the references of the tuple.

4. The method of claim 3, wherein applying the Hilbert function comprises selecting the subset of references to which to apply the Hilbert function based on a size of the respective dimension associated with each of the references.

5. The method of claim 1, further comprising:

receiving a request for the tuple, wherein the request includes one or more object values;

forming a standardized request by mapping each object value of the request to an associated reference;

applying the Hilbert function to the references of the standardized request to determine a request Hilbert ordering for the standardized request;

retrieving the requested Hilbert ordering from the B-tree based on the determined request Hilbert ordering.

9. The method of claim 1, wherein storing the Hilbert ordering comprises storing the Hilbert ordering to a B-tree data storage structure within an on-line analytical processing (OLAP) database.

6. The method of claim 6, wherein retrieving the requested Hilbert ordering comprises:

determining whether the request Hilbert ordering resides within the B-tree; and

retrieving the requested Hilbert ordering from the B-tree based on the determination.

7. The method of claim 6, further comprising forming the requested tuple by applying an inverse Hilbert function to the retrieved Hilbert ordering to determine the references that form the requested tuple.

8. The method of claim 7, further comprising determining the object values associated with the requested tuple by mapping the references of the requested tuple back to their associated object values.

10. A system comprising:

a linear storage structure that includes a B-tree for storing multidimensional data;

a tuple storage module that receives multidimensional data elements to store to the B-tree, where each multidimensional data element is defined by a plurality of different object types, and where each object is associated with a different dimension within a multidimensional data space,

wherein the tuple storage module forms a respective tuple for each of the multidimensional data elements by mapping each object to an associated reference,

wherein the tuple storage module applies a Hilbert function to two or more of the references of each of the tuples to determine a respective Hilbert ordering for each of the tuples, and

wherein the tuples are arranged within the B-tree in a sorted order such that retrieval of the tuples is substantially equal for two or more of the dimensions within the multi-dimensional space.

11. The system of claim 10, wherein the tuple storage module applies the Hilbert function to all of the references of the tuple.

12. The system of claim 10, wherein the tuple storage module applies the Hilbert function to a subset of the references of the tuple.

13. The system of claim 12, wherein the subset of references is selected based on a size of the respective dimension of the associated with each of the references.

14. The system of claim 10,

wherein the tuple storage structure further receives a request for the tuple, wherein the request includes one or more object values, forms a standardized request by mapping each object value of the request to an associated reference, and applies the Hilbert function to the references of the standardized request to determine a request Hilbert ordering for the standardized request, and

wherein the B-tree retrieves the requested Hilbert ordering based on the determined request Hilbert ordering.

15. The system of claim 14, wherein the B-tree retrieves the requested Hilbert ordering by:

determining whether the request Hilbert ordering resides within the B-tree; and

retrieving the requested Hilbert ordering from the B-tree based on the determination.

16. The system of claim 14, wherein the tuple storage system further forms the requested tuple by applying an inverse Hilbert function to the retrieved Hilbert ordering to determine the references that form the requested tuple.

17. The system of claim 14, wherein the tuple storage module further determines the object values associated with the requested tuple by mapping the references of the requested tuple back to their associated object values.

18. The system of claim 10, wherein the linear storage structure stores the Hilbert ordering by storing the Hilbert ordering to the B-tree within an on-line analytical processing (OLAP) database.

19. A computer-readable medium comprising instructions for causing a programmable processor to:

receive multidimensional data elements, where each multidimensional data element is defined by a plurality of different object types, and where each object is associated with a different dimension within a multidimensional data space;

form a respective tuple for each of the multidimensional data elements by mapping each object to an associated reference;

apply a Hilbert function to two or more of the references of each of the tuples to determine a respective Hilbert ordering for each of the tuples; and

store the Hilbert orderings to a B-tree.