Grammar-based graph compression. (July 2018) - Maneth, Sebastian; Peternek, Fabian
Highlights: We present a linear time graph compression algorithm. The algorithm produces straight-line graph grammars. A resulting grammar can be, in the limit, exponentially smaller than the given graph. Certain queries such as reachability queries can be performed directly on the grammar, without prior decompression. Abstract: We present a new graph compressor that works by recursively detecting repeated substructures and representing them through grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. Specific queries such as reachability between two nodes or regular path queries can be evaluated in linear time (or quadratic times, respectively), over the grammar, thus allowing speed-ups proportional to the compression ratio.