• algorithms
• compresseddatastructure
• database
• datacompression
• datastructure

Our society is generating an exponentially increasing amount of data that is becoming
progressively repetitive. While compressed data structures have traditionally played a
crucial role in addressing repetitiveness, the current dynamic data flow is characterised
by new emerging patterns and trends. Ignoring this evolving tendency means missing
out on the opportunity to significantly enhance both space and time efficiency in system
performance.
In this thesis, we design, implement, and experimentally validate innovative, distinctive,
and data-aware compressed data structures for a wide set of data types. As a result, our
schemes automatically tailor to new patterns and trends arising from Big Data using brand
new algorithms, as well as state-of-the-art machine-learning-inspired techniques.
This research introduces a learned approach to address the ubiquitous problem of com-
pressing and indexing integers. Additionally, it explores data-aware optimisation strategies
for constructing compressed trie structures, thereby indexing and compressing strings.
The exploration extends to theoretically grounded solutions for selecting compression
encodings for table columns within industrial analytical database management systems.
Furthermore, it delves into the compression of huge source code datasets, considering file
similarity based on the actual content. To underscore the substantial practical benefit these
techniques bring, they have been thoroughly compared against well-engineered known
solutions. The dataset size goes from tens of GB of integers and strings to petabytes scale
database columns and ultra-large-scale source code datasets.
In conclusion, this PhD thesis represents a contribution to the evolving landscape of data
management and compression in the era of Big Data. The data-aware compressed data
structures proposed and examined herein contribute to the emerging trend of designing
adaptive systems that can automatically tailor themselves to diverse patterns.