31Jul2026
15:00 Master's Defense Room 85 of IC2
Topic on
Grammatical compression in external memory based on induced suffix ordering.
Student
Victor Racso Galvan Oyola
Advisor / Teacher
Guilherme Pimentel Telles - Co-advisor: Daniel Saad Nogueira Nunes
Brief summary
The rapid expansion of datasets in areas such as bioinformatics and large language model training has led to inputs that frequently exceed the capacity of main memory, motivating the development of compression algorithms in the out-of-memory model. Among the available compression paradigms, grammar-based compression is particularly attractive because it represents a text as a context-free grammar that generates it as its only derivation, allowing compact storage while supporting operations such as decompression and substring extraction directly from the compressed representation. These properties also make grammar-based compression algorithms useful as building blocks for compressed text indexes and self-indexing structures. Among grammar-based compression algorithms, Grammar Compression by Induced Sorting (GCIS) recursively constructs grammars using suffix-induced sorting techniques. However, GCIS assumes an internal memory scenario and does not scale to large out-of-memory workloads. We present eGCIS, the first out-of-memory adaptation of GCIS. Based on the fSAIS external-memory suffix array construction algorithm, eGCIS reuses intermediate structures already produced during induced sorting, including recursively sorted substrings and reduced texts, to generate grammar rules throughout the recursion. The resulting construction pipeline relies exclusively on external-memory primitives, such as sequential scans and external sorting, avoiding random access to the input text. We also developed an external-memory decoder capable of reconstructing the original text under RAM constraints. Experimental results show that eGCIS can compress and decompress inputs up to 4 GiB using only 32 MiB of RAM, demonstrating that grammar-based compression via induced sorting can be effectively performed in the external-memory model.
Examination Board
Headlines:
| Guilherme Pimentel Telles | IC / UNICAMP |
| Diego Gastón Arroyuelo Billiardi | PUC/Chile |
| Nalvo Franco de Almeida Junior | UFMS |
Substitutes:
| Santiago Valdés Ravelo | IC / UNICAMP |
| Maria Emília Machado Telles Walter | UnB |