geohasher

Showing:

8

9

8yrs ago

1

0

MIT

No

SUMMARY

This is a basic demonstration of how the GeoHash algorithm can be used to generate bounding box searches without the use of specialized spatial indexing approaches.

This can be especially helpful in cases where spatial indexes are either not supported or do not scale to high volumes. Environments such as Google App Engine, EC2, and SQLite provide reasonable string indexing services but do not support spatial indexing. This algorithm could be used to provide proximity searching in these environments.

BACKGROUND

The Geohash algorithm was first described by Gustavo Niemeyer in February 2008. By interleaving latitude and longitude information in a bitwise fashion, a composite value is generated that provides a high resolution geographic point, and is well suited for storage or transmission as a character string.

Geohash also has the property that as the number of digits decreases (from the right), accuracy degrades. This property can be used to do bounding box searches, as points near to one another will share similar Geohash prefixes.

However, because a given point may appear at the edge of a given Geohash bounding box, it is necessary to generate a list of Geohash values in order to perform a true proximity search around a point. Because the Geohash algorithm uses a base-32 numbering system, it is possible to derive the Geohash values surrounding any other given Geohash value using a simple lookup table.

So, for example, 1600 Pennsylvania Avenue, Washington DC resolves to:

``````38.897, -77.036
``````

Using the geohash algorithm, this latitude and longitude is converted to:

``````dqcjr0bp7n74
``````

A simple bounding box around this point could be described by truncating this geohash to:

``````dqcjqc
``````

However, 'dqcjr0bp7n74' is not centered inside 'dqcjqc', and searching within 'dqcjqc' may miss some desired targets.

So instead, we can use the mathematical properties of the Geohash to quickly calculate the neighbors of 'dqcjqc'; we find that they are:

``````'dqcjqf','dqcjqb','dqcjr1','dqcjq9','dqcjqd','dqcjr4','dqcjr0','dqcjq8'
``````

This gives us a bounding box around 'dqcjr0bp7n74' roughly 2km x 1.5km and allows for a database search on just 9 keys:

``````SELECT * FROM table WHERE LEFT(geohash,6) IN ('dqcjqc', 'dqcjqf','dqcjqb','dqcjr1','dqcjq9','dqcjqd','dqcjr4','dqcjr0','dqcjq8');
``````

GeoHash on Wikipedia

USE AS COMMONJS MODULE

To use this in a CommonJS capable system use the following code snippet to generate GeoHashes:

``````var GeoHasher = require("geohasher");
var hash = GeoHasher.encode(38.897, -77.036);
// dqcjr0bp7n74
``````

Or in Browser:

``````<script type="text/javascript" src="http://domain/path/to/lib/geohasher.js"></script>
<script>
var hash = GeoHasher.encode(38.897, -77.036); // dqcjr0bp7n74
</script>
``````

Geohash Javascript Demonstration
(c) 2008 David Troy
(c) 2010 Chris Williams
(c) 2013 Jackson Tian

Refactored to CommonJS module by Chris Williams (c) 2010
Fix global vars by Jackson Tian (c) 2013

Rate & Review

Great Documentation0
Easy to Use0
Performant0
Highly Customizable0
Bleeding Edge0
Responsive Maintainers0
Poor Documentation0
Hard to Use0
Slow0
Buggy0
Abandoned0
Unwelcoming Community0
100
No reviews found
Be the first to rate

Alternatives

No alternatives found