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