Hypergraphs model complex, non-binary relationships such as co-authorships, social group memberships, and recommendation systems. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26 % to 79 % of the original file size on real-world hypergraphs-outperforming existing methods on all large hypergraphs in our experiments. HyperCSA also scales to larger datasets than existing approaches and evaluates neighbor queries 6 to 40 times faster on common real-world hypergraphs.

Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We enable the use of multi-string BWT construction algorithms to construct the BWT of a long string by partitioning it into shorter substrings using a prefix of the suffix array. We prove that except for a single run of sentinel symbols $, the BWT of the shorter substrings is equal to the BWT of the long string. The proposed partitioning idea is applicable to string collections of any alphabet.

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.

A fundamental operation on large graphs is the search of occurrences of a given pattern in the graph. Like [1], we consider an original graph OG and a query pattern Q of labeled nodes and unlabeled edges and aim to compute a relation called simulation of Q in OG, which determines a superset of the occurrences of Q in OG. An algorithm in [1] computes the simulation of Q in OG in time O(n*m) for n vertices and m edges of OG. In comparison, we have developed an algorithm [2] that works on a compressed graph grammar GG of OG, instead of operating on OG itself. The speed-up of our algorithm [2] compared to the algorithm in [1] grows with the size |OG| of OG and with the compression strength |OG| / |GG| of the graph grammar GG.

Huge amounts of tree structured data (such as JSON, XML, etc.) can be compressed to straight-line context-free (SLCF) tree grammars. This compression of tree-structured data of size O(N) reduces the number of edges ideally to O(log N), which reduces the memory footprint and speeds-up search algorithms. Nevertheless, grammar-based tree compression has two major limitations resulting in an unnecessary high number of edges: first, updates of SLCF grammars by path extraction over time increase the grammar size, second, a given sibling-order prohibits a compression of arbitrary combinations of siblings. A way out of the first limitation is re-compression, i.e. to find a stronger compressed SLCF tree grammar of the tree without decompressing the given grammar. A way out of the second limitation is an extension of re-compression to unordered trees. RECUT provides not only re-compression for unordered trees, but also for partially ordered trees. Furthermore, whenever parts of the data are unordered - as it is the case for data-centric data - RECUT significantly improves grammar-based compression by further reducing the number of edges in the compressed data by a factor of up to 30.

XML tree structures can be effectively compressed using straight-line grammars. It has been an open problem how to update straight-line grammars, while keeping them compressed. Therefore, the best previous known methods resort to periodic decompression followed by compression from scratch. The decompression step is expensive, potentially with exponential running time. We present a method that avoids this expensive step. Our method recompresses the updated grammar directly, without prior decompression; it thus greatly outperforms the decompress-compress approach, in terms of both space and time. Our experiments show that the obtained grammars are similar or even smaller than those of the decompress-compress method.

Summary form only given. Grammar-based compression yields high compression ratios for XML document trees. However, the holy grail of grammar-based compression has been how to support incremental updates. Supporting updates is a crucial demand for many applications. The best available method decompresses the grammar, performs the update, and compresses the result. The new Online Repair algorithm presented here recompresses a given updated tree grammar directly, without decompression. Surprisingly, the algorithm yields the same compression ratios as the decompress-update-compress strategy, while being much more efficient in time and space.

Text compression techniques like bzip2 lack the possibility to delete the nth word or to insert text be-fore the nth word of compressed texts without prior decompression of the compressed texts. We present a text compression technique that supports fast insertion into and deletion from compressed texts without full decompression of the compressed text. Our approach combines Indexed Reversible Transformation (IRT) [1], Run-Length-Encoding (RLE), and the Wavelet Tree (WT). For a reasona-ble size of inserted or deleted texts (more details are given in [2]), our approach is faster than modifying uncompressed text preceded by a decompression step and followed by a compression step.

Text compression techniques like bzip2 lack the possibility to search or to update substrings at given positions of texts that have been compressed without prior decompression of the compressed text. We have developed Indexed Reversible Transformation (IRT), a modified version of the Burrows-Wheeler-Transformation (BWT) that in combination with run length encoding (RLE) and wavelet trees (WT) allows for position-based searching and updating substrings of compressed texts without prior decompression of the compressed text. As a result, IRT may be useful for a huge class of applications that due to space limitations prefer to search or to modify compressed texts instead of uncompressed texts.