Doing computation with graphs often causes the machine to be bandwidth bounded when retrieving the neighbors of a vertex. One way to help with this issue is to compress the set of neighbors. This improves performance because now we need to load and store fewer bytes of information, hence requesting less bandwidth. Although more computation is needed in order to encode and decode the edge set, this does not affect the performance because we are ultimately still bounded by bandwidth.
kayvonf
"Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+". Shun et al. 2015
Elias gamma encoding is another popular compression technique whose use could potentially be explored in such scenarios.
themj
Why does storing the encoding width reduce the encoding size? Is it because the smaller numbers can be encoded in less than 4 bytes if necessary?
rrp123
In this case however, when we're jumping from 1030 to 100000, wouldn't we want to use 100000 as the base for all future numbers? This way, we will be able to compress the numbers after 100000 to take up less memory than 4 bytes each, unlike what they're doing now.
Doing computation with graphs often causes the machine to be bandwidth bounded when retrieving the neighbors of a vertex. One way to help with this issue is to compress the set of neighbors. This improves performance because now we need to load and store fewer bytes of information, hence requesting less bandwidth. Although more computation is needed in order to encode and decode the edge set, this does not affect the performance because we are ultimately still bounded by bandwidth.
"Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+". Shun et al. 2015
http://www.cs.cmu.edu/~jshun/ligra+.pdf
Elias gamma encoding is another popular compression technique whose use could potentially be explored in such scenarios.
Why does storing the encoding width reduce the encoding size? Is it because the smaller numbers can be encoded in less than 4 bytes if necessary?
In this case however, when we're jumping from 1030 to 100000, wouldn't we want to use 100000 as the base for all future numbers? This way, we will be able to compress the numbers after 100000 to take up less memory than 4 bytes each, unlike what they're doing now.