ITR: Grammar-based graph compression supporting fast triple queries
Enno Adler, Stefan Böttcher, Rita Hartel · 2024
Neighborhood queries are the most common queries on graphs; thus, it is desirable to answer them efficiently on compressed data structures. Our full paper [1] presents a grammar-based compressor called Incidence-Type-RePair (ITR) for graphs with labeled nodes and labeled edges based on RePair. We applied ITR to network, version, and RDF graphs and we compared the performance of triple SPO queries on these compressed datasets generated by ITR and 4 state-of-the-art graph compression approaches. As shown in the figure below and in our full paper [1] , ITR outperforms the other graph compressors for all triple SPO queries except for the query-type ? P ?, while providing a compression size comparable to the other compressors. Thereby, ITR is 2 to 6 times faster than the fastest compared query-evaluation technique and up to 100 times faster than the slowest approach in our tests.