Nearest neighbour search with Redis

Redis has a very nice geo API but it doesn’t support nearest neighbour queries. Given a point x, the answer to a nearest neighbour query is the closest point to x.

However, you’ll be able to answer nearest neighbour queries with the following Lua script. It does an exponential search over the distance parameter for GEORADIUS to find the nearest neighbour of a given point.

local dist = 100 -- Initial distance in m
local latitude = ARGV[1]
local longitude = ARGV[2]
local maxDist = tonumber(ARGV[3]) -- Max search distance in m, to avoid infinite loop on keys with no data

if not redis.call('EXISTS', KEYS[1]) then
return nil
end

local res = redis.call('GEORADIUS', KEYS[1], longitude, latitude, dist, 'm', 'count', '1', 'asc')
while #res == 0 and dist <= maxDist do
dist = 2 * dist
res = redis.call('GEORADIUS', KEYS[1], longitude, latitude, dist, 'm', 'count', '1', 'asc')
end

if #res > 0 then
return res[1]
else
return nil
end


Note that the time complexity is $O(\log M \cdot \log D)$, where $M$ is the number of elements in the geo index and $D$ is the distance to the nearest neighbour (assuming that the number of elements within distance $D$ is constant).

To invoke the script, you need to pass the key to your geo index and three arguments: latitude, longitude, and a maximum search distance. The latter is necessary to avoid infinite loops if a key doesn’t contain any data.

If you want to use it from the shell then save the script as nn.lua and load the script:

$redis-cli SCRIPT LOAD "$(cat nn.lua)"
"90702b22ecf3e3118ac4c3ffbd40f94c2d8a92bc"


The output is the SHA1 of your script. The script is now stored on your Redis instance. You only have to load it once. Now you can invoke it by issuing:

\$ redis-cli EVALSHA 90702b22ecf3e3118ac4c3ffbd40f94c2d8a92bc 1 <key> <latitude> <longitude> <max_dist>


I needed to make nearest neighbour queries from an application so I wrapped the Lua script in Scala code using Jedis for connecting to Redis. Here’s a slightly simplified version of my code.

class NearestNeighbourSearcher(redisClient: Jedis) {
// Get the SHA1 of the script. Assumes that it is stored in /src/main/resources/nn.lua of your project
private val script = Source.fromInputStream(getClass.getClassLoader.getResourceAsStream("nn.lua")).getLines.mkString("\n")
private val scriptSha: String = stringToSHA1(script)

// Load the script if it doesn't exist on the host
if (!redisClient.scriptExists(scriptSha)) redisClient.scriptLoad(script)

def getNearestNeighbour(key: String, lat: Double, long: Double, maxSearchDistance: Int): Option[String] = {
val res = redisClient.evalsha(scriptSha, 1, key, lat.toString, long.toString, maxSearchDistance.toString)
if (res != null)
Some(res.asInstanceOf[String])
else
None
}

def stringToSHA1(s: String): String = {
val md = MessageDigest.getInstance("SHA-1")
md.digest(s.getBytes("UTF-8")).map("%02x".format(_)).mkString
}
}


This post first appeared May 19, 2019 on Medium.

I have been using redis for quite some time. Never did I play around with the geo API.

This is a really nice post. Useful to anyone using redis regardless of the stack they use with it.