Hilbert-Geohash - Hashing Geographical Point Data Using the Hilbert Space-Filling Curve

Abstract

As geographic information systems become more and more widely used, an increasing amount of positional data is generated and shared between users. Sharing spatial data introduces challenges, with URLs containing lengthy coordinates needing to be sent through services with character limits. This problem has been solved with the usage of geospatially-specific URL-shortening systems, using properties of space-filling curves to reduce the multiple dimensions of point data, down to a shorter, URL-friendly, hash value.

An example of such a system is the Geohash.org service, using the Z-order space-filling curve to map between hash values and geographical points. While the Z-order curve is simple, alternative space-filling curves of higher complexity exist, possessing several theoretical advantages and disadvantages. One such alternative is the Hilbert curve, which presumably has superior hashing properties at the cost of being computationally more complex. Thus, the Hilbert-curve based point data hashing system \textit{hilbert-geohash}, is implemented to determine whether these properties are worth the additional complexity they introduce.

The results show that the Hilbert curve is, to some extent, applicable within the context point-data hashing, but that the complexity increment is not proportional to the practical benefits over the Z-order curve. While a point-data hashing system is not fully capable of exploiting the specific advantages of the Hilbert-curve, a proposed distributed point-data retrieval system should be capable of doing so. This proposed system would use the presented \textit{hilbert-geohash} system as a crucial part of its hash-space addressing mechanism, taking advantage of the properties of the Hilbert curve to reduce communication distances between peers in the distributed network.