Compact Hilbert Indices


Chris Hamilton

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2


Space-filling curves are continuous self-similar functions which map compact multi-dimensional sets into one-dimensional ones. Since their invention they have found applications in a wide variety of fields [12, 21]. In the context of scientific computing and database systems, space-filling curves can significantly improve data reuse and request times because of their locality properties [9, 13, 15]. In particular, the Hilbert curve has been shown to be the best choice for these applications [21]. However, in database systems it is often the case that not all dimensions of the data have the same cardinality, leading to an inefficiency in the use of space-filling curves due to their being naturally constrained to spaces where all dimensions are of equal size. We explore the Hilbert curve, reproducing classical algorithms for their generation and manipulation through an intuitive and rigorous geometric approach. We then extend these basic results to construct compact Hilbert indices which are able to capture the ordering properties of the regular Hilbert curve but without the associated inefficiency in representation for spaces with mismatched dimensions.

Tech Report Number: 
Report Date: 
July 24, 2006
PDF icon CS-2006-07.pdf960.77 KB