Compact encodings of the web graph are required in order to keep the graph on main memory and to perform operations on the graph efficiently. Link2, the second version of the Link Database by Randall et al., which is part of the Connectivity Server, represented the adjacency list of each vertex by the variable-length nybble codes of delta values. In this paper, the fact is shown that certain variables related to the web graph have power distributions, and the reason is explained why using variable-length nybble codes in Link2 led to a compact representation of the graph from the statistical viewpoint on the basis of the relationship between power distributions and generalization of the variable-length nybble code. Besides, another encoding of the web graph based on these fact and relationship is proposed, and it is compared with Link2 and the encoding proposed by Guillaume et al. in 2002. Though our encoding is slower than Link2, it is 10% more compact than Link2. And our encoding is 20% more compact than the encoding proposed by Guillaume et al. and is comparable to it in terms of extraction time.
展开▼
