As for backend, you might want to choose between the various backends as supported by AnyDBM_File; BerkeleyDB, in particular BerkeleyDB::Hash might be a good choice.

The advantage is that no rewriting of your code is necessary: it's just a hash. You will likely lose raw speed, though.

If you don't mind rewriting, you might want to look into DBD::SQLite as a backend for DBI, which gives you a SQL interface to your data.

What does a node look like?

If performance is important, before you consider paying the penalties of constructing, updating and traversing a disk-based graph, consider using a more memory efficient data structure.

If you store 10 million of the following simple nodes as:

1. Array of hashes:

   >perl -E"$a[$_] = {a=>1,b=>3.2,c=>'a short string'} for 1..10e6; <>"
   [download]

   It requires ~3.9 GB.

2. Array of arrays:

   >perl -E"$a[$_] = [1,3.2,'a short string'] for 1..10e6; <>"
   [download]

   ~2.8 GB.

   As an array of simple (or packed) strings:

   >perl -E" $a[$_] = qq[1,3.2,'a short string'] for 1..10e6; <>"
   >perl -E" $a[$_] = pack 'VdA8', 1,3.2,'a short string' for 1..10e6; <>
   +"
   [download]

   Only 1.1 GB.

By saving 75% of the memory requirement, you may be able to fit all your data in to ram comfortably.

It means that you need to split or unpack and join or repack each time you access or modify a node, but that will be far faster than doing disk IO. You can easily hide the details of the splitting and joining behind a tied array or an OO class. And you can even add a simple caching mechanism to avoid re-splitting in a read-update sequence.

Or an SQL database (lots of database interfaces around, for example DBIx::Simple, DBIx:Class), but you also would need to install a database engine.

Files for individual nodes would be a bad idea, as every access of a node would entail the opening of a file, heavy overhead I would assume.

Installing a database engine is not such a problem. There are quite a few to choose from. Even most of the big expensive ones have free developer versions. Plus you may use DBD::SQLite which is a database engine inside a module. No need to install anything more.

Jenda
Enoch was right!
Enjoy the last years of Rome.

Depending on the nature of the nodes and how they're going to be accessed/manipulated, an object store (such as Pixie, Tangram, or KiokuDB) seems likely to work well for something like this, while avoiding the need to worry about SQL schemas (even if the objects are ultimately stored into an SQL database).

Well, in this case it seems that the whole schema will be just two tables

CREATE TABLE dbo.Users (
  Id int not null identity(1,1) primary key,
  Code varchar(...),
  FirstAttribute ...,
  SecondAttribute ...,
  ...
)go
CREATE INDEX idx_Users_Code ON dbo.Users(Code)
go

CREATE TABLE dbo.Links (
  UserId1 int not null,
  UserId2 int not null,
  Weight ...,
  CONSTRAINT pk_Links PRIMARY KEY CLUSTERED (UserId1, UserId2)
)go
[download]

and that's about it.

Object store is most likely an overcomplication in this case.

Jenda
Enoch was right!
Enjoy the last years of Rome.

I've made a graph using the Graph module that has 0.5 million nodes and 100 thousand links. It takes > 300M of memory, so tieing it to disk or increasing the amount of swap space might work. The other possibility, depending on the nature of the graph, is to try PDL which is implemented in C and use a matrix representation for the weighted graph with other data structures to handle the various attributes.

If you get desperate enough to write it yourself, take a gander at the C++ code under Optimising "generalised modularities". For my graph, it runs very fast.

Ea

I'd agree with this; the matrix approach I'd go with is an incidence one, which would be O(E), here 2*100k (col1=startpoint,col2=endpoint). The adjacency approach would be 500k*500k = 2.5e11 = 250 billion entities = minimum 30GB even if you used bitfields. Naturally, I think PDL would be a good platform for this.