Gonzalo Navarro
Profesor Titular
Gonzalo Navarro
Nombramiento Académico Actual
- Académico - Profesor Titular
Títulos y Grados
- Doctor - Universidad De Chile 1998
- Magíster - Universidad De Chile 1995
Cargos en Docencia y/o Administración
- Coordinador de Biblioteca - Departamento de Ciencias de la Computación actual
- Coordinador del Doctorado en Computación - Departamento de Ciencias de la Computación actual
- Coordinador de Investigación - Departamento de Ciencias de la Computación actual
- Coordinador de Postgrado - Departamento de Ciencias de la Computación actual
- Director Comité de Postgrado DCC - Departamento de Ciencias de la Computación actual
- Director - Departamento de Ciencias de la Computación 2007 - 2009
- Jefe Docente - Departamento de Ciencias de la Computación 2003 - 2007
Docencia Últimos 7 años
-
CC4102 Diseño y Análisis de Algoritmos
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2021 Primavera y 2020 Primavera
-
CC7920 Introducción a la Tesis
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC7010 Pasantía de Investigación I
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC7015 Pasantía de Investigación II
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8910 Trabajo de Tesis I
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8920 Trabajo de Tesis II
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8930 Trabajo de Tesis III
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8940 Trabajo de Tesis IV
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8950 Trabajo de Tesis V
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC8960 Trabajo de Tesis VI
Impartido en 2026 Primavera, 2026 Otoño, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC6919 Trabajo de Título
Impartido en 2026 Primavera, 2026 Otoño y 2025 Otoño
-
CC7020 Investigación Dirigida
Impartido en 2026 Primavera, 2025 Primavera, 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Primavera, 2022 Otoño, 2021 Primavera, 2021 Otoño, 2020 Primavera y 2020 Otoño
-
CC5905 Trabajo Dirigido
Impartido en 2026 Primavera, 2025 Otoño y 2024 Otoño
-
CC7320 Estructuras de Datos Comprimidas
Impartido en 2026 Otoño, 2025 Primavera, 2024 Primavera, 2024 Otoño, 2023 Otoño, 2022 Otoño, 2021 Otoño y 2020 Otoño
-
CC7025 Escuela Temática Internacional
Impartido en 2025 Otoño
-
CC3102 Teoría de la Computación
Impartido en 2025 Otoño y 2021 Primavera
-
CC6909 Trabajo de Título
Impartido en 2025 Otoño, 2024 Primavera, 2024 Otoño, 2023 Primavera, 2023 Otoño, 2022 Otoño, 2021 Primavera, 2021 Otoño y 2020 Primavera
-
CC3101 Matemáticas Discretas para la Computación
Impartido en 2022 Otoño y 2020 Otoño
Investigación Últimos 7 Años
Publicaciones
-
Smallest suffixient sets: Effectiveness, resilience, and calculation
THEORETICAL COMPUTER SCIENCE, 2026
-
A textbook solution for dynamic strings
THEORETICAL COMPUTER SCIENCE, 2026
-
Smallest Suffixient Sets asaRepetitiveness Measure
Lecture Notes in Computer Science, 2026
-
Cache-Friendly Compressed Boolean Matrices
Lecture Notes in Computer Science, 2026
-
New compressed indices for multijoins on graph databases
INFORMATION SYSTEMS, 2026
-
Preface
OpenAccess Series in Informatics, 2025
-
BWT Indexes for Optimal Joins in Graph Databases
OpenAccess Series in Informatics, 2025
-
Compact Data Structures for Collections of Sets
OpenAccess Series in Informatics, 2025
-
Faster Run-Length Compressed Suffix Arrays
OpenAccess Series in Informatics, 2025
-
Fast and Small Subsampled R-indexes
ACM TRANSACTIONS ON ALGORITHMS, 2025
-
CompactLTJ: Space & Time Efficient Leapfrog Triejoin on Graph Databases
VLDB JOURNAL, 2025
-
(Worst-case) Optimal Adaptive Dynamic Bitvectors
THEORY OF COMPUTING SYSTEMS, 2025
-
Practical Adaptive Dynamic Bitvectors
SOFTWARE-PRACTICE & EXPERIENCE, 2025
-
Worst-Case-Optimal Joins on Graphs with Topological Relations
WWW 2025 - Proceedings of the ACM Web Conference, 2025
-
Text Indexing for Simple Regular Expressions
Leibniz International Proceedings in Informatics, LIPIcs, 2025
-
Counting on General Run-Length Grammars
Leibniz International Proceedings in Informatics, LIPIcs, 2025
-
Stronger compact representations of object trajectories
GEO SPATIAL INFORMATION SCIENCE, 2025
-
Repetitiveness measures based on string morphisms
THEORETICAL COMPUTER SCIENCE, 2025
-
Space-efficient data structures for the inference of subsumption and disjointness relations
SOFTWARE-PRACTICE & EXPERIENCE, 2025
-
Computing MEMs and Relatives on Repetitive Text Collections
ACM TRANSACTIONS ON ALGORITHMS, 2025
-
Generalized straight-line programs
ACTA INFORMATICA, 2025
-
Evaluating regular path queries on compressed adjacency matrices
VLDB JOURNAL, 2025
-
Adaptive Dynamic Bitvectors
Lecture Notes in Computer Science, 2025
-
Compressed Graph Representations for Evaluating Regular Path Queries
Lecture Notes in Computer Science, 2025
-
Clustering-based compression for raster time series
COMPUTER JOURNAL, 2024
-
Dynamic compact data structure for temporal reachability with unsorted contact insertions
COMPUTER JOURNAL, 2024
-
A Textbook Solution for Dynamic Strings
Leibniz International Proceedings in Informatics, LIPIcs, 2024
-
MillenniumDB: A Multi-modal, Multi-model Graph Database
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2024
-
BAT-LZ out of hell
Leibniz International Proceedings in Informatics, LIPIcs, 2024
-
Space & Time Efficient Leapfrog Triejoin
Proceedings of the 7th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems, (GRADES) and Network Data Analytics, (NDA), GRADES-NDA 2024, 2024
-
Taxonomic Classification with Maximal Exact Matches in KATKA Kernels and Minimizer Digests
Leibniz International Proceedings in Informatics, LIPIcs, 2024
-
Tackling Challenges in Implementing Large-Scale Graph Databases
COMMUNICATIONS OF THE ACM, 2024
-
Faster Maximal Exact Matches with Lazy LCP Evaluation
Data Compression Conference Proceedings, 2024
-
The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2024
-
Two-Dimensional Block Trees
COMPUTER JOURNAL, 2024
-
Wheeler Maps
Lecture Notes in Computer Science, 2024
-
Space-Efficient Conversions from SLPs
Lecture Notes in Computer Science, 2024
-
Iterated Straight-Line Programs
Lecture Notes in Computer Science, 2024
-
Optimizing RPQs over a compact graph representation
VLDB JOURNAL, 2024
-
Near-Optimal Search Time in d-Optimal Space, and Vice Versa
ALGORITHMICA, 2024
-
Constant Time and Space Updates for the Sigma-Tau Problem
Lecture Notes in Computer Science, 2023
-
A Simple Grammar-Based Index for Finding Approximately Longest Common Substrings
Lecture Notes in Computer Science, 2023
-
Evaluating Regular Path Queries on Compressed Adjacency Matrices
Lecture Notes in Computer Science, 2023
-
MillenniumDB: An Open-Source Graph Database System
DATA INTELLIGENCE, 2023
-
Computing MEMs on Repetitive Text Collections
Leibniz International Proceedings in Informatics, LIPIcs, 2023
-
L-Systems for Measuring Repetitiveness
Leibniz International Proceedings in Informatics, LIPIcs, 2023
-
Compact Data Structures Meet Databases
Leibniz International Proceedings in Informatics, LIPIcs, 2023
-
Compact representations of spatial hierarchical structures with support for topological queries
INFORMATION AND COMPUTATION, 2023
-
Toward a Definitive Compressibility Measure for Repetitive Sequences
IEEE TRANSACTIONS ON INFORMATION THEORY, 2023
-
Space/time-efficient RDF stores based on circular suffix sorting
JOURNAL OF SUPERCOMPUTING, 2023
-
Efficient Construction of the BWT for Repetitive Text Using String Compression
INFORMATION AND COMPUTATION, 2023
-
Faster compressed quadtrees
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2023
-
Navigating planar topologies in near-optimal space and time
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2023
-
Efficient Construction of the BWT for Repetitive Text Using String Compression
Leibniz International Proceedings in Informatics, LIPIcs, 2022
-
Grammar Compression by Induced Suffix Sorting
Journal of Experimental Algorithmics, 2022
-
Graph Compression for Adjacency-Matrix Multiplication
SN Computer Science, 2022
-
Correction to: Graph Compression for Adjacency-Matrix Multiplication (SN Computer Science, (2022), 3, 3, (193), 10.1007/s42979-022-01084-2)
SN Computer Science, 2022
-
Bi-Directional r-Indexes
Leibniz International Proceedings in Informatics, LIPIcs, 2022
-
Balancing Run-Length Straight-Line Programs
Lecture Notes in Computer Science, 2022
-
Near-Optimal Search Time in d -Optimal Space
Lecture Notes in Computer Science, 2022
-
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
Data Compression Conference Proceedings, 2022
-
Time- and Space-Efficient Regular Path Queries
Proceedings - International Conference on Data Engineering, 2022
-
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
PROCEEDINGS OF THE VLDB ENDOWMENT, 2022
-
Total mutational load and clinical features as predictors of the metastatic status in lung adenocarcinoma and squamous cell carcinoma patients
JOURNAL OF TRANSLATIONAL MEDICINE, 2022
-
Faster repetition-aware compressed suffix trees based on Block Trees
INFORMATION AND COMPUTATION, 2022
-
A practical succinct dynamic graph representation
INFORMATION AND COMPUTATION, 2022
-
Optimal Joins Using Compressed Quadtrees
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2022
-
The Compression Power of the BWT
COMMUNICATIONS OF THE ACM, 2022
-
Efficient and compact representations of some non-canonical prefix-free codes
THEORETICAL COMPUTER SCIENCE, 2022
-
Engineering Practical Lempel-Ziv Tries
Journal of Experimental Algorithmics, 2021
-
On Stricter Reachable Repetitiveness Measures
Lecture Notes in Computer Science, 2021
-
An LMS-Based Grammar Self-index with Local Consistency Properties
Lecture Notes in Computer Science, 2021
-
PFP compressed suffix trees
Proceedings of the Workshop on Algorithm Engineering and Experiments, 2021
-
PHONI: Streamed Matching Statistics with Multi-Genome References
Data Compression Conference Proceedings, 2021
-
An index for moving objects with constant-time access to their compressed trajectories
INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE, 2021
-
A grammar compressor for collections of reads with applications to the construction of the BWT
Data Compression Conference Proceedings, 2021
-
Compact Representation of Spatial Hierarchies and Topological Relationships
Data Compression Conference Proceedings, 2021
-
A Disk-Based Index for Trajectories with an In-Memory Compressed Cache
Data Compression Conference Proceedings, 2021
-
Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures
ACM COMPUTING SURVEYS, 2021
-
Indexing Highly Repetitive String Collections, Part II: Compressed Indexes
ACM COMPUTING SURVEYS, 2021
-
Range Majorities and Minorities in Arrays
ALGORITHMICA, 2021
-
Grammar-compressed indexes with logarithmic search time
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2021
-
Optimal-Time Dictionary-Compressed Indexes
ACM TRANSACTIONS ON ALGORITHMS, 2021
-
On the Approximation Ratio of Ordered Parsings
IEEE TRANSACTIONS ON INFORMATION THEORY, 2021
-
Block trees
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2021
-
Compact structure for sparse undirected graphs based on a clique graph partition
INFORMATION SCIENCES, 2021
-
Towards a Definitive Measure of Repetitiveness
Lecture Notes in Computer Science, 2020
-
Latin America Regional Special Section
COMMUNICATIONS OF THE ACM, 2020
-
Predecessor Search
ACM COMPUTING SURVEYS, 2020
-
Practical Random Access to SLP-Compressed Texts
Lecture Notes in Computer Science, 2020
-
Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
JOURNAL OF THE ACM, 2020
-
Improved compressed string dictionaries
CEUR Workshop Proceedings, 2020
-
On the reproducibility of experiments of indexing repetitive document collections
CEUR Workshop Proceedings, 2020
-
Lempel-Ziv-Like Parsing in Small Space
ALGORITHMICA, 2020
-
Contextual Pattern Matching
Lecture Notes in Computer Science, 2020
-
On dynamic succinct graph representations
Data Compression Conference Proceedings, 2020
-
Semantrix: A compressed semantic matrix
Data Compression Conference Proceedings, 2020
-
Approximating optimal bidirectional macro schemes
Data Compression Conference Proceedings, 2020
-
Optimal joins using compact data structures
Leibniz International Proceedings in Informatics, LIPIcs, 2020
-
Tree path majority data structures
THEORETICAL COMPUTER SCIENCE, 2020
-
Compressed Dynamic Range Majority and Minority Data Structures
ALGORITHMICA, 2020
-
Text Indexing and Searching in Sublinear Time
Leibniz International Proceedings in Informatics, LIPIcs, 2020
-
Fast and compact planar embeddings
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2020
-
Ranked document selection
THEORETICAL COMPUTER SCIENCE, 2020
-
Parallel computation of the Burrows Wheeler Transform in compact space
THEORETICAL COMPUTER SCIENCE, 2020
-
Fast Compressed Self-indexes with Deterministic Linear-Time Construction
ALGORITHMICA, 2020
-
Extending general compact querieable representations to GIS applications
INFORMATION SCIENCES, 2020
Proyectos de Investigación
-
Space/Time Efficient Solutions to Extend Graph Databases
Fondecyt_Anid, 1260080, 2026 - 2029
-
Compact Data Structures for Gaph Databases
Fondecyt_Anid, 1230755, 2023 - 2026
-
Practical Indexes for Very Large Repetitive Text Collections
FONDECYT, 1200038, 2020 - 2023
-
Measures of Compressibility of Repetitive Text Collections: Their Relations and Applications
FONDECYT, 3201041, 2020 - 2022
-
Evaluating Database Queries Through Points and Boxes
FONDECYT, 3190550, 2019 - 2021
-
Compressed data structures for highly repetitive data sets
FONDECYT, 1170048, 2017 - 2020
-
Efficient Compressed Indexes Construction for Multicore Architectures
FONDECYT, 3170534, 2017 - 2020
-
Instituto Milenio de Investigación sobre los Fundamentos de los Datos - IMFD
Iniciativa científica Milenio, IM1705, 2017 - 2027
-
Centro de Biotecnología y Bioingeniería
Programa Financiamiento Basal, FB0001, 2014 - 2025
© 2026 Departamento de Ciencias de la Computación, Universidad de Chile
Of. N312