Hacker News Reader

Comment by jacobolus | Hacker News Reader

The linked presentation slides give a bit better explanation IMO: https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSn...

Too bad there aren’t more general docs for the library.

I still don’t quite understand the benefit of using a single number instead of a pair of numbers for describing a cell in a two-dimensional space. Seems like a pair of 32-bit fixed point numbers would be just as descriptive as a single double-precision float along the hilbert curve.

The way they project the sphere onto a cube also leads to cell shapes that aren’t especially relevant to typical human purposes, whereas there are many shapes on a map which align with the latitude/longitude grid.

View on HN

The purpose of the space filling curve is to preserve locality when you store the two dimensional data on a one dimensional storage medium. If you used x and y coordinates and stored the data like an image row by row, then data of cells adjacent in the x direction would get stored close together but data of cells adjacent in the y direction would get stored quite a bit away because of the other cells of the rows in between. On the other hand the Hilbert curve keeps cells adjacent in both directions closer together and therefore preserves locality better which in turn means less read head repositioning on spinning disks or a better hit probability when you prefetch adjacent data.

It also allows you to do the opposite, and turn a single-dimensional quantity into two-dimensional coordinates in a useful manner.

The most famous example I know is, of course, XKCD's Map of the Internet:

https://xkcd.com/195/

It isn't a matter of representation, but also how data structures could take advantage of such representations. B-trees for instance are very efficient with one-dimensional data. Take a look here: http://www.drdobbs.com/database/space-filling-curves-in-geos...

I think that if you used a pair of numbers you wouldn't be able to do the fast "checking of containment" described by the author, which is just a bitwise comparison apparently. I don't think they use a floating point representation for the 1D hilbert space coordinate.

The checking of containment, to verify if a cell is contained in another cell, all you just have to do is to do a prefix comparison. These operations are really fast and they are possible only due to the Hilbert Curve enumeration and the hierarchical decomposition method used.

If you had a pair of numbers you could do two bitwise comparisons instead. If you packed both 32-bit fixed point numbers into one 64-bit integer, you might even be able to handle both parts with the same few instructions. In the worst case it would be within a factor of two of the Hilbert-curve version in terms of instructions, and I highly doubt this operation is ever a bottleneck in practice. Would be interesting to see some benchmarks.

Reply on news.ycombinator.com