Patent ID: 7167856
Filing Date: 2007-01-23
Classification: G06F,Y10S

Abstract:
1. A method of storing multi-dimensional data or multi-dimensional data points, in a multi-dimensional database and retrieving subsets of said multi-dimensional data according to the specification of a query comprising: 1 providing a computer memory which is able to store said multi-dimensional data at a series of addresses in said memory, 2 providing a means of transforming by calculation of multi-dimensional points including said multi-dimensional data into one-dimensional values by mapping said multi-dimensional data to one-dimensional distance values along an approximation of a Hilbert space-filling curve that passes through all multi-dimensional points corresponding to possible data values in the domain of said multi-dimensional database, 3 providing a means of partitioning said multi-dimensional data into an ordered sequence of subsets of said multi-dimensional data so that each said subset of said multi-dimensional data comprises multi-dimensional data that maps to lower said one-dimensional distance values than all succeeding said subsets of said multi-dimensional data, 4 providing a means of identifying each said subset of said multi-dimensional data together with the location in said computer memory in which each said subset of multi-dimensional data is stored, 5 providing a means of indexing locations in said computer memory of said subsets of said multi-dimensional data, 6 providing a means of specifying a query region or query as a multi-dimensional rectangular region within said domain of said database, 7 providing a calculation method utilizing bit-wise manipulation of said one-dimensional distance values along an approximation of a Hilbert space-filling curve for identifying for retrieval and searching which said subsets of said multi-dimensional data intersect with any said query, the calculation method comprising the steps of: whereby said database and its index adapt efficiently to insertion and deletion of said multi-dimensional data, and whereby subsets of multi-dimensional data that intersect with a query region can be identified efficiently for searching and retrieval of multi-dimensional data that lies within the query region.