Method of storing and retrieving multi-dimensional data using the hilbert curve

Abstract

A method of partitioning and indexing multi-dimensional data that maps data to one-dimensional values according to the sequence in which an approximation of a Hilbert space-filling curve passes through all of the points corresponding to potential multi-dimensional data in a data space. Data is partitioned into ordered pages, each corresponding to a length of Hilbert curve and identified by the sequence of the first point on it. Practical application of the indexing method is made viable and useful by the provision of an efficient querying algorithm enabling data lying within any given hyper-rectangular query region to be retrieved. This is achieved by successively calculating ever higher sequence numbers of potential data points lying within a query region and each being the lowest such value for a point lying on a different curve section. Thus a single calculation is performed to identify each page potentially containing data of interest.