About Graph Index Compression Techniques

We perform a preliminary study on large graph efficient indexing using a gap-based compression techniques and different node labelling functions. As baseline we use the Webgraph + LLP labelling function. To index the graph we use three labelling functions: Pagerank, HITS, and Pagerank with random walks choosing restart nodes with HITS authority scores. To compress the graphs we use Varint GB, with and without d-gaps, derived by rank value of the labelling function. Overall, we compare 8 different methods on different datasets composed by the WebGraph eu-2005, uk-2007-05@100000, cnr-2000, and the social networks, enron, ljournal-2008, provided by the Laboratory for Web Algorithmics (LAW)