Space Efficient Representation of a Graph in Java?

Question

I want to have an undirected graph where the nodes are labelled with a pair (currently using String[] for this) and can be arbitraryly linked to other nodes. I have started with the type Hashtable. It turns out that this is not space efficient enough for me - I intend on having around 60,000 nodes (eventually, well in excess of that number).

How should I implement this kind of graph so as to be more memory efficient? Should I, instead, be considering some kind of Relational Database?

Answer 1

If space efficiency is your priority, then you can sacrifice time efficiency on graph operations and do away with the Hashtable (which I assume you are using for storing a node's labeled links). Simply switch to an array and incur the cost of comparing label values on graph operations:

public class Node {
    private Links[] links;

    // ... the ops ...

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

If you wish to further squeeze the memory usage and your space of labels is finite (i.e. labels are not unique for a given node; e.g. "parent" is a label that occurs again and again) then consider using a custom Label class per flyweight pattern so you do not duplicate instances of String.

Answer 2

Is your main concern the size on disk when serialized, or the size in memory?

If you are concerned about size in memory, and if you do not necessarily need to hold each node in memory at the same time, you may want to look into using some type of lazy loading using something like transparent activation with db4o