C와 C 사이의 최단 경로를 얻기위한 Cypher 쿼리는 C를 통과하지 못합니다. 또는 Cypher/Neo4j에 대한 대안을 추천하십시오.

Question

나는 수천 개의 노드가있는 그래프로 작업하고 있습니다. 사람 노드가 있고 그 사이에 친구 관계가 있다고 가정 해보십시오. 예를 들어, 거스 - : 나는만큼 그들은 이상 20 RELS로 구분하지 않는 행크와 거스 사이의 최단 친구의 경로를 찾을 싶었다면

-skylar [친구], 나는이 작업을 수행 할 수 있습니다 :

START hank=node(68), gus=node(66) 
MATCH p = shortestPath((hank)-[:FRIENDS*..20]-(gus)) 
RETURN p 

발견 된 최단 경로 길이가 10 이상인 경우에도 작동하며 빠르다.

하지만 행크에서 거스로가는 길을 찾고 싶다고 말하면 은 글렌을 통과합니까?

내가 시도한 쿼리

은 이것이다 :

START hank=node(68), gus=node(66), glenn=node(59) 
MATCH p =(hank)-[:FRIENDS*..20]-(gus) 
WHERE NOT glenn IN nodes(p) 
RETURN p 
ORDER BY length(p) 
LIMIT 1; 

이 매우 작은 그래프 (30여 명)에 작동하지만 1000 년대가있는 경우 ... JVM이 heapspace에서 실행됩니다.

그래서 Cypher가 ALL 길이가 20 이하인 행크스 사이의 경로를 찾은 다음 WHERE 필터를 적용한다고 생각하십니까? 왜 그렇게 느린 지 분명합니다.

추상적 인 의미에서이 알고리즘은 동일한 큰 O 런타임으로 수행 할 수 있어야합니다. 변경되는 것은 각 노드 (검색 할 때)가 피하려는 노드가 아닌지 확인하기 때문입니다.

이 작업을 수행하는 방법에 대한 어떤 제안? 나는 Cypher에게 아주 익숙하다. 이 사이퍼와 함께 할 수없는 경우

, 당신은 다른 데이터베이스와 그래프 언어 "스택"을 추천 할 수 있습니까?

감사

Answer 1

다음 쿼리의 성능을 테스트 할 수 있습니까? 주요 차이점은 노드 대신 경로를 비교한다는 점입니다. 경로에 방향을 추가 했으므로 쿼리 속도가 빨라집니다.

START hank=node(68), gus=node(66), glenn=node(59) 
MATCH p = allshortestPaths((hank)-[:FRIENDS]->(gus)) 
WITH COLLECT(p) AS gusPaths, hank, glenn 
MATCH p2 = allshortestPaths((hank)-[:FRIENDS]->(glenn)) 
WITH COLLECT(p2) AS glennPaths, gusPaths 
WITH filter(x IN gusPaths 
      WHERE NONE (x2 IN glennPaths 
         WHERE x = x2)) AS filtered 
RETURN filtered 
ORDER BY length(filtered) 
LIMIT 1