Redis: Implement Weighted Graphics

Question

What is the best way to implement a weighted schedule using Redis?

Basically we will look for the shortest paths on the schedule (possibly using Dijkstra's algorithm)

We are currently considering adding edges to Redis.

For each node, we will have nodeId as the key and a sorted set of keys for the referenced nodes. The evaluation of each nodeId in sortedSet is the weight of the edge.

What do you think? Correct me if I am wrong, but the only flaw here is that for each request for the next node in the sorted set we pay O (logn) instead of O (1) ...

http://redis.io/commands/zrange

Answer 1

Getting the next element in a sorted set is only O (log (n)) if you get them one at a time, in which case the latency of connecting to redis will be more of a problem than the complexity of the operation.

For most operations on the chart, you need to look at all the edges from the node, so it makes sense to load the entire set (or at least a suitable score) into local memory when processing the node. Of course, this means loading some edges that will not be followed because you have already found a suitable path, but since the sets are quite small, the cost of this will be much less than creating a new call to repeat for each edge that you make.

Answer 2

Sorry for being late :), but I recently ran into 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 will add that an efficient way from a space point of view is to use hashes and store your graph information as follows:

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 each value (which may be a JSON string ...) and unpack / import / deserialize your client code.