Spatial efficient graph representation in Java?
I want to have an undirected graph where the nodes are marked with a pair (currently using String [] for this) and can be arbitrarily linked to other nodes. I started with the Hashtable type. It turns out that this is not enough space for me - I intend to have around 60,000 nodes (ultimately well over that number).
How do I implement such a graph to be more memory efficient? Should I consider some kind of relational database instead?
If space efficiency is your priority, you can sacrifice time efficiency on graph operations and do away with the Hashtable (which I assume you use to store the tagged link node). Just switch to an array and incur the cost of comparing label values ββon graphical operations:
public class Node {
private Links[] links;
// ... the ops ...
public static final class Link {
String label;
Node target;
}
}
If you want to compress memory usage even further, and your label space is finite (i.e. labels are not unique to a given node, for example "parent" is a label that occurs over and over again), then consider using a custom Label
class for flies . so you don't duplicate instances String
.
source to share
Is your main problem the size on disk when serializing or size in memory?
If you're concerned about in-memory size, and if you don't necessarily need to store every node in memory at the same time, you might want to look at using some kind of lazy loading using something like transparent activation with db4o
source to share
If you need consistent scalability, consider using an existing graphing database like Neo4J that can handle LOTS of LARGE graphs you describe (millions or billions of relationships). I've used it for graphs of about 25 million nodes with good results.
source to share