Modern graphs exert colossal time and space pressure on graph analytics applications. In
2022, Facebook social graph reaches 2.91 billion users with trillions of edges. Many …

We show that a context-free grammar of size that produces a single string of length (such a
grammar is also called a string straight-line program) can be transformed in linear time into a …

The sensitivity of a string compression algorithm C asks how much the output size C (T) for
an input string T can increase when a single character edit operation is performed on T. This …

Lossless data compression is an effective way to handle the huge transmission and storage
overhead of massive text data. Its utility is even more significant today when data volumes …

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 …

Web services are the de-facto standard for implementing web-based systems today, and
comprise message-based interactions involving XML and JSON documents. These formats …

We describe a data structure that stores a strings in space similar to that of its Lempel-Ziv
encoding and efficiently supports access, rank and select queries. These queries are …

Unranked node-labeled trees can be represented using their minimal dag (directed acyclic
graph). For XML this achieves high compression ratios due to their repetitive mark up …

Re-Pair [5] is an effective grammar-based compression scheme achieving strong
compression rates in practice. Let n, σ, and d be the text length, alphabet size, and dictionary …

Representing a proof tree by a combinator term that reduces to the tree lets subtle forms of
duplication within the tree materialize as duplicated subterms of the combinator term. In a …