Hilbert Sort

Problem

Setup and Motivation

Consider a problem in which we are trying to store/pack up spatial data in an efficient way. We need a way of sorting the data in such a way that (x,y) data that are located in nearby regions to one another will live closer in memory to one another. This speeds up access to the data in memory.

If we sort by, say, x-coordinates, and let y-coordinates break ties, then we end up with points with very similar x values but dissimilar y values. These are inefficient and spread out the points in memory. (x,y) data points that are far away in space end up being neighbors in memory, and vice-versa.

Using Euclidean distance is another possible approach, but this does not utilize direction, and so you can again end up with points that are similar distances from a reference point, but in opposite directions, leading to data points that are far away in space becoming neighbors in memory.

If we imagine this problem getting much larger - for example, if the set of (x,y) data points becomes millions of points on a map - the Hilbert sort provides a way to pack up data in a way that preserves local, spatial structure. The closer two given points are in memory, the shorter the interval time between visits by the space-filling curve.

Space Filling Curves

Space filling curves are curves that are capable of "filling up" a finite area with longer and longer distances.

We can think of space-filling curves as being parameterized on a numerical parameter that controls the amount of curvature or the degree of "packing" of the curve.

The way that space-filling curves are constructed is to create a pattern, then scale it down and repeat it, attaching the subsequent scaled-down, repeated curves.

Mathematician Giuseppe Peano was the first to discover the space filling curves. His Peano curve is an example of a triplet curve that is scaled down by 1/3 on both sides and repeated 9 times:

David Hilbert then expanded on the idea with a new curve in a paper published in 1890, subsequently called the Hilbert curve.

Hilbert Curve

The Hilbert Curve is a particular space-filling curve invented by David Hilbert, a famous mathematician who lived around the turn of the 20th century and is recognized as a universally influential mathematician.

Hilbert proposed the construction of a space-filling curve based on bending a line at two additional points. By starting with a squared-off U shape, the curve is repeated by shrinking it in half on both sides, and repeating it 4 times, connecting each of the four curves.

The Hilbert Curve can be drawn in a region bounded by the four points (0,0), (0,S), (S,0), (S,S). Construct it by splitting the square into four quadrants meeting at (S/2, S/2). Recursively fill them with a rotated and scaled copy of the curve.

Given (x,y) coordinate locations, sort them according to when the Hilbert Curve visits them. If the number of nodes on the grid, S, is odd, then the curve will not intersect itself and each integer point will only be visited once.

Solution Approach

The Hilbert Curve sort problem can be solved by observing a simple fact: the coarsest level of quadrant organization takes precedence over finer grained levels of quadrant organization. So, if one point is in the southwest corner and one point ins in the northeast corner, then no matter what iteration it takes for the Hilbert Curve to visit those two points, we definitely know that the curve will visit the southwest corner before it visits the northeast corner.

This begins to take on the characteristics of a recursive method: our "base case" is the simple comparison of one or no points in each of our four quadrants. If we get to this base case, we know the order in which the Hilbert Curve will visit each of those points.

If we are not at the base case, if we have a large number of points to sort, we can bin together all the points in a given quadrant, and consider the order in which those points go with an additional level of finer granularity.

Implementation Details

The biggest challenge to implementing this is dealing with the rotation of the curve for the southwest and southeast corners.

There are a couple of ways to handle the rotation - there's a messy conditional approach, and a more elegant approach that transforms the (x,y) data in a bin, rather than trying to transform the bin to fit the (x,y) data.

Conditional Approach

The first way is to look at two different levels when binning points into quadrants; that allows you to say, "if point A is in the southeast quadrant on this level, and was in the southwest quadrant on the prior level, then it should go second, but if it was in the northwest quadrant on the prior level, then it should go fourth, etc."

This is clunky and awkward to code, and you wind up with a bunch of nested if/else statements.

Transform the Data, Not the Bin

The second way is to say, okay, when we bin these (x,y) points into their respective quadrants, the only thing we care about is what order they're visited by the Hilbert Curve, and that only depends on what quadrant they're in, so we can actually change the (x,y) values to be anything we want - as long as we don't change the order in which they would be visited by the Hilbert curve. Which is to say, which quadrants they're in.

This technique can be thought of as transforming the (x,y) data associated with each point to fit the bin structure, rather than transforming the bin structure to fit the (x,y) data.

For example, the southwest corner is always inverted and rotated 90 degrees. So rather than trying to account for that inversion and rotation when looking at the (southwest, northwest, northeast, and southeast