How to use Redis and geo proximity search to find two users at the same location?

Question

I want to implement a service that, given users' geo coordinates, can detect whether two users are at the very same location in real time.

In order to do this in real time and to scale, it seems I should go with a distributed in-memory datastore like Redis. I have researched using geohashing, but the problem is that points close to each other may not always share the same hash prefix. And geohashing may be overkill since I'm interested in finding whether two users are close enough where they are standing next to each other.

The simple solution of course is just to test whether pairs of geo coordinates fall within a small distance of each other. But AFAIK, Redis and other in-memory datastorse don't have geospatial indexing to support that kind of look-up.

What is the best way to go about implementing this?

Answer 1

This functionality is baked into Redis 3.2+.

But for older versions the problem still exists. I've taken Yin Qiwen's answer and created a module for Node, and you can see how it uses Redis by examining the code. His instructions are perfect and I was able to follow them for great results. https://github.com/arjunmehta/node-georedis

The same algorithm is essentially what is used for the native commands.

It is very fast, and avoids any kind of intersections/haversine type operations. The coolest thing (I think) about Yin Qiwen's method is that the most computationally intense parts of the algorithm can be distributed to clients (instead of all happening in the DB or on the server).

It's not 100% precise and uses preconfigured distance steps, but for most applications you won't need exact precision I'd imagine.

I've also paraphrased Yin Qiwen's article at the GIS stack exchange.

Sorry for all the linkage. :P

Answer 2

Generally, this could be done by GeoHash and Redis's sorted set. There is a design I wrote before talking about how to implement a spatial index service on redis.

https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Answer 3

Maybe you can try this one:

Redis Geography Edition

You really want to try it, it works awesome. :)

Answer 4

I realize this doesn't answer your question... but I don't think that it's the correct tool.

PostgreSQL + PostGIS can perform really, really well. You can configure PostgreSQL to pretty much run as much of the database as it can fit in memory.

PostGIS uses (I think) rtree indexes, so it's incredibly fast to perform the kind of lookup you are interested in.

Using a backend that fires off websocket requests would allow you to perform pretty much real-time. Anytime your backend receives a persons GPS coordinates; perform the spatial lookup; and notify applicable clients through websockets.

Answer 5

The Redis geography edition mentioned by other answers in this thread has been integrated into Redis since version 3.2 (also see this earlier comment).

You can find the new commands here (in beta for now) :

• GEOADD
• GEODIST
• GEOHASH
• GEOPOS
• GEORADIUS
• GEORADIUSBYMEMBER

Answer 6

Tarantool database keeps data in memory, pushes them to disk as transaction logs, has RTree-type spatial index (not only 2-dimensional) and a number of nice operations on such index (containment, overlapping, distance).

I use it in a commercial project for storing and querying records which describe objects in 3D space.

http://tarantool.org/doc/book/box/box_index.html

https://github.com/tarantool/tarantool/wiki/R-tree-index-quick-start-and-usage

Standard client and examples are in Lua, but there are couple of other clients developed by the database authors. I use Java client in an Scala application with success.

The database is also very fast - here's scientific comparison with other databases (putting aside an aspect of being a spatial db): http://airccse.org/journal/ijdms/papers/6314ijdms01.pdf

Answer 7

I would like to share a sample Java code for Redis Geography edition.

public void geoadd(String objectId, BigDecimal latitude, BigDecimal longitude) {
    log.info("geoadd(): {} {} {}", objectId, latitude, longitude);
    try (Jedis jedis = jedisPool.getResource()) {
        if (geoaddSha == null) {
            String script = "return redis.call('geoadd','" + GEOSET + "', ARGV[1], ARGV[2], KEYS[1])";
            geoaddSha = jedis.scriptLoad(script);
        }
        log.info("geoaddSha: {}", geoaddSha);
        log.info(jedis.evalsha(geoaddSha, 1, objectId, latitude.toString(), longitude.toString()).toString());
    }
}

@SuppressWarnings("unchecked")
public List<String> georadius(BigDecimal latitude, BigDecimal longitude, int radius, Unit unit) {
    log.info("georadius(): {} {} {} {}", latitude, longitude, radius, unit);
    try (Jedis jedis = jedisPool.getResource()) {
        if (georadiusSha == null) {
            String script = "return redis.call('georadius','" + GEOSET + "', ARGV[1], ARGV[2], ARGV[3], ARGV[4])";
            georadiusSha = jedis.scriptLoad(script);
        }
        log.info("georadiusSha: {}", georadiusSha);
        List<String> objectIdList = (List<String>) jedis.evalsha(georadiusSha, 0, latitude.toString(), longitude.toString(), String.valueOf(radius), unit.toString());
        log.info("objectIdList: {}", objectIdList);
        return objectIdList;
    }
}

public void remove(String objectId) {
    log.info("remove(): {}", objectId);
    try (Jedis jedis = jedisPool.getResource()) {
        jedis.zrem(GEOSET, objectId);
    }
}