Very interesting paper, but the experimental section confuses me. They compare their system which preprocesses the graph into the tile-structure (a compressed representation), but none of the in-memory systems they compare against use a compressed representation. Is this comparison really apples-to-apples? If you can reduce the size in-memory of the graph by 60%, then I would expect an algorithm running on the compressed version to be faster than the same algorithm running on the uncompressed version (assuming that decoding the compressed adjacency-list is significantly cheaper than the cost of a cache-miss).