Redis: Implement Weighted Directed Graph

Question

What's the best way to implement weighted graph using Redis?

We will mostly search for shortest paths over the graph (probably using the Dijkstra algorithm)

Currently we considered adding the edges to Redis

For each node, we will have the nodeId as the key and a sortedset of keys of referenced nodes the score of each nodeId in the sortedSet is the weight of the edge.

What do you think? Correct me if I am wrong but the only bummer here is that for each query for the next node in a sortedset we pay O(logn) instead of O(1)...

http://redis.io/commands/zrange

Answer 1

Getting the next item in a sorted set is only O(log(n)) if you are getting them out one at a time, in which case the latency of the connection to redis will be more of an issue than the complexity of the operation.

For most operations on a graph you need to look at all the edges from a node, so it makes sense to load the whole set (or at least those with a suitable score) into local memory when you process the node. This will of course mean loading some edges that will not be followed because you have already found a suitable path, but since the sets are fairly small the cost of this will be far less than making a new call to redis for every edge that you do need.

Answer 2

Sorry for being late :), but I recently came across the same problem, and I modeled it using hashes. I agree with Tom Clarkson that (almost) everything should be loaded into local memory and I augment by saying that an efficient way in terms of space is to use hashes, and store your graph information like this:

Graph = { node1 : { nodeX : edge_weight, nodeY : edge_weight, other_info: bla..},
          node2 : { nodeZ : edge_weight, nodeE : edge_weight, other_info: bla..},
          bla bla...
        }

If you need more space and efficiency, compress every value ( which can be a JSON string...) and decompress/import/deserialize in your client code.