Geohash


Geohash is a public domain geocode system invented in 2008 by Gustavo Niemeyer and G.M. Morton, which encodes a geographic location into a short string of letters and digits. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape, which is one of the many applications of what is known as a Z-order curve, and generally space-filling curves.
Geohashes offer properties like arbitrary precision and the possibility of gradually removing characters from the end of the code to reduce its size. Geohashing guarantees that the longer a shared prefix between two geohashes is, the spatially closer they are together. The reverse of this is not guaranteed, as two points can be very close but have a short or no shared prefix.

History

The core part of the Geohash algorithm and the first initiative to similar solution was documented in a report of G.M. Morton in 1966, "A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing". The Morton work was used for efficient implementations of Z-order curve, like in , based on directly interleaving 64-bit integers. But his geocode proposal was not human-readable and was not popular.
Apparently, in the late 2000s, G. Niemeyer still didn't know about Morton's work, and reinvented it, adding the use of base32 representation. In February 2008, together with the announcement of the system, he launched the website http://geohash.org, which allows users to convert geographic coordinates to short URLs which uniquely identify positions on the Earth, so that referencing them in emails, forums, and websites is more convenient.
Many variations have been developed, including OpenStreetMap's short link in 2009, the 64-bit Geohash in 2014, the exotic Hilbert-Geohash in 2016, and others.

Typical and main usages

To obtain the Geohash, the user provides an address to be geocoded, or latitude and longitude coordinates, in a single input box, and performs the request.
Besides showing the latitude and longitude corresponding to the given Geohash, users who navigate to a Geohash at geohash.org are also presented with an embedded map, and may download a GPX file, or transfer the waypoint directly to certain GPS receivers. Links are also provided to external sites that may provide further details around the specified
location.
For example, the coordinate pair 57.64911,10.40744 produces a slightly shorter hash of u4pruydqqvj.
The main usages of Geohashes are:
Geohashes have also been proposed to be used for geotagging.
When used in a database, the structure of geohashed data has two advantages. First, data indexed by geohash will have all points for a given rectangular area in contiguous slices. This is especially useful in database systems where queries on a single index are much easier or faster than multiple-index queries. Second, this index structure can be used for a quick-and-dirty proximity search: the closest points are often among the closest geohashes.

Technical description

A formal description for Computational and Mathematical views.

Textual representation

For exact latitude and longitude translations Geohash is a spatial index of base 4, because it transforms the continuous latitude and longitude space coordinates into a hierarchical discrete grid, using a recurrent four-partition of the space. To be a compact code it uses base 32 and represents its values by the following alphabet, that is the "standard textual representation".
The "Geohash alphabet" uses all digits 0-9 and almost all lower case letters except "a", "i", "l" and "o".
For example, using the table above and the constant, the Geohash ezs42 can be converted to a decimal representation by ordinary positional notation:

Geometrical representation

The geometry of the Geohash have a mixed spatial representation:
Is possible to build the "И-order curve" from Z-order by merging neighboring cells and indexing the result rectangular grid by the function j=floor. The side illustration shows how to obtain the grid of 32 rectangular cells from the grid of 64 square cells.
The most important property of Geohash for humans is that it preserves spatial hierarchy in the code prefixes.
For example, in the "1 Geohash digit grid" illustration of 32 rectangles, above, the spatial region of the code e is preserved with prefix e in the "2 digit grid" of 1024 rectangles.

Algorithm and example

Using the hash ezs42 as an example, here is how it is decoded into a decimal latitude and longitude. The first step is decoding it from textual "base 32ghs", as showed above, to obtain the binary representation:
This operation results in the bits 01101 11111 11000 00100 00010. Assuming that counting starts at 0 in the left side, the even bits are taken for the longitude code, while the odd bits are taken for the latitude code.
Each binary code is then used in a series of divisions, considering one bit at a time, again from the left to the right side. For the latitude value, the interval -90 to +90 is divided by 2, producing two intervals: -90 to 0, and 0 to +90. Since the first bit is 1, the higher interval is chosen, and becomes the current interval. The procedure is repeated for all bits in the code. Finally, the latitude value is the center of the resulting interval. Longitudes are processed in an equivalent way, keeping in mind that the initial interval is -180 to +180.
For example, in the latitude code 101111001001, the first bit is 1, so we know our latitude is somewhere between 0 and 90. Without any more bits, we'd guess the latitude was 45, giving us an error of ±45. Since more bits are available, we can continue with the next bit, and each subsequent bit halves this error. This table shows the effect of each bit. At each stage, the relevant half of the range is highlighted in green; a low bit selects the lower range, a high bit selects the upper range.
The column “mean value” shows the latitude, simply the mean value of the range. Each subsequent bit makes this value more precise.
Final rounding should be done carefully in a way that
So while rounding 42.605 to 42.61 or 42.6 is correct, rounding to 43 is not.

Digits and precision in km

geohash lengthlat bitslng bitslat errorlng errorkm error
123±23±23 ±2500
255 ±2.8 ±5.6 ±630
378 ±0.70 ±0.70  ±78
41010 ±0.087 ±0.18  ±20
51213 ±0.022 ±0.022   ±2.4
61515 ±0.0027 ±0.0055   ±0.61
71718 ±0.00068 ±0.00068   ±0.076
82020 ±0.000085 ±0.00017   ±0.019

Limitations when used for deciding proximity

Edge cases

Geohashes can be used to find points in proximity to each other based on a common prefix. However, edge case locations close to each other but on opposite sides of the 180 degree meridian will result in Geohash codes with no common prefix. Points close to the North and South poles will have very different geohashes.
Two close locations on either side of the Equator will not have a long common prefix since they belong to different 'halves' of the world. Put simply, one location's binary latitude will be 011111... and the other 100000...., so they will not have a common prefix and most bits will be flipped. This can also be seen as a consequence of relying on the Z-order curve for ordering the points, as two points close by might be visited at very different times. However, two points with a long common prefix will be close by.
In order to do a proximity search, one could compute the southwest corner and northeast corner of a bounding box and search for geohashes between those two. This search will retrieve all points in the z-order curve between the two corners, which can be far too many points. This method also breaks down at the 180 meridians and the poles. Solr uses a filter list of prefixes, by computing the prefixes of the nearest squares close to the geohash .

Non-linearity

Since a geohash is based on coordinates of longitude and latitude the distance between two geohashes reflects the distance in latitude/longitude coordinates between two points, which does not translate to actual distance, see Haversine formula.
Example of non-linearity for latitude-longitude system:
Note that these limitations are not due to geohashing, and not due to latitude-longitude coordinates, but due to the difficulty of mapping coordinates on a sphere to two dimensional coordinates and the difficulty of exploring a two dimensional space uniformly. The first is related to Geographical coordinate system and Map projection, and the other to Hilbert curve and z-order curve. Once a coordinate system is found that represents points linearly in distance and wraps up at the edges, and can be explored uniformly, applying geohashing to those coordinates will not suffer from the limitations above.
While it is possible to apply geohashing to an area with a Cartesian coordinate system, it would then only apply to the area where the coordinate system applies.
Despite those issues, there are possible workarounds, and the algorithm has been successfully used in Elasticsearch, MongoDB, HBase, Redis, and Accumulo to implement proximity searches.

Similar indexing systems

An alternative to storing Geohashes as strings in a database are , which are also called spatial keys and similar to QuadTiles.
In some geographical information systems and Big Data spatial databases, a Hilbert curve based indexation can be used as an alternative to Z-order curve, like in the S2 Geometry library.
In 2019 a front-end was designed by QA Locate in what they called GeohashPhrase to use phrases to code Geohashes for easier communication via spoken English language. There were plans to make GeohashPhrase open source.

Licensing

The Geohash algorithm was put in the public domain by its inventor in a public announcement on February 26, 2008.
While comparable algorithms have been successfully patented and
had copyright claimed upon, GeoHash is based on an entirely different algorithm and approach.