geohashes and proximity: part I

A few days ago while I was working on a project, I reached what turned out to be a pretty difficult challenge. I thought I had a very simple problem:

Given a single (geo)coordinate x, and a large set of other (geo)coordinates A, how might one very efficiently query the set to return all coordinates within A that fall within a certain distance of x?

A Naive Approach

Initially, I thought this would be simple geometry. Just find all the coordinates that fall between a latitudinal range, and a longitudinal range. Something like:

function findNearbyNodes(radius, latitude, longitude){
  var latRange = radius/111111;
  var lonRange = radius/(111111 *  Math.abs(Math.cos(lat)));

  var latitudeMin = latitude - latRange;
  var latitudeMax = latitude + latRange;
  var longitudeMin = longitude - lonRange;
  var longitudeMax = longitude + lonRange;

  return database.getPointsBetween(latitudeMin, latitudeMax, longitudeMin, longitudeMax);
}

In fact this is an okay way of getting nearby points, particularly if a high degree of precision isn’t necessary, which suits my application. But, it’s not super efficient, because it would ultimately require an intersection operation to find all points within the latitudinal range AND the longitudinal range.

I was curious to know if there were better ways of doing this since for my project I was using Redis which lacks an efficient intersection function.

Enter the Geohash

A geohash is basically a number that represents a box of a certain size and its position amongst other boxes. The longer the geohash, the smaller the box and the more precisely it distinguishes regions of space. Using this technique, we can take a two-value coordinate (lat, lon) and reduce it down to a single value through a series of quadtree operations. I’ll get into what this means in more detail throughout the post but, practically, you can go from something like 43.646838, -79.403723 to something like dpz831evr0kf, which can be stored as a single (1-dimensional) value. When you need to, you can convert it back again to 43.646838, -79.403723. The coolest thing about geohashing is how it actually works!

How Geohashing Works

First imagine the entire world divided into two halves: left and right. If a point exists on the left half, it gets assigned a 0, if it’s on the right, it gets assigned a 1.

At the same time, imagine that the world is divided into top and bottom halves. If a point exists within the bottom half it gets a 0, and if in the top it gets a 1.

Because for most general purposes the surface of the earth is essentially two-dimensional, we can assume that this is a good framework for dividing up earth’s surface space, and so we can use this quandrant representation of space: top-left 01, top-right 11, bottom-right 10 and bottom left 00.

Now, we can repeat this process over and over again for each box!

Geohashing Gives Space an Address

It might not be totally obvious from the points outlined above, but here’s a definition for you: A geohash is just the address of a box calculated by subdividing a space following a standard set of rules a given number of times.

Every time we subdivide our boxes (into 4 new boxes), we just prepend the parent box’s “binary path”, to get a more and more precise representation of the subspaces.

So the more we iterate on dividing up the space, the more (relatively) accurately we can describe a single finite point using a box. All by using a sequence of 0s and 1s to map a path to any defined box in our space! If the sequence is longer it is more precise (smaller box) and if it is shorter, it remains less precise (bigger box).

*Geohash Resolution

In reality, we can’t actually keep dividing our space forever and ever. Each geohash value is actually limited to bit size of your number primitive that you are working with. A uint64 object in C would have 64-bits of information, whereas a uint32 would only have 32-bits. So, 32-bit, 52-bit (ie. javascript), and 64-bit systems each have their own inherent limits to precision.

But you might be able to suspect that, given that bit depths indicate the size of a box, that these boxes at various bit depths actually represent a physical space. And so we’ll see in part II of this exploration, how these inherent box-area relationships can be leveraged for proximity search.

Geohash Value Progression and Z-Curve

It’s not totally clear from the above that there exists a certain balance of predictability and unpredictability in the standard geohash algorithm. Geohashing follows a Z-Curve space filling algorithm, which means that as you subdivide your space, the indexes of the smaller boxes produced all increment from bottom-left to top-right (as opposed to a hilbert curve for example). In general, space filling curves tend to impose a level of unpredictability in the values of neighbouring boxes in isolation. That is, just by knowing the value of a box, there isn’t really an efficient way of deducing the values of neighbouring boxes, other than calculating them.

A natural byproduct of mapping multidimensional information to a single dimension is that the mapping is discontinuous. Generally the most efficient way to find the indexes of neighbouring boxes is by calculating them ground up.

Geohashing a 2-Dimensional Coordinate

So, what does this mean for us? Well, I thought it would be good to run through an example of how we could geohash a single geocoordinate. When working with geo-coordinates the ranges of values are between: latitude -90.0 and +90.0; and longitide -180.0 and +180.0.

Let’s choose an arbitrary point in our space. We can find a path to this point by recursively dividing the space and mapping our way to the point with a series of binary operations that determind whether the point falls above or below and left or right of the center of a particular subspace. The more times we can divide the space, the more accurately we can describe the location of the point withing our space using a binary sequence.

By walking through a simple range algorithm, we can see how we get a unique binary representation of the location of a particular point within a space. For the sake of finding proximal points, the reverse (decoding) or a geohash is not actually necessary, so I won’t get into that (but imagine the reverse process!).

In our example, at three levels deep, we have six 0s and 1s giving us a binary sequence of 011010. So we can say, in our example, given that we know we are 3 levels deep (6-bits), our point is within box 26. Now, imagine what could happen if we repeated our subdivision a bunch more times…

Conclusion to Part I

This post was really just to give some background on geohashing things, and how it all works. It’s more to help me understand how to communicate the process, and might act as a primer to understand how we can use them to find nearby points within a set.

To summarize, there are a few main things to note about geohashes.

1. A geohash is actually a numeric representation of a box.
2. The more “bit-depth” the geohash has, the smaller the box it represents, and the more accurately it can be used to represent a single point.
3. Hence, a geohash’s precision is limited to how many bits can be stored in the computer system’s numbers.

Resources

I’ve written a follow up post to actually describe the process of finding proximal points using geohashes!