HILBERT ORDERING OF MULTIDIMENSIONAL TUPLES WITHIN COMPUTING SYSTEMS
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 9)
-
-
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. - View Dependent Claims (7, 8)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
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.
-
Specification