Spatial Search and Plotting Using Geohashes
===========================================
Introduction
------------
A geohash is an encoded character string that is computed from geographic
coordinates. For example the approximate latitude and longitude of The National
Center For Ecological Analysis and Synthesis is 34.419279, -119.698472 from
which the geohash of *9q4gu1y4z* can be derived. The geohash algorithm is
bidirectional, so geographic coordinates can be encoded into geohashes and
geohashes can be decoded to obtain coordinates.
Geohashes have the property that characters can be incrementally removed from
the right side of the geohash to represent a geographic location less
precisely. A geohash is an approximation of a point, where each length of the
geohash corresponds to a rectangle (a geohash tile) that is an approximation of
the original encoded geographic coordinate.
This feature of geohashes can be useful for searching and plotting at different
resolutions.
Table 1 shows the relationship between geohash length and the size of the
rectangle represented by that geohash at the equator.
.. table:: **Table 1** Geohash Tile Sizes
======= =====================
Length Tile Size
======= =====================
1 5,009.4km x 4,992.6km
2 1,252.3km x 624.1km
3 156.5km x 156km
4 39.1km x 19.5km
5 4.9km x 4.9km
6 1.2km x 609.4m
7 152.9m x 152.4m
8 38.2m x 19m
9 4.8m x 4.8m
10 1.2m x 59.5cm
11 14.9cm x 14.9cm
12 3.7cm x 1.9cm
======= =====================
Table 2 shows the relationship between a geohash and the resulting latitude and
longitude decoded from the different length geohashes. As characters are
removed from the original geohash '9q4gu1y4z' the bounding rectangle and the
accuracy of the decoded geohash becomes less precise. The decoded geohash
corresponds to the centroid of the bounding rectangle.
.. table:: **Table 2.** Geohash length vs Accuracy
========== =========================== =============================================
Geohash Tile Center lat, long Tile minlat, minlong, maxlat, maxLong
========== =========================== =============================================
9 22.5, -112.5 0, -135, 45, -90
9q 36.5625, -118.125 33.75, -123.75, 39.375, -112.5
9q4 34.45312, -120.23437 33.75, -120.9375, 35.15625, -119.53125
9q4g 34.36523, -119.70703 34.27734, -119.88281, 34.45312, -119.53125
9q4gu 34.43115, -119.68505 34.40917, -119.70703, 34.45312, -119.66308
9q4gu1 34.41741, -119.70153 34.41467, -119.70703, 34.42016, -119.69604
9q4gu1y 34.41947, -119.69810 34.41879, -119.69879, 34.42016, -119.69741
9q4gu1y4 34.41922, -119.69861 34.41913, -119.69879, 34.41930, -119.69844
9q4gu1y4z 34.41928, -119.69846 34.41926, -119.69849, 34.41930, -119.69844
========== =========================== =============================================
Geohashes comprise a nested spatial indexing system with each level of
geohashes tile containing 32 tiles of the next smaller tile size. The level one
geohashes (length=1) divide the earth into 32 tiles. Each of these 32 tiles is
then subdivided into 32 level 2 tiles and so on.
Geohashes also have the property that all smaller tiles within the enclosing
geohash tile begin with the same leading characters, therefor for the level 1
tile '9', all level 2 sub-tiles begin with '9': '90', '91', '93',..., '9z'.
For example the level 3 geohash tile that encloses much of Santa Barbara County
is '9q4'. Also contained in this bounding rectangle is the city center of Santa
Maria (geohash 9q4qg7j2hmdz), Goleta (geohash 9q4gckb5jxu7) and Santa Barbara
(geohash 9q4gu4n7y5b7) all of which begin with the characters '9q4' and fall
within the '9q4' geohash rectangle. This property is very useful for searching
and sorting datastores that contain geohashes.
DataONE Search Index and Geohashes
----------------------------------
The DataONE search index contains geohashes that have been computed for each
geographic coverage associated with a PID containing geographic coverage
information, which currently includes metadata objects in EML and FGDC formats.
The search index is described here: `<SearchMetadata.html>`_. Each PID in the
search index has a geohash computed at nine different resolutions,
corresponding to the geohash lengths shown *Table 3*. The field names are
appended with the geohash length, so for example the field *geohash_1* has a
string length of one and corresponds to the largest tile size in *Table 1*.
Geohashes are added to the search index at different lengths to allow for
searching and plotting at different resolutions.
For EML documents, the geohashes are computed by determining the centroid of
the XML elements *northBoundingCoordinate, southBoundingCoordinatem,
eastBoundingCoordinate, westBoundingCoordinate* which are child element of
*//dataset/coverage/geographicCoverage/boundingCoordinates*. Because any number
of coverages may be defined with the EML format, the geohashes for these
coverages are stored in a Solr multi-valued field. EML allows for the four
bounding coordinates to specify a single coordinate (i.e.
westBoudingCoordinate=eastBoundingCoordinate and
northBoundingCoordinate=southBoundingCoordinate), in which case this location
is used to compute a geohash.
For FGDC documents, the XML elements *northBoundingCoordinate,
southBoundingCoordinate, eastBoundingCoordinate, westBoundingCoordinate*
(parent element //metadata/idinfo/spdom/bounding) are used to compute the
geohash using the same method as for EML.
Using Geohashes for plotting
----------------------------
Geohashes can be used to efficiently plot the location of the geographic
coverages. The following examples show different search and plotting strategies
that are possible using geohashes. Several public domain Javascript libraries
are available for assisting in developing web clients that could use geohashes.
For example, the Javascript library *node-geohash* (available at
https://github.com/sunng87/node-geohash) contains routines to encode and decode
geohashs in addition to other spatial operators using geohashes. This library
will be used for the examples that follow.
**Example: Retrieve geohashes as facets in Solr search**
In this example the Solr search index is queried for a particular field of
interest, with the associated geohash counts being returned as a field facet.
Used in this way, the facet field of geohashes becomes a spatial bin, with the
size of the geographic area and the spatial resolution of the binning selected
by the geohash level.
For example, if we are interested in plotting the location of PIDs that have
some associated with kelp, we could query the search index with the Solr query:
..
https://cn.dataone.org/cn/v1/query/solr?q=kelp&facet=true&facet.field=geohash_5&facet.mincount=1&rows=0
The portion of the response that we are interested in are the facet counts:
::
<lst name="facet_counts">
<lst name="facet_queries"/>
<lst name="facet_fields">
<lst name="geohash_5">
<int name="9q4qx">5</int>
<int name="9q4ce">4</int>
<int name="9q4cf">4</int>
<int name="9q4ey">4</int>
<int name="9q4ge">4</int>
<int name="9q4gx">4</int>
<int name="9q4kj">4</int>
<int name="9q4s4">4</int>
<int name="9q4ez">3</int>
<int name="9q4g8">3</int>
<int name="9q4gb">1</int>
</lst>
</lst>
<lst name="facet_dates"/>
<lst name="facet_ranges"/>
</lst>
To display these search results each geohash can be decoded to obtain the
latitude, longitude of the geohash. For example, we can obtain the coordinates
of the first geohash returned from the search as shown in the following code
fragment:
::
// Use the node-geohash Javascript library
var geohashLib= require('ngeohash');
// Return [minlat, minlon, maxlat, maxlon] of geohash tile
var coords = geohashLib.decode("9q4qx");
The variable *coords* now contains the latitude, longitude (coords.latitude,
coords.logitude) of the decoded geohash, which is center point of the geohash
tile, in this case for level 5 geohash tiles. We could then place a marker with
counts at these coordinates to indicate how many hits occured in this geohash
tile.
Care must be taken in selecting the right geohash tile level for the Solr
query, with the consideration of smaller geohash tiles providing more accurate
spatial results, but returning a greater number of facet results as each
greater resolution tile covers a smaller geographic area.
Using Geohashes for searching
-----------------------------
Geohashes in the search index are multi-valued, so that geohashes have been
computed for each geographic coverage for a PID. Since the geohashes are
indexed at different resolutions, you can search all coverages at different
spatial resolutions.
**Example: Search using a bounding box**
One appraach to using geohashes for search is to retrieve all PIDs with
geohashes that overlap a search box. First determine which geohashes overlap a
bounding rectangle, in this case the bounding rectangle that encompasses Santa
Cruz Island in the Santa Barbara Channel:
::
// Use the node-geohash Javascript library
var geohashLib= require('ngeohash');
// Search for all geohashes within a geographic bounding box
// which might be the current browser viewport or alternatively a
// region of interest
// Santa Cruz Island bounding coordinates (approximate)
// lower left
minlat = 33.959878;
minlon = -119.914398;
// upper right
maxlat = 34.075341;
maxlon = -119.520264;
// Find all geohashes that overlap the specified bounding box.
var geohashes = geohashLib.bboxes (minlat, minlon, maxlat, maxlon, precision=4);
The geohashes that overlap the search bounding box are returned. These
geohashes can then be used to find PIDs that have a coverage that is within
these geohash tiles:
::
https://cn.dataone.org/cn/v1/query/solr?q=*:*&q.op=OR&fq=geohash_4:(9q4c 9q49 9q51)&fl=id
This Solr filter query will find all entries for which one of the level 4
geohashes matches any of the specified geohashes. Because the geohash_* fields
are indexed as Solr multivalued fields, all coverages for a PID are compared to
see if they match.
Geohash algorithm
-----------------
A description of the geohash algorith is outside the scope of this document,
but an excellent description of the can be found at
http://en.wikipedia.org/wiki/Geohash.
One caveat of the geohash algorith that may be of interest to end users
however, is that because of the tile ordering ("Z" ordering) where tile
geohashes are incremented in a "Z" pattern and not strictly by row, column, it
is not gauranteed that adjancent tiles have similar geohashes, for example, the
level 1 geohashes at the equator, starting from the International Date Line,
are named "8", "9", "d", "e", "s", "t" and so on.