What this research is about
The research work relates to methods of querying multidimensional data that is indexed by mapping it to a 'Hilbert space-filling' curve. In a nutshell, the mapping technique enables the effective provision of all possible secondary indexes over multidimensional data using a *single* index, such as a simple B-Tree. This provides flexible data access while saving the overhead of maintaining multiple indexes. The querying method itself allows the mapping technique to be put to practical use - for range as well as point queries.
PhD Thesis: The Application of Space-filling Curves to the Storage and Retrieval of Multi-dimensional Data (2000)
Thesis: compressed postscript
J.K.Lawder and P.J.H.King. Using Space-filling Curves for Multi-dimensional Indexing.
In Brian Lings & Keith Jeffery, editors, Advances in Databases:
proceedings of the 17th British National Conference on Databases
(BNCOD 17), volume 1832 of Lecture Notes in Computer Science, pages
20 - 35. Springer Verlag, July 2000.
(slides of BNCOD presentation)
J.K.Lawder and P.J.H.King. Querying Multi-dimensional Data Indexed Using the Hilbert Space-Filling Curve.
ACM Sigmod Record 30(1):19-24 (March 2001)
(formerly Research Report BBKCS-00-04 or JL3/00, September 2000)
J.K.Lawder and P.J.H.King. Using State Diagrams for Hilbert Curve Mappings.
International Journal of Computer Mathematics 78(3):327-342 (2001)
(formerly Research Report BBKCS-00-02 or JL2/00, August 2000)
How to generate Hilbert curve state diagrams: Source code
J.K.Lawder. Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve.
Research Report BBKCS-00-01
(formerly JL1/00), August 2000
postscript pdf (corrected July 2009)
Source code: mapping.c
Code to test mapping.c: here
US Patent no. 7,167,856, issued January 23, 2007
"Method of storing and retrieving multi-dimensional data using the Hilbert Curve"
`The MASH File' -- Demonstration Software
Demonstration version of the software implementation of the application.
This software is available for non-profit making / non-commercial use and evaluation purposes.
The software includes a (very) simple menu-driven demonstration program allowing a database to be created and updates
and queries to be made. Object files and headers are available for inclusion in your own programs.
Programs are written in C++. Currently available for unix (solaris 5.7), linux and dos (windows 95).
Just click on the appropriate platform link below. Instructions included.
linux version * updated January 2011 *
Source code - added January 2011
Any queries or feedback? email me at