Compressing Graphs by Grammars

Sebastian Maneth, Fabian Peternek

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a new graph compressor that detects repeating substructures and represents them by grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. For RDF graphs and version graphs it outperforms the best known previous methods. Specific queries such as reachability between two nodes, can be evaluated in linear time over the grammar, thus allowing speed-ups proportional to the compression ratio.
Original languageEnglish
Title of host publicationProceedings of the 32nd International Conference on Data Engineering -- ICDE 2016
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)978-1-5090-2020-1
Publication statusPublished - 23 Jun 2016
Event2016 IEEE 32nd International Conference on Data Engineering - Helsinki, Finland
Duration: 16 May 201620 May 2016


Conference2016 IEEE 32nd International Conference on Data Engineering
Abbreviated titleICDE 2016
Internet address

Fingerprint Dive into the research topics of 'Compressing Graphs by Grammars'. Together they form a unique fingerprint.

Cite this