Expand description
The cold form: the same adjacency at bits an edge rather than bytes.
Adjacency is what a graph being written looks like,
twelve bytes an edge and every operation O(1). Csr is what the settled
part of it looks like once nothing is changing it: read only, node grouped,
and about an order of magnitude smaller. Spec 11 section 2 calls these the
hot form and the cold form and expects a graph to be mostly cold, because a
graph that is being traversed is very rarely being edited at the same rate.
§The shape
Nodes are dense u32 ids, cut into groups of GROUP consecutive ids.
Everything that varies is chosen per group, so one hub does not set the
width of the whole graph. A group carries:
- a table of one bit offset per node, at the width that group’s stream needs, pointing at where that node’s run starts,
- the runs themselves, each of them a degree, then the first neighbour written against the group’s smallest neighbour, then the gaps between the rest.
The gaps go out in blocks of BLOCK with a width per block rather than a
width per run. That is the one idea from BtrBlocks and FastLanes that is
worth taking here: a run of ten thousand where one gap is enormous and the
rest are small would otherwise pay the enormous one ten thousand times, and
a block only ever pays it thirty two times. It costs seven bits a block,
which is under a quarter of a bit an edge, and no extra offsets at all,
because a run is decoded from its start and the blocks come in order.
A block whose width does not fit everything in it leaves the ones that did
not fit behind as patches, written again at the end of the block with their
positions, which is what PFOR does. The encoder tries every width and keeps
the cheapest, so a block only patches when patching is cheaper than widening.
This was measured before and rejected, and what changed is the numbering
rather than the code: under a degree ordering the gaps in one block are all
about the same size and there is nothing to patch, and under the community
numbering in bisect a block is mostly ones with a jump to
another community in it, which is exactly the shape patching is for. It is
worth 0.65 bits an edge on R-MAT, 2.36 on soc-LiveJournal1 as its ids arrive,
and 5.41 on a bisected web-Google. On a uniform graph it is a wash, 15.98
before and 15.96 after, because there the widths in a block already agree and
the few blocks that do patch save about what the headers cost. It is worth
about a tenth of the decode, which is the trade being made.
Elias gamma, which needs no width at all, was 1.7 bits an edge worse on R-MAT and 7.7 worse on a uniform graph, and is not here.
§What it costs
Two things, and they pull in opposite directions. The payload is the gaps,
and how small they are is a property of the graph rather than of the
encoder: a uniformly random graph on n nodes with m edges cannot be
stored below about log2(n * n / m) + 1.44 bits an edge no matter what
anybody does. The 8 bits an edge in 11 is not a claim about random
graphs. It is paid for entirely by real graphs having hubs and communities,
so neighbours cluster and the gaps between them are small.
The overhead is the node offset table plus the per run header, and it is per node rather than per edge, so it is loud at degree one and inaudible at degree a hundred.
The test at the bottom of this file measures both a uniformly random graph and an R-MAT graph, which is the standard synthetic social graph and the one Graph500 uses. At 65536 nodes and an average degree of 16:
total table head gaps
uniform 15.96 1.06 1.31 13.58
R-MAT 11.98 1.00 1.14 9.83
R-MAT, degree ordered 9.38 0.69 0.78 7.90The uniform row is 15.96 against a floor of 13.44, so the encoder is within
a fifth of what is provably possible on the case where nothing can help. The
whole of the rest is the graph: R-MAT is 3.98 bits an edge cheaper for no
other reason than that it has hubs, and order_by_degree takes another
2.60 off by giving those hubs the small ids. The same ordering pass moves a
uniform graph by nothing at all, which is the control that says it is the
structure being exploited rather than the measurement.
§What it costs on a graph nobody here generated
R-MAT is a stand in and it is known to cluster less than the social graphs it
stands in for, so a real one should come out under 9.38. It does not.
soc-LiveJournal1 from SNAP, 4847571 nodes and 68993773 edges, on server3,
through examples/compress.rs:
total offsets degrees firsts widths gaps patches
cold 17.99 1.18 0.49 1.43 0.82 10.58 3.47
cold, degree ordered 19.00 1.13 0.27 1.43 0.74 14.57 0.84
cold, bisected 15.00 1.14 0.42 1.44 0.91 7.53 3.55Three things in that table are worth saying out loud.
The best number is 15.00 and it takes the numbering to get there. Before the
patches and bisect the same three rows were 20.35, 19.62
and nothing, so this graph is a quarter smaller than it was and the whole of
the difference is community structure that was there all along.
Degree ordering now makes this graph bigger, 19.00 against 17.99. SNAP’s ids are roughly the order the crawl found the accounts in, which already puts friends near each other, and sorting by degree throws that away. It was still the right call when the code could not exploit locality, and it stopped being the right call the moment the code could.
The gaps are no longer most of the file. Under bisection the per node fields
are 3.00 of the 15.00 and the payload is 11.99, against a floor, quoted by
--codes, of 10.46 bits a gap or about 9.81 an edge. So the code is now 2.2
bits over what any code that prices each gap on its own could do, where under
degree ordering it was 1.18 over a floor that was itself six bits worse.
gaps 64685321, 24.9% of them 1, 16.6% of neighbours in a run of 4 or more
by length floor 10.46 bits a gap
block of 32 17.06 (unpatched, which is what this used to be)
block of 8 13.99
block of 32, patched 14.06 (the model, and the real one does better)
elias delta 12.14
intervals, block 8 13.78The 8 bits an edge in 11 is still not met and this is 15.00. What would
close it is not another block code: the three that are left are all within a
bit or two of each other and of the floor. It is a better numbering, and the
measurement that says so is that bisection’s own objective, a plain log gap
code, prices this ordering at 9.29 bits a gap where it prices the degree
ordering at 14.87. The numbering has found structure the encoder is only half
spending. Interval encoding, which was dead on arrival under a degree
ordering because only 0.9 percent of neighbours were consecutive, is now
looking at 16.6 percent and is the first thing to try.
§What this does not do
It does not change. There is no link and no unlink, because every edge after
the first in a run is written against the one before it, so touching one is
rewriting the group. New edges go into the hot form and a later sweep folds
them in, which is the promotion in 11 section 2 and is why O-G2, when the
sweep should run, is still open.
It does not renumber behind the caller’s back. order_by_degree hands
back a numbering and renumber applies it, and the caller keeps it,
because the mapping from a caller’s node id to a dense one is the node
table’s and there is no way to read the encoded graph without it.
It does not hold the edge slots. A traversal wants to know where it can go next and nothing else, and the payload for that answer is what is packed here. Edge records are found by their own ids, which is the next piece.
Structs§
Constants§
Functions§
- order_
by_ degree - A node numbering that makes the graph smaller, busiest node first.
- renumber
- Rewrite an edge list under a numbering, in place.