Redis：实现加权有向图 [英] Redis: Implement Weighted Directed Graph

问题描述

使用Redis实现加权图的最佳方法是什么？ 我们将主要搜索图中的最短路径（可能使用Dijkstra算法）

目前我们考虑将边缘添加到Redis中

对于每个节点，我们将有nodeId作为引用节点的键和一组排序键
sortedSet中每个nodeId的分数就是边的权重。

你认为什么？纠正我，如果我错了，但唯一令人失望的是，对于排序集中的下一个节点的每个查询，我们支付O（logn）而不是O（1）...

http://redis.io/commands/zrange

解决方案

如果您一次只有一个，那么获取排序集中的下一个项目只有O（log（n）），在这种情况下，连接到redis的延迟将会比操作的复杂性更重要。

对于图上的大多数操作，您需要查看节点中的所有边，因此它是有意义的在处理节点时将整个集合（或至少具有合适分数的集合）加载到本地内存中。这当然意味着加载一些不会被遵循的边缘，因为你已经找到了合适的路径，但是因为这些集合相当小，所以它的成本将远远低于你为每一个边缘对redis进行新的调用需要。

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

解决方案

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.

这篇关于Redis：实现加权有向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！