Java로 공간 효율적인 그래프 표현?

Question

노드가 쌍으로 레이블이 지정되고 (현재이 경우 String [] 사용) 무차별 그래프가 필요하며 다른 노드에 임의로 링크 될 수 있습니다. 나는 Hashtable 타입으로 시작했다. 이 공간이 나에게 충분한 공간이 아닌 것으로 밝혀졌습니다. 약 6 만 개의 노드 (결국 그 수를 훨씬 웃도는)를 가질 생각입니다.

메모리 효율성이 향상되도록 그래프를 어떻게 구현해야합니까? 대신 관계형 데이터베이스를 고려해야합니까?

Answer 1

공간 효율성을 우선시한다면 그래프 작업에서 시간 효율성을 희생하고 Hashtable (노드의 레이블이 지정된 링크를 저장하는 데 사용하는 것으로 가정)을 제거 할 수 있습니다. 즉 라벨이 지정된 노드에 대한 고유하지 않은 (당신이 더 메모리 사용 및 라벨의 당신의 공간을 짜하려면 유한

public class Node { 
    private Links[] links; 

    // ... the ops ... 

    public static final class Link { 
     String label; 
     Node target; 
    } 
} 

: 간단하게 배열로 전환 그래프 작업에 라벨 값을 비교하는 비용을 부담 예 : "parent"는 반복해서 나타나는 레이블입니다) 인스턴스를 복제하지 않으므로 flyweight pattern에 대해 사용자 정의 Label 클래스를 사용하는 것을 고려하십시오.

Answer 2

주된 관심사는 직렬화 될 때 디스크의 크기 또는 메모리의 크기입니까? 당신은 메모리의 크기에 대한 우려, 당신은 반드시 동시에 메모리의 각 노드를 개최 할 필요가없는 경우, 당신은 db4o

으로 transparent activation 같은 것을 사용하여 지연로드의 몇 가지 유형을 사용하여 조사 할 수 있습니다 경우

Answer 3

계속 확장 성이 필요한 경우 설명하는 많은 수의 그래프 (수백만 또는 수십억 개의 관계)를 처리 할 수있는 Neo4J과 같은 기존 그래프 데이터베이스를 사용하는 것이 좋습니다. 좋은 결과를 얻은 2,500 만 개의 그래프 그래프에 사용했습니다.