Spatial Index: Grid Systems

Grid Systems in spatial indexing using GeoHash and Google S2

This post is a continuation of Stomping Grounds: Spatial Indexes, but don’t worry if you missed the first part—you’ll still find plenty of new insights right here.

3. Geohash

Geohash: Invented in 2008 by Gustavo Niemeyer, it encodes a geographic location into a short string of letters and digits. It’s a hierarchical spatial data structure that subdivides space into buckets of grid shape using a Z-order curve ( Section 2.).

3.1. Geohash — Intuition

Earth is round or, more accurately, an ellipsoid. Map projection is a set of transformations that represent the globe on a plane. In a map projection. Coordinates (latitude and longitude) of locations from the surface of the globe are transformed to coordinates on a plane. And GeoHash Uses Equirectangular projection

The core of GeoHash is just a clever use of Z-order curves. Split the map-projection (rectangle) into 2 equal rectangles, each identified by unique bit strings.