Grammar-based graph compression. (July 2018)

• Record Type: Journal Article
• Authors: Maneth, Sebastian; Peternek, Fabian
• Is Part Of: Information systems. Volume 76:(2018)
• Page Start: 19
• Page End: 45
• Publication Date: 2018-07
• Subjects: Graph compression -- Straight-line context-free hyperedge replacement grammar; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2018.03.002
• Languages: English
• ISSNs: 0306-4379

Abstract

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.