Saturday, November 21, 2009

Hilbert Space notes

DDJ journal article on space filling curves
example code aa799.txt from the zip file.
Google's Uzaygezen project
Geo::Hash perl module, which has a nice clean implementation
GeoHash uses Z encoding.
The DDJ article does a nice job comparing the Z-curve and Hilbert curve. They're both nice ways to convert 2-space to 1-space, which is easier to search via b-tree.

A downside of the standard Hilbert curve is that the x and y space must be the same size. The standard procedure is to inflate the smaller dimension and then produce a curve for the full space. This is wasteful of space and processing time. Compact Hilbert Indices are an idea to make a modified form that doesn't require equal dimensions. That paper was published in 2007, and other than Uzaygezen doesn't seem to have been cited/used yet. So let's get started!

No comments: