Man

Gonzalo Navarro

FULL PROFESSOR

UNIVERSIDAD DE CHILE

Santiago, Chile

Líneas de Investigación


Algorithms and Data Structures; Compression; Information Retrieval; Text Compression and Searching; Data Structures for Information Retrieval; Adaptive Analysis of Algorithms; Optimisation of Information Retrieval Systems; Succinct Data Structures

Educación

  •  Informatics, Latin American School of Informatics ESLAI. Argentina, 1992
  •  Informatics, UNIVERSIDAD NACIONAL DE LA PLATA UNLP. Chile, 1993
  •  COMPUTER SCIENCE, UNIVERSIDAD DE CHILE. Chile, 1995
  •  COMPUTER SCIENCE, UNIVERSIDAD DE CHILE. Chile, 1998

Experiencia Académica

  •   FULL PROFESSOR Full Time

    UNIVERSIDAD DE CHILE

    OF PHYSICS AND MATHEMATICAL SCIENCES

    SANTIAGO, Chile

    1995 - A la fecha

Formación de Capital Humano


In the past 3 years the thesis directed are:
4 Undergraduate: Andrés Abeliuk (2012), Hernán Arroyo (2010), Felipe Sologuren (2009), Daniel Valenzuela (2009)
3 Master: Daniel Valenzuela (2013), Eliana Providel (2012), Sebastián Kreft (2010)
3 PhD: Ana Cerdeira (2013), Susana Ladra (2010), Diego Arroyuelo (2009)


Difusión y Transferencia


Interviewed in magazine Bits of Science, number 5, pages 78-81, April 2011.
"Compact Data Structures", magazine Bits of Science, number 3, pages 2-8, November 2009.
Diverse divulgation articles in column Bits, Science, and Society, of Terra.cl, since July 2009
Interview to Ricardo Baeza-Yates, magazine Bits of Science, number 2, pages 30-31, April 2009.
Co-creator and member of the Editorial Board of the magazine Bits of Science, published by the DCC. Participation with an article in the first issue, August 2008.
"Searching the Web", chapter 4 (pages 51-62) in the book How the Web Works, published by the Center for Web Research, Santiago, Chile, 2008. Also, participation as a panelist, as director of the Center and the DCC, in the public presentation of the book, University of Chile, August 2008. The event was mentioned in several press releases and radio stations.
Interview, as Head of Department, in El Mercurio (one of the main Chilean newspapers), March 24, 2008, page A14 (science and technology), about the p osition of the Department on the OOXML standard proposal.
Opinion article "Data Standards and OOXML: today´s vote", as Head of the DCC and on its behalf, in La Nación (nationwide newspaper), March 19, 2008, page 13.
Interview, as Head of the Center for Web Rsearch, in Radio University, 102.5 FM, March 18, 2008, 7:30 to 8:00 PM. With Claudio Gutierrez.
Interview, with other 3 Faculty professors with a high number of ISI publications, in Revista FCFM (magazine of the Faculty of Physical and Mathematical Sciences, University of Chile), number 41, Summer 2008, "Passion for Research", pages 22-25.
Short interview, as Head of Department, in La Tercera (one of the main Chilean newspapers), January 12, 2007, page 7 of section "University Life". In Spanish.
Interview, as Head of the Center for Web Research, in Radio University of Chile, 102.5 FM, November 15, 2006, 7:00 to 7:30 PM.
Interview as Head of the Center for Web Research, in Bioplanet magazine (Chile), year 6, number 42, September 2006. "Center for Web Research: The Science of Finding it All", pages 15-17. With Ricardo Baeza-Yates. In Spanish.
Interview, as Teaching Coordinator of the Department, in the newpaper Publimetro (Chile), August 17 2006, section Admission 2006, page 6. In Spanish.


Premios y Distinciones

  •   Best score at the Faculty of Exact Sciences

    UNIVERSIDAD NACIONAL DE LA PLATA

    Argentina, 1992

    Best score at the Faculty of Exact Sciences

  •   First Prize in the III CLEI-UNESCO

    CLEI-UNESCO

    Colombia, 1996

    First prize in the III CLEI-UNESCO Contest of Latin American Computer Science MSc. Theses (developed during 1995)


 

Article (243)

Adaptive Dynamic Bitvectors
Compressed Graph Representations for Evaluating Regular Path Queries
Evaluating regular path queries on compressed adjacency matrices
A Textbook Solution for Dynamic Strings
BAT-LZ out of hell
Clustering-based compression for raster time series
Dynamic compact data structure for temporal reachability with unsorted contact insertions
Faster Maximal Exact Matches with Lazy LCP Evaluation
Iterated Straight-Line Programs
MillenniumDB: A Multi-modal, Multi-model Graph Database
Near-Optimal Search Time in δ-Optimal Space, and Vice Versa
Optimizing RPQs over a compact graph representation
Space & Time Efficient Leapfrog Triejoin
Space-Efficient Conversions from SLPs
Space-efficient data structures for the inference of subsumption and disjointness relations
Tackling Challenges in Implementing Large-Scale Graph Databases
Taxonomic Classification with Maximal Exact Matches in KATKA Kernels and Minimizer Digests
The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space
Two-Dimensional Block Trees
Wheeler Maps
A Simple Grammar-Based Index for Finding Approximately Longest Common Substrings
Compact Data Structures Meet Databases
Compact representations of spatial hierarchical structures with support for topological queries
Computing MEMs on Repetitive Text Collections
Constant Time and Space Updates for the Sigma-Tau Problem
Efficient construction of the BWT for repetitive text using string compression
L-Systems for Measuring Repetitiveness
MillenniumDB: An Open-Source Graph Database System
Navigating planar topologies in near-optimal space and time
Space/time-efficient RDF stores based on circular suffix sorting
Toward a Definitive Compressibility Measure for Repetitive Sequences
A practical succinct dynamic graph representation
Balancing Run-Length Straight-Line Programs
Bi-Directional r-Indexes
Efficient and compact representations of some non-canonical prefix-free codes
Faster repetition-aware compressed suffix trees based on Block Trees
Grammar Compression by Induced Suffix Sorting
Graph Compression for Adjacency-Matrix Multiplication
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
Near-Optimal Search Time in δ -Optimal Space
Optimal Joins Using Compressed Quadtrees
The Compression Power of the BWT
Time- and Space-Efficient Regular Path Queries
Total mutational load and clinical features as predictors of the metastatic status in lung adenocarcinoma and squamous cell carcinoma patients
A Disk-Based Index for Trajectories with an In-Memory Compressed Cache
A fast and small subsampled R-Index
A grammar compressor for collections of reads with applications to the construction of the BWT
An index for moving objects with constant-time access to their compressed trajectories
An LMS-Based Grammar Self-index with Local Consistency Properties
Block trees
Compact Representation of Spatial Hierarchies and Topological Relationships
Compact structure for sparse undirected graphs based on a clique graph partition
Engineering Practical Lempel-Ziv Tries
Grammar-compressed indexes with logarithmic search time
Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures
Indexing Highly Repetitive String Collections, Part II: Compressed Indexes
On Stricter Reachable Repetitiveness Measures
On the Approximation Ratio of Ordered Parsings
Optimal-Time Dictionary-Compressed Indexes
PFP Compressed Suffix Trees
PHONI: Streamed Matching Statistics with Multi-Genome References
Range Majorities and Minorities in Arrays
Worst-Case Optimal Graph Joins in Almost No Space
Approximating Optimal Bidirectional Macro Schemes
Compressed Dynamic Range Majority and Minority Data Structures
Contextual Pattern Matching
Extending general compact querieable representations to GIS applications
Fast and compact planar embeddings
Fast Compressed Self-indexes with Deterministic Linear-Time Construction
Fully functional suffix trees and optimal text searching in BWT-runs bounded space
Latin America Regional Special Section
Lempel-Ziv-Like Parsing in Small Space
On dynamic succinct graph representations
Parallel computation of the Burrows Wheeler Transform in compact space
Practical Random Access to SLP-Compressed Texts
Predecessor Search
Semantrix: A Compressed Semantic Matrix
Text Indexing and Searching in Sublinear Time
Towards a Definitive Measure of Repetitiveness
Tree path majority data structures
GraCT=> A Grammar-based Compressed Index for Trajectory Data
Lempel-Ziv compressed structures for document retrieval
Universal compressed text indexing
A succinct data structure for self-indexing ternary relations
Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries
Compressed representation of dynamic binary relations with applications
Document retrieval on repetitive string collections
Grammar compressed sequences with rank/select support
Inverted Treaps
Protein complex prediction via dense subgraphs and false positive analysis
TIME-OPTIMAL TOP-k DOCUMENT RETRIEVAL
Top-k Term-Proximity in Succinct Space
Aggregated 2D range queries on clustered points
Faster Compressed Suffix Trees for Repetitive Collections
New dynamic metric indices for secondary memory
Optimal Encodings for Range Majority Queries
Practical compressed string dictionaries
Reporting consecutive substring occurrences under bounded gap constraints
Universal indexes for highly repetitive document collections
Bottom-k document retrieval
Compressed vertical partitioning for efficient RDF management
Efficient and Compact Representations of Prefix Codes
Improved and extended locating functionality on compressed suffix arrays
Near neighbor searching with K nearest references
Optimal Lower and Upper Bounds for Representing Sequences
PcapWT: An efficient packet extraction tool for large volume network traces
The wavelet matrix: An efficient wavelet tree for large alphabets
Compact representation of Web graphs with extended functionality
Compressed representations for web and social graphs
Distributed text search using suffix arrays
Encoding range minima and range top-2 queries
Entropy-bounded representation of point grids
Fully Functional Static and Dynamic Succinct Trees
General document retrieval in compact space
New space/time tradeoffs for top-k document retrieval on sequences
OPTIMAL DYNAMIC SEQUENCE REPRESENTATIONS
Spaces, Trees, and Colors: The Algorithmic Landscape of Document Retrieval on Sequences
XXS: Efficient XPath Evaluation on Compressed XML Documents
Colored range queries and document retrieval
Compact binary relation representations with rich functionality
DACs: Bringing direct access to variable-length codes
Entropy-bounded representation of point grids
On compressing and indexing repetitive sequences
On compressing permutations and adaptive sorting
Space-efficient data-analysis queries on grids
Space-efficient representations of rectangle datasets supporting orthogonal range querying
Succinct nearest neighbor search
Boosting Text Compression with Word-Based Statistical Encoding(1)
Efficient Fully-Compressed Sequence Representations
Implicit indexing of natural language text by reorganizing bytecodes
LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations
New algorithms on wavelet trees and applications to information retrieval
String matching with alphabet sampling
Stronger Lempel-Ziv Based Compressed Text Indexing
Word-Based Self-Indexes for Natural Language Text
Fully Compressed Suffix Trees
Fully dynamic metric access methods based on hyperplane partitioning
Improving semistatic compression via phrase-based modeling
On-line approximate string matching with bounded errors
Self-Indexed Grammar-Based Compression
Space-efficient construction of Lempel-Ziv compressed text indexes
STRONGER QUICKHEAPS
Students' socio-emotional adaptation: Assessment of a new instrument in Concepción city Adaptación socioemocional en escolares: Evaluación de un instrumento nuevo en la provincia de Concepción
Dynamic Lightweight Text Compression
Fast and Compact Web Graph Representations
On Sorting, Heaps, and Minimum Spanning Trees
Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
Storage and Retrieval of Highly Repetitive Sequence Collections
The longest common extension problem revisited and applications to approximate string searching
A Prototype for Querying over LZCS Transformed Documents
Approximate string matching with compressed indexes
Faster entropy-bounded compressed suffix trees
Improving the space cost of k-NN search in metric spaces by using distance estimators
Parameterized matching on non-linear structures
Rank/select on dynamic compressed sequences and applications
Dynamic spatial approximation trees
Effective proximity retrieval by ordering permutations
New adaptive compressors for natural language text
Compressed representations of sequences and full-text indexes
Lempel-Ziv compression of highly structured documents
Lightweight natural language text compression
Rank and select revisited and extended
Rotation and lighting invariant template matching
t-Spanners for metric space searching
Using structural contexts to compress semistructured text collections
A metric index for approximate string matching
A simple alphabet-independent FM-index
An index data structure for searching in metric space databases
Dynamic entropy-compressed sequences and full-text indexes
On the least cost for proximity searching in metric spaces
Posit ion-restricted substring searching
Practical construction of k-nearest neighbor graphs in metric spaces
Reducing the space requirement of LZ-index
Statistical encoding of succinct data structures
A compact space decomposition for effective metric indexing
Bit-parallel witnesses and their applications to approximate string matching
Compressing dynamic text collections via phrase-based coding
LZgrep: a Boyer-Moore string matching tool for Ziv-Lempel compressed text
New bounds on D-ary optimal codes
New techniques for regular expression searching
Proximity searching in high dimensional spaces with a proximity preserving order
Sequential and indexed two-dimensional combinatorial template matching allowing rotations
Space-efficient construction of LZ-index
Succinct suffix arrays based on run-length encoding
Transposition invariant string matching
Advantages of backward searching - Efficient secondary memory and distributed implementation of Compressed Suffix Arrays
An alphabet-friendly FM-index
Average complexity of exact and approximate multiple string matching
Bit-parallel branch and bound algorithm for transposition invariant LCS
Compressed compact suffix arrays
First Huffman, then Burrows-Wheeler: A simple alphabet-independent FM-index
Improved single and multiple approximate string matching
Increased bit-parallelism for approximate string matching
Indexing text using the Ziv-Lempel trie
On NFA reductions
Pattern matching
Practical and flexible pattern matching over Ziv-Lempel compressed text
Probabilistic proximity searching algorithms based on compact partitions
Rotation and lighting invariant template matching
Simple, fast, and efficient natural language adaptive compression
(S,C) code for natural language text databases
(S,C)-dense coding: An optimized compression code for natural language text databases
A bit-parallel suffix automaton approach for (?,?)-matching in music retrieval
A bit-parallel suffix automaton approach for (delta, gamma)-matching in music retrieval
A practical index for genome searching
Algorithms for transposition invariant string matching (extended abstract)
An efficient compression code for text databases
Approximate matching of run-length compressed strings
Approximate regular expression searching with arbitrary integer weights
Average-optimal multiple approximate string matching
Compressing semistructured text databases
Distributed query processing using suffix arrays
Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching
Fast multipattern search algorithms for intrusion detection
Flexible and efficient bit-parallel techniques for transposition invariant approximate matching in music retrieval
Matchsimile: a flexible approximate matching tool for searching proper names
Memory-adaptative dynamic spatial approximation trees
Optimal binary search trees with costs depending on the access paths
Pivot selection techniques for proximity searching in metric spaces
Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces
SCM: Structural contexts model for improving compression in semistructured text databases
Suffix arrays in parallel
A metric index for approximate string matching
Faster bit-parallel approximate string matching
New and faster filters for multiple approximate string matching
Optimal exact and fast approximate two dimensional pattern matching allowing rotations
Searching in metric spaces by spatial approximation
XQL and proximal nodes
Fixed queries array: A fast and economical data structure for proximity searching
Improving an algorithm for approximate pattern matching
NR-grep: a fast and flexible pattern-matching tool
Searching in metric spaces
A pattern matching based filter for audit reduction and fast detection of potential intrusions
Adding compression to block addressing inverted indexes
Approximate string matching over Ziv-Lempel compressed text
Binary searching with nonuniform costs and its application to text retrieval
Block addressing indices for approximate text retrieval
Boyer-Moore string matching over Ziv-Lempel compressed text
Compression: A key for next-generation text retrieval systems
Fast and flexible word searching on compressed text
Improved approximate pattern matching on hypertext
Indexing text with approximate q-grams

ConferencePaper (85)

Optimal joins using compact data structures
LATIN 2016: Theoretical informatics 12th latin American symposium ensenada, Mexico, April 11-15, 2016 proceedings
A Compact RDF Store Using Suffix Arrays
An empirical evaluation of intrinsic dimension estimators
Document Counting in Compressed Space
Faster Compressed Quadtrees
Improved single-term top-k document retrieval
Asymptotically optimal encodings for range selection
Document Retrieval on Repetitive Collections
Dynamic List of Clusters in Secondary Memory
Efficient Compressed Indexing for Approximate Top-k String Retrieval
Efficient Indexing and Representation of Web Access Logs
Encoding data structures
Encodings for Range Majority Queries
Fast fully-compressed suffix trees
Faster Compressed Suffix Trees for Repetitive Text Collections
Grammar Compressed Sequences with Rank/Select Support
Interleaved K2-tree: Indexing and navigating ternary relations
Locally compressed suffix arrays
Ranked document selection
Top-k Term-Proximity in Succinct Space
A Lempel-Ziv Compressed Structure for Document Listing
Compact querieable representations of raster data
Compressing Huffman Models on Large Alphabets
Faster Compact Top-k Document Retrieval
Faster Top-k Document Retrieval in Optimal Space
Top-k Document Retrieval in Compact Space and Near-Optimal Time
Compressed dynamic binary relations
Compressed representation of web and social networks via dense subgraphs
Compressed suffix trees for repetitive texts
Dual-sorted inverted lists in practice
Fast, small, simple rank/select on bitmaps
Improved grammar-based compressed indexes
Indexing highly repetitive collections
New lower and upper bounds for representing sequences
Ranked document retrieval in (Almost) no space
Smaller self-indexes for natural language
Sorted range reporting
Space-efficient top-k document retrieval
The wavelet matrix
Top-k document retrieval in optimal time and linear space
Wavelet trees for all
Alphabet-independent compressed text indexing
Backwards search in context bound text transformations
Compressed string dictionaries
Improved compressed indexes for full-text document retrieval
Indexes for highly repetitive document collections
LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
Practical Compressed Document Retrieval
Self-indexing Based on LZ77
A fun application of compact data structures to indexing geographic data
A new searchable variable-to-variable compressor
Alphabet Partitioning for Compressed Rank/Select and Applications
Compact Rich-Functional Binary Relation Representations
Compressed q-gram indexing for highly repetitive biological sequences
Dual-Sorted Inverted Lists
Extended compact Web graph representations
Fast and compact prefix codes
Fast in-memory Xpath search using compressed indexes
Fully-functional succinct trees
LZ77-like compression with fast random access
Parallel and distributed compressed indexes
Practical Compressed Suffix Trees
Range queries over a compact representation of minimum bounding rectangles
Top-k ranked document search in general text databases
A compressed self-indexed representation of XML documents
A compressed text index on secondary memory
Analyzing Metric Space Indexes: What For?
Dynamic Spatial Approximation Trees for Massive Data
EGNAT: A Fully Dynamic Metric Access Method for Secondary Memory
Indexing Variable Length Substrings for Exact and Approximate Matching
An(other) entropy-bounded compressed suffix tree
Improved dynamic rank-select entropy-bound structures
Practical Rank/Select Queries over Arbitrary Sequences
Re-pair achieves high-order entropy
Speeding Up Pattern Matching by Text Sampling
A fast and compact web graph representation
A Lempel-Ziv text index on secondary storage
Compressed text indexes with fast locate
Optimal Incremental Sorting
Bit-parallel (?,?)-matching and suffix automata
Current challenges in textual databases
Improved deletions in dynamic spatial approximation trees
Practical construction of metric t-spanners
Faster approximate string matching over compressed text

Editorial (1)

Computation over compressed data

EditorialMaterial (1)

Special section on Selected Papers from SISAP 2012

Proyecto (9)

Millennium Institute for Foundational Research on Data
Compressed Data Structures for Highly Repetitive Datasets
Bioinformatics and Information Retrieval Data Structures Analysis and Design (BIRDS)
Centro Basal de Biotecnología y Bioingeniería
FUNDAMENTAL DATA STRUCTURES FOR MANAGING LARGE DATASETS
Millennium Nucleus Center Information and Coordination in Networks
COMPACT DATA STRUCTURES FOR INFORMATION RETRIEVAL
THE MONOAMINERGIC "RECEPTOPHORE". SIMILARITIES AMONG THE ACTIVE SITES OF MONOAMINERGIC TARGET PROTEINS, BASED ON THEIR CRYSTAL STRUCTURES=> IMPLICATIONS FOR THE DEVELOPMENT OF SELECTIVE AND NON-SELECTIVE LIGANDS.
MEMORY-HIERARCHY-AWARE DATA STRUCTURES

Review (2)

Compressed full-text indexes
A guided tour to approximate string matching
333
Gonzalo Navarro

FULL PROFESSOR

COMPUTER SCIENCE

UNIVERSIDAD DE CHILE

Santiago, Chile

16
Francisco Claude

Assistant Professor

Informática y Telecomunicaciones

Universidad Diego Portales

Santiago, Chile

10
Diego Arroyuelo

Full-time Professor

Departamento de Informática

UNIVERSIDAD TÉCNICA FEDERICO SANTA MARÍA

Santiago, Chile

7
Jeremy Barbay

Assistant Professor

Universidad de Chile

Santiago, Chile

3
Cecilia Hernández

Profesor Asistente

UNIVERSIDAD DE CONCEPCION

Concepción, Chile

3
Benjamin Bustos

UNIVERSIDAD DE CHILE, DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

Santiago, Chile

3
Diego Seco

Associate Professor

DIICC

Universidad de Concepción

Concepción, Chile

3
Juan Reutter

Profesor Asistente

PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE

Santiago, Chile

2
José Fuentes

Profesor asistente

Ingeniería Informática y Ciencias de la Computaciónq

Universidad de Concepción

Concepción, Chile

2
Roberto Uribe-Paredes

Académico

Ingeniería en Computación

Universidad de Magallanes

Punta Arenas, Chile

1
Francisca Munoz

Data and Computing Manager

Data and Computing

CEntro

Santiago, Chile

1
Leonardo Ferres

Research Professor

Institute of Data Science

Universidad del Desarrollo

Santiago, Chile

1
Carolina Bonacic

Investigador asociado

Informática

Universidad

santiago, Chile

1
Mauricio Marin

professor

Informatics Engineering

University of Santiago

Santiago, Chile

1
HECTOR FERRADA

Profesor

Instituto de Informática

UACh

Valdivia, Chile

1
Diego Dujovne

Associate Professor

School of Informatics and Telecommunications

UNIVERSIDAD DIEGO PORTALES

Santiago, Chile

1
Karen Oróstica

Vigilancia genómica

Genética Molecular

Universidad de Tal

Santiago, Chile

1
MARIA RODRIGUEZ

Profesor titular

Ingeniería Informática y Ciencias de la Computación

UNIVERSIDAD DE CONCEPCIÓN

Concepción, Chile

1
Ricardo Armisen

Associate Professor

Centro de Genética y Genómica

Universidad del Desarrollo

Santiago, Chile

1
José Merino

Full Professor

Sociology

UNIVERSIDAD DE CONCEPCION

Concepción, Chile

1
Marcos Kiwi

Full Professor

Ingeniería Civil Matemática

UNIVERSIDAD DE CHILE

Santiago, Chile

1
Alvaro Olivera

Principal Investigator and Assistant Professor

Chemical Engineering, Biotechnology and Materials

UNIVERSIDAD DE CHILE

Santiago, Chile

1
Sebastián Ferrada

Profesor Asistente

Universidad de Chile

Santiago, Chile