큰 (메모리에 맞지 않는) 그래프를 효율적으로 조작하는 방법

Question

수백만 개의 노드와 가장자리가있는 대형 그래프 G를 유지해야합니다. 잠재적으로 메모리에 맞지 않을 수 있습니다.

I이 그래프에서 수행해야하는 일부 빈번한 작업 포함

1. 각 노드/에지 등의 접근 횟수, 체중 등의 연관된 사용자 정의 속성을 가질 것

2. 각 노드 (정점)에 대해 속성 값을 기반으로 효율적인 쿼리를 수행해야합니다. 예를 들어, X 값이 v1보다 크지 만 v2보다 작은 노드를 찾으십시오. 아마도 특정 필드에 대한 색인을 작성해야합니다.

3. 주어진 노드의 들어오는 가장자리와 나가는 가장자리를 모두 찾고 가장자리의 가중치를 업데이트해야합니다.

4. 특정 노드에서 로컬 (DFS 기반) 순회를 수행하고 특정 사용자 정의 조건자를 만족하는 모든 경로를 반환해야합니다 (이 조건자는 경로에서 노드/에지의 속성 값을 사용할 수 있음).

5. 노드/에지를 효율적으로 추가/삭제해야합니다. 이것은 작업 1, 2, 3과 같이 자주 수행되지는 않습니다.

는 잠재적으로 다른 부분보다 훨씬 더 자주 액세스됩니다 그래프의 일부 핫스팟이 있고, 나는 메모리에이 핫스팟을 캐시하고 싶습니다.

최소 구현 노력으로이를 달성하는 효율적인 방법은 무엇입니까?

저는 Neo4j/InfiniteGraph/DEX와 같은 디스크 기반 그래프 데이터베이스를보고 있습니다. 위의 모든 작업을 지원하지만 일관성/동시 제어 또는 클러스터 기반 복제와 같은 많은 기능을 필요로하지 않으므로 과도한 것 같습니다. 또한 이들 중 상당수는 Java를 기반으로하며 C/C++ 인터페이스로 무언가를 선호합니다.

기본적으로 노드와 로컬 순회에 대한 지속성, 쿼리를 효율적으로 처리하는 디스크 그래프 라이브러리가 필요합니다. 내가 사용할 수있는 기존 (오픈 소스) 프로젝트에 대한 권장 사항이 있습니까? 그렇지 않다면 그런 것을 구현하는 가장 좋은 방법은 무엇입니까?

Answer 1

"C/C++ 인터페이스가있는 것을 선호"하므로 GraphChi을 사용해 볼 수 있습니다.

"GraphChi는 디스크 (SSD 또는 하드 드라이브)에서 그래프를 처리하기위한 새로운 알고리즘을 사용하여 단일 시스템에서만 매우 큰 그래프 계산을 실행할 수 있습니다."

C++ 용 GraphChi의 소스 코드와 문서는 Google Code project pages에 있습니다.

Example Apps에는 PageRank, 커뮤니티 검색 및 연결된 구성 요소와 같은 알고리즘이 포함됩니다. 필요에 맞게 수정할 수 있습니다.

Answer 2

또 다른 옵션은 e4Graph 일 수 있습니다. 이는 간단한 C++ 그래프 지속성 라이브러리입니다. 나는 그것을 시도하지 않았지만 유망 해 보인다.

Answer 3

수백만 개의 노드로 수백만 개의 큰 그래프를 보았습니다.내가 권장하는 것은 당신이 포인트를 찾는다는 것이다. 당신은 가중 압축을해야한다. 따라서 N 개의 노드를 가져 와서 평균 및 가중치를 사용하여 N/M 노드로 압축 한 다음 그래프를 다시 작성하십시오.

당신이 선택한 많은 노드마다 재 압축을합니다. 그 이유는 모든 것이 거대 해짐에 따라 어떤면에서는 시간이 지남에 따라 정상화 될 수 있다는 것입니다.

당신은 유향 그래프를 가지고 있습니다. 큰 노드를 더 크게 통과 할 때 A> B> (E & D)> H이면 다음과 같이 말할 수 있습니다. A> H.

노드 간의 가장 짧은 점프를 기준으로 노드 간의 공통 경로를 결정할 수 있습니다. 압축 된 목록에 있지 않다면 특정 영역을 향하여 적어도 향할 것입니다. 어떤면에서는 감압됩니다.

Answer 4

C++ 솔루션을 찾으려면 GraphLab이 좋습니다. 그러나 분산 컴퓨팅 솔루션입니다. 수백만 개의 노드/에지를 다루므로 그것은 좋은 적합일지도 모른다. 이 문서에서는 다른 그래프 라이브러리를 나열 당신이 필요로하지 않는 일부 옵션이 포함 된 도구를 사용하여 뭐가 잘못

http://www.ibm.com/developerworks/library/os-giraph/