Redis: implementar gráfico dirigido ponderado

Question

¿Cuál es la mejor manera de implementar gráficos ponderados con Redis?

mayoría Vamos a buscar caminos más cortos sobre el gráfico (probablemente utilizando el algoritmo de Dijkstra)

Actualmente hemos considerado la adición de los bordes para ReDiS

Para cada nodo, que tendrán la NODEID como la clave y un conjunto ordenado de claves de los nodos referenciados el puntaje de cada ID de nodo en el conjunto ordenado es el peso del borde.

¿Qué opinas? corrígeme si estoy equivocado, pero el único malo aquí es que para cada consulta para el siguiente nodo en una SortedSet prestamos O (log n) en lugar de O (1) ...

http://redis.io/commands/zrange

Answer 1

Conseguir la siguiente el elemento en un conjunto ordenado es solo O (log (n)) si los está sacando de uno en uno, en cuyo caso la latencia de la conexión a redis será más un problema que la complejidad de la operación.

Para la mayoría de las operaciones en un gráfico, debe observar todos los bordes de un nodo, por lo que tiene sentido cargar todo el conjunto (o al menos aquellos con puntaje adecuado) en la memoria local cuando procesa el nodo. Esto, por supuesto, significará cargar algunos bordes que no se seguirán porque ya ha encontrado una ruta adecuada, pero dado que los conjuntos son bastante pequeños, el costo de esto será mucho menor que realizar una nueva llamada a redes para cada ventaja que haga necesitar.

Answer 2

Perdón por llegar tarde :), pero recientemente me encontré con el mismo problema, y ​​lo modelé usando hash. Estoy de acuerdo con Tom Clarkson que (casi) todo debe ser cargado en la memoria local y aumentan diciendo que una manera eficiente en términos de espacio es el uso de hashes, y almacenar su información gráfica como esta:

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

Si necesita más espacio y eficiencia, comprime cada valor (que puede ser una cadena JSON ...) y descomprime/importa/deserializa en tu código de cliente.