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.

Publications

PhD Thesis: The Application of Space-filling Curves to the Storage and Retrieval of Multi-dimensional Data (2000)
Abstract
Thesis: compressed postscript   pdf

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.
Abstract
(slides of BNCOD presentation)
Paper: compressed postscript  pdf

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)
Abstract
Article: compressed postscript  pdf

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)
Abstract
Report: compressed postscript  pdf
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
Abstract
Report: compressed postscript  pdf (corrected July 2009)
Source code: mapping.c
Code to test mapping.c: here

US Patent

US Patent no. 7,167,856, issued January 23, 2007
"Method of storing and retrieving multi-dimensional data using the Hilbert Curve"
J.K.Lawder.

`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.

    dos version
    linux version * updated January 2011 *
    unix version
    Source code - added January 2011



Any queries or feedback? email me at jkl@dcs.bbk.ac.uk