Papers for

data system architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Grammar compression algorithm has growing worst-case inefficiency

A Non-constant Lower Bound for Grammar-Based Compression with Greedy

Abstract: We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

Thu 10 SeptData Structures and AlgorithmsFormal Languages and Automata Theory
The gist
Compressing data by finding patterns and expressing them as rules is common, but figuring out how well certain methods perform is tricky. The authors show that a popular greedy method for grammar-based compression can sometimes perform increasingly worse compared to the best possible compression as the data size grows. This means that the efficiency of this method doesn’t just have a fixed worst case; it can get worse logarithmically with input size. They also used formal verification tools to prove their finding rigorously.
Open → 2609.12106v1