The S2 Geometry library homepage
An interesting approach to representing geospatial data - most systems use a 2D projection of the Earth, but this uses a cube that is then projected onto a sphere. This system not only has low distortion compared to a 2D projection, but its cell ID scheme is also cleverly engineered. It’s conceptually similar to geohashes - divide the Earth into a grid and give each block in the grid an ID - although it uses Hilbert curves instead of Z-curves.
S2 divides the Earth into 6 faces - this is level 0. In the cell ID, level 0 takes up 3 bits to represent faces 0 through 5: 000, 001, 010, 011, 100, 101. At each subsequent level (1 through 30), the face is further subdivided into four regions, each of which is represented by 2 bits - 00, 01, 10, 11. At the end, the binary form of 0.5 is added to represent the exact middle point of the subdivision (see Hilbert curves).
Combining the face id (3 bits), level ids (up to 60 bits), and binary 0.5 (1 bit) forms the subdivision’s cell ID: a unique representation of the subdivision and its midpoint that fits into a 64-bit integer. The 31 levels of subdivision can represent areas of less than 1 square centimeter. A further benefit from S2’s use of Hilbert curves is that cell IDs close in value tend to be geographically close - more so than Z-curves as used in geohashes (reference).
I wonder if double-indexing with S2, one at a certain rotation and the other offset by half, would be worth it to further remove edge cases where points are close but IDs are not?
A much longer, and much more thorough, write-up of S2
More detail on the construction of the cell IDs from the S2 library site
A blog post that illustrates some of the benefits of S2 over geohash