Redis: Implementacja ważonego wykresu ukierunkowanego

Question

Jaki jest najlepszy sposób wdrożenia ważonego wykresu za pomocą narzędzia Redis?

Będziemy głównie szukać najkrótszych ścieżek na wykresie (prawdopodobnie przy użyciu algorytmu Dijkstry)

Obecnie uważany dodanie krawędzi do Redis

Dla każdego węzła, będziemy mieć nodeid jako klucz i sortowany zestaw kluczy odniesionych węzłów wynik każdego nodeId w sortedSet jest wagą krawędzi.

Co myślisz? Popraw mnie jeśli się mylę, ale tylko porażka jest to, że dla każdego zapytania do następnego węzła w sortedset płacimy O (logn) zamiast O (1) ...

http://redis.io/commands/zrange

Answer 1

Pierwsze następny pozycja w posortowanym zbiorze to tylko O ​​(log (n)), jeśli wysyłasz je pojedynczo, w którym to przypadku opóźnienie połączenia z redis będzie większym problemem niż złożoność operacji.

Dla większości operacji na wykresie należy spojrzeć na wszystkie krawędzie z węzła, więc sensowne jest załadowanie całego zestawu (lub przynajmniej tych z odpowiednim wynikiem) do pamięci lokalnej podczas przetwarzania węzła. Będzie to oczywiście oznaczało ładowanie niektórych krawędzi, których nie będzie można śledzić, ponieważ już znalazłeś odpowiednią ścieżkę, ale ponieważ zestawy są dość małe, koszt tego będzie znacznie mniejszy niż wykonanie nowego połączenia z Redis dla każdej krawędzi, którą wykonujesz. potrzeba.

Answer 2

Przepraszam za spóźnienie :), ale ostatnio natknąłem się na ten sam problem i zamodelowałem go za pomocą skrótów. Zgadzam się z Tom Clarkson, że (prawie) wszystko powinno być ładowane do pamięci lokalnej i powiększać, mówiąc, że to skuteczny sposób pod względem powierzchni jest stosowanie skrótów i przechowywać swoje dane wykresu takiego:

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

If potrzebujesz więcej przestrzeni i wydajności, kompresuj każdą wartość (która może być ciągiem JSON ...) i rozpakuj/importuj/deserializuj w swoim kodzie klienta.