GeoLocation Indexing

By

I worked before with the open street maps API, and display maps in applications. A few times I had the thought of making a game, on the map, similar to ingress or other GPS map games, where the player will walk around. I thought about Zombies, as people playing the game would for others look like the “mobile zombies” walking slowly in uneven paths. Or to have some dealership, maybe drugs. and the dealer will control some area.

A problem I always had was how to effectively index the GEO data, the two dimensional coordinates for longitude and latitude. I saw that mongoDB or postgresDB have some feature for that, but the usage in both systems is more then strange.

So recently I was reading at the redis db documentation and saw that it now also has support for geo data. The API in redis looked pretty much straight forward. The description pointed to a wikipedia article geohash. by reading it, I found, I could implement that myself with a small JS function.

1
2
3
4
5
6
7
8
9
10
11
12
function tGeoHash(lon, lat) {
    // take binary string
    var los = parseInt(lon * 100000).toString(2).padStart(32, '0')
    var las = parseInt(lat * 100000).toString(2).padStart(32, '0')
    // merging one bit from each string;
    var join = '';
    for (var i = 0; i < 26; i++) {
        join += los[i] + las[i];
    }
    // printing the hash
    return parseInt(join, 2).toString(16).padStart(14, '0')
}

After a few minutes I found, the implementation takes to much time and redis has the feature to search in a way, where you can provide a position and a distance to get the items in a particular area. I liked those features, so I was searching on NPM. For some solution. There is not much about this topic.

But what I found was satisfying: ngeohash. It is able to produce integer and string hash. I found the implementation works internally directly on number without creating a binary-string. I liked that. Just the feature to find by range.

Redis is able to accept the distance in meter miles or kilo meters. But the library only works with “error” in the form of degrees. Searching within the redis github repo for their GEORADIUS method, I very quickly found the method geohashEstimateStepsByRadius.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const double MERCATOR_MAX = 20037726.37;
const double MERCATOR_MIN = -20037726.37;

/* This function is used in order to estimate the step (bits precision)
 * of the 9 search area boxes during radius queries. */
uint8_t geohashEstimateStepsByRadius(double range_meters, double lat) {
    if (range_meters == 0) return 26;
    int step = 1;
    while (range_meters < MERCATOR_MAX) {
        range_meters *= 2;
        step++;
    }
    step -= 2; /* Make sure range is included in most of the base cases. */

    /* Wider range towards the poles... Note: it is possible to do better
     * than this approximation by computing the distance between meridians
     * at this latitude, but this does the trick for now. */
    if (lat > 66 || lat < -66) {
        step--;
        if (lat > 80 || lat < -80) step--;
    }

    /* Frame to valid range. */
    if (step < 1) step = 1;
    if (step > 26) step = 26;
    return step;
}

The precision is determined by a number of bits, that need to be same for the elements that will be found together. This can help to create the hash, that can be stored in db. It can be indexed and queried very easy.

Now when using the string hash, for indexing, it is very easy to query. As all keys get prefixed in the same way. simple query “asa*” or “1354?” depending on your database. The problem with this, is, that a string need more memory than an integer what can sum up to huge numbers very quick. and the precision described by the distance is less precise, as you only can have full characters as the prefix. so the distance would be like 1km, 8km,64km.

If we are able to store and query integer the memory, as well as the query precision would be much better. For integers you can not do the wildcard, but you can query a range. Like in a binary uint8 hash, where we want to search with precision of 4 bits: 1010 0000 - 1010 1111.

After having these things thought trough these ideas, feels very empowering. I think in future I will have some more fun, playing around with GEO data.

Contents