Hilbert ordering of multidimensional tuples within computing systems

• US 9,146,948 B2
• Filed: 12/12/2006
• Issued: 09/29/2015
• Est. Priority Date: 12/12/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Grosset, Robin, Hood, David
• Primary Examiner(s): LIN, SHEW FEN
• Application Number:
  US11/609,531
• Publication Number:
  US 20080140682A1
• Time in Patent Office: 3,213 Days
• Field of Search: 707/3, 707/999.002, 707736-757
• US Class Current: 1/1
• 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, wherein each multidimensional data element is defined by a plurality of objects having different object types, wherein each object type is associated with a different dimension within a multidimensional data space, and wherein an object value is stored to each object;

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

applying, with a processor, 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 each of the Hilbert orderings to a respective record within a tree data structure allocated within a linear data storage structure,

wherein the tree data structure comprises a plurality of pages, wherein the plurality of pages comprises a first page having a first record corresponding to a first Hilbert value and a second record corresponding to a second Hilbert value, wherein the plurality of pages further comprises a second page having a third record corresponding to a third Hilbert value, and wherein the third Hilbert value is greater than the first Hilbert value and less than the second Hilbert value.

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 a requested Hilbert ordering from the tree data structure based on the determined request Hilbert ordering.

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

determining whether the request Hilbert ordering resides within the tree data structure; and

retrieving the requested Hilbert ordering from the tree data structure 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.

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.

10. The method of claim 1, wherein the multidimensional data elements comprise a first multidimensional data element that is associated with a measure, and wherein a record within the tree data structure to which the first multidimensional data element is stored stores the respective measure associated with the first multidimensional data element.

11. The method of claim 1, wherein the Hilbert orderings are used as keys to search the tree data structure.

12. A system comprising:

a programmable processor;

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

a tuple storage module, executing on the programmable processor, that receives multidimensional data elements to store to the B-tree, where each multidimensional data element is defined by a plurality of objects having different object types, wherein each object type is associated with a different dimension within a multidimensional data space, and wherein an object value is stored to each object,

wherein the tuple storage module forms a respective tuple for each of the multidimensional data elements at least in part by mapping each object value to an associated reference, 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 stores each of the Hilbert orderings to a respective record within the B-tree,

wherein the tuple storage module applies the Hilbert function to a subset of the references of the tuple, and

wherein the subset of references is selected based on a size of the respective dimension associated with each of the references.

13. The system of claim 12,

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 a requested Hilbert ordering based on the determined request Hilbert ordering.

14. The system of claim 13, 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.

15. The system of claim 13, 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.