Publications

Here is a list of my publications, together with abstracts, bibtex entries and pdfs. The copyrights belong to the publishers, so the papers are offered here only for personal use on a non-commercial basis. More formally, this work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License Creative Commons License

No pdfs are given for books and some book chapters once they appear, but I may give some version of the book chapters upon request. Also, I do not guarantee that what you get is exactly what is published, especially when the system is not camera-ready but involves some editing from the publisher. I'm also starting to include, backwards, pointers to the formal publications.

There is also available code (most is free).

Along time I have discovered erratas in some papers. I have documented the fixes to these below. I have divided the erratas into small (technically incorrect statements that nevertheless do not affect at all the results), medium (those that have an impact but the main results stay correct), and serious (those that compromise the main results; fortunately they are the least).

2024 (11+4)

International journals
1. Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter, and Domagoj Vrgoc.
  Tackling Challenges in Implementing Large-Scale Graph Databases.
  To appear in Communications of the ACM [bibtex]
2. Adrián Gómez-Brandón, Gonzalo Navarro, José Paramá, Nieves Brisaboa, and Travis Gagie.
  Stronger Compact Representations of Object Trajectories.
  To appear in Geo-spatial Information Science [abstract] [bibtex] [pdf] [url]
3. Diego Arroyuelo, Benjamin Bustos, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, and Juan Reutter.
  Worst-Case-Optimal Similarity Joins on Graph Databases.
  Proceedings of the ACM on Management of Data 2(1):article 39, 2024 (SIGMOD'24 conference) [abstract] [bibtex] [pdf] [url]
4. Diego Arroyuelo, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, Juan Reutter, Javiel Rojas-Ledesma, and Adrián Soto.
  The Ring: Worst-Case Optimal Joins in Graph Databases using (Almost) No Extra Space.
  ACM Transactions on Database Systems 49(2):article 5, 2024 [abstract] [bibtex] [pdf] [url]
5. Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares.
  Near-Optimal Search Time in δ-Optimal Space, and Vice Versa.
  Algorithmica 86:1031-1056, 2024 [abstract] [bibtex] [pdf] [url]
6. Diego Arroyuelo, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, and Javiel Rojas-Ledesma.
  Optimizing RPQs over a Compact Graph Representation.
  The VLDB Journal 33:349-374, 2024 [abstract] [bibtex] [pdf] [url]
7. Nieves Brisaboa, Travis Gagie, Adrián Gómez-Brandón, and Gonzalo Navarro.
  Two-Dimensional Block Trees.
  The Computer Journal 67(1):391-406, 2024 [abstract] [bibtex] [pdf] [url]
International conferences
1. Diego Arroyuelo, Daniela Campos, Adrián Gómez-Brandón, Gonzalo Navarro, Carlos Rojas, and Domagoj Vrgoc.
  Space & Time Efficient Leapfrog Triejoin.
  To appear in Proc. GRADES-NDA'24 [abstract] [bibtex] [pdf]
2. Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Vicente Calisto, Benjamín Farías, Sebastián Ferrada, Tristan Heuer, Aidan Hogan, Gonzalo Navarro, Alexander Pinto, Juan Reutter, Henry Rosales, and Etienne Toussiant.
  MillenniumDB: A Multi-modal, Multi-model Graph Database Engine.
  To appear in Proc. SIGMOD'24 (Demo Track) [abstract] [bibtex] [pdf]
3. Zsuzsanna Lipták, Francesco Masillo, and Gonzalo Navarro.
  BAT-LZ Our of Hell.
  Proc. CPM'24, article 17 [abstract] [bibtex] [pdf]
4. Dominika Draesslerova, Omar Ahmed, Travis Gagie, Jan Holub, Benjamin Langmead, Giovanni Manzini,and Gonzalo Navarro.
  Taxonomic Classification with Maximal Exact Matches in KATKA Kernels and Minimizer Digests.
  Proc. SEA'24, article 9 [abstract] [bibtex] [pdf]
5. Adrián Goga, Lore Depuydt, Nathaniel Brown, Jan Fostier, Travis Gagie, and Gonzalo Navarro.
  Faster Maximal Exact Matches with Lazy LCP Evaluation.
  Proc. DCC'24, pages 123-132 [abstract] [bibtex] [pdf]
6. Travis Gagie, Adrián Goga, Artur Jez, and Gonzalo Navarro.
  Space-efficient Conversions from SLPs.
  Proc. LATIN'24, part I, pages 146-161 [abstract] [bibtex] [pdf] [url]
7. Andrej Baláž, Travis Gagie, Adrián Goga, Simon Heumos, Gonzalo Navarro, Alessia Petescia, and Jouni Sirén.
  Wheeler Maps.
  Proc. LATIN'24, part I, pages 178-192 [abstract] [bibtex] [pdf] [url]
8. Gonzalo Navarro and Cristian Urbina.
  Iterated Straight-Line Programs.
  Proc. LATIN'24, part I, pages 66-80 [abstract] [bibtex] [pdf] [url]

2023 (14)

International books
1. Gonzalo Navarro and Julian Shun (editors).
  Proceedings of the 25th Symposium on Algorithm Engineering and Experiments (ALENEX 2023).
  Florence, Italy, January 2023.
  SIAM. [bibtex] [url]
International journals
1. Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Diego Arroyuelo, Carlos Buil-Aranda, Aidan Hogan, Gonzalo Navarro, Cristian Riveros, and Juan Romero.
  MillenniumDB: An Open-Source Graph Database System.
  Data Intelligence 5(3):560-610, 2023 [abstract] [bibtex] [pdf] [url]
2. Diego Díaz-Domínguez and Gonzalo Navarro.
  Efficient Construction of the BWT for Repetitive Text using String Compression.
  Information and Computation 294:article 105088, 2023 [abstract] [bibtex] [pdf] [url]
3. José Fuentes-Sepúlveda, Diego Gatica, Gonzalo Navarro, Andrea Rodríguez, and Diego Seco.
  Compact Representations of Spatial Hierarchical Structures with Support for Topological Queries.
  Information and Computation 292:article 105029, 2023 [abstract] [bibtex] [pdf] [url]
4. Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.
  Towards a Definitive Compressibility Measure for Repetitive Sequences.
  IEEE Transactions on Information Theory 69(4):2074-2092, 2023 [abstract] [bibtex] [pdf] [url]
5. Nieves Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña, and Gonzalo Navarro.
  Space/time-Efficient RDF Stores based on Circular Suffix Sorting.
  The Journal of Supercomputing 79:5643-5683, 2023 [abstract] [bibtex] [pdf] [url]
6. Guillermo de Bernardo, Travis Gagie, Susana Ladra, Gonzalo Navarro, and Diego Seco.
  Faster Compressed Quadtrees.
  Journal of Computer and System Sciences 131:86-104, 2023 [abstract] [bibtex] [pdf] [url]
7. José Fuentes-Sepúlveda, Gonzalo Navarro, and Diego Seco.
  Navigating Planar Topologies in Near-Optimal Space and Time.
  Computational Geometry Theory and Applications 109:101922, 2023 [abstract] [bibtex] [pdf] [url]
International conferences
1. Diego Arroyuelo, Adrián Gómez-Brandón, and Gonzalo Navarro.
  Evaluating Regular Path Queries on Compressed Adjacency Matrices.
  Proc. SPIRE'23, pages 35-48 [abstract] [bibtex] [pdf] [url]
2. Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro, and Aaron Williams.
  Constant Time and Space Updates for the Sigma-Tau Problem.
  Proc. SPIRE'23, pages 323-330 [abstract] [bibtex] [pdf] [url]
3. Travis Gagie, Sana Kashgouli, and Gonzalo Navarro.
  A Simple Grammar-based Index for Finding Approximately Longest Common Substrings.
  Proc. SPIRE'23, pages 246-252 [abstract] [bibtex] [pdf] [url]
4. Gonzalo Navarro.
  Computing MEMs on Repetitive Text Collections.
  Proc. CPM'23, article 22 [abstract] [bibtex] [pdf] [url]
5. Gonzalo Navarro and Cristian Urbina.
  L-systems for Measuring Repetitiveness.
  Proc. CPM'23, article 14 [abstract] [bibtex] [pdf] [url]
6. Gonzalo Navarro.
  Compact Data Structures Meet Databases.
  Proc. ICDT'23, pages 2:1-2:16 [abstract] [bibtex] [pdf] [url]

2022 (16)

International books
1. Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman (editors).
  Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022).
  Postdam, Germany, September 2022.
  LIPIcs Series, volume 244 [bibtex] [contents] [url]
International journals
1. Gonzalo Navarro.
  The Compression Power of the BWT.
  Communications of the ACM 65(6):90, 2022 [bibtex] [url]
2. Paolo Ferragina, Giovanni Manzini, Travis Gagie, Dominik Köppl, Gonzalo Navarro, Manuel Striani, and Francesco Tosoni.
  Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices.
  Proceedings of the VLDB Endowment (VLDB'22 conference) 15(10):2175-2187, 2022 [abstract] [bibtex] [pdf] [url]
3. Daniel Nunes, Felipe Louza, Simon Gog, Mauricio Ayala-Rincón, and Gonzalo Navarro.
  Grammar Compression by Induced Suffix Sorting.
  ACM Journal of Experimental Algorithmics 27:article 1.1, 2022 [abstract] [bibtex] [pdf] [url]
4. Karen Y. Oróstica, Juan Saez Hidalgo, Pamela R. de Santiago, Solange Rivas, Sebastian Contreras, Gonzalo Navarro, Juan A. Asenjo, Álvaro Olivera-Nappa, and Ricardo Armisen.
  Total Mutational Load and Clinical Features as Predictors of the Metastatic Status in Lung Adenocarcinoma and Squamous Cell Carcinoma Patients.
  Journal of Translational Medicine 20:373, 2022 [abstract] [bibtex] [pdf] [url]
5. Miguel E. Coimbra, Joana Hrotkó, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, and Gonzalo Navarro.
  A Practical Succinct Dynamic Graph Representation.
  Information and Computation 285B, article 104862, 2022 [abstract] [bibtex] [pdf] [url]
6. Manuel Cáceres and Gonzalo Navarro.
  Faster Repetition-Aware Compressed Suffix Trees based on Block Trees.
  Information and Computation 285B, article 104749, 2022 [abstract] [bibtex] [pdf] [url]
7. Diego Arroyuelo, Gonzalo Navarro, Juan L. Reutter, and Javiel Rojas-Ledesma.
  Optimal Joins using Compressed Quadtrees.
  ACM Transactions on Database Systems 47(2):article 8, 2022 [abstract] [bibtex] [pdf] [url]
8. Alexandre P. Francisco, Travis Gagie, Dominik Köppl, Susana Ladra, and Gonzalo Navarro.
  Graph Compression for Adjacency-Matrix Multiplication.
  SN Computer Science 3:article 193, 2022 [abstract] [bibtex] [pdf] [url]
9. Antonio Fariña, Travis Gagie, Szymon Grabowski, Giovanni Manzini, Gonzalo Navarro, and Alberto Ordóñez.
  Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes.
  Theoretical Computer Science 907:11-25, 2022 [abstract] [bibtex] [pdf] [url]
International conferences
1. Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares.
  Near-Optimal Search Time in δ-Optimal Space.
  Proc. LATIN'22, pages 88-103 [abstract] [bibtex] [pdf] [url]
2. Gonzalo Navarro, Francisco Olivares, and Cristian Urbina.
  Balancing Run-Length Straight-Line Programs.
  Proc. SPIRE'22, pages 117-131 [abstract] [bibtex] [pdf] [url]
3. Yuma Arakawa, Gonzalo Navarro, and Kunihiko Sadakane.
  Bidirectional r-indexes.
  Proc. CPM'22, article 11 [abstract] [bibtex] [pdf] [url]
4. Diego Díaz-Domínguez and Gonzalo Navarro.
  Efficient Construction of the BWT for Repetitive Text using String Compression.
  Proc. CPM'22, article 29 [abstract] [bibtex] [pdf] [url]
5. Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, and Javiel Rojas-Ledesma.
  Time- and Space-Efficient Regular Path Queries.
  Proc. ICDE'22, pages 3091-3105 [abstract] [bibtex] [pdf] [url]
6. Dominik Köppl, Gonzalo Navarro, and Nicola Prezza.
  HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances.
  Proc. DCC'22, pages 83-92 [abstract] [bibtex] [pdf] [url]

2021 (18)

International journals
1. Diego Arroyuelo, Rodrigo Cánovas, Johannes Fischer, Dominik Köppl, Marvin Löbel, Gonzalo Navarro, and Rajeev Raman.
  Engineering Practical Lempel-Ziv Tries.
  ACM Journal of Experimental Algorithmics 26(1):article 14, 2021 [abstract] [bibtex] [pdf] [url]
2. Nieves Brisaboa, Adrián Gómez-Brandón, Travis Gagie, Gonzalo Navarro, and José Paramá.
  An Index for Moving Objects with Constant-Time Access to their Compressed Trajectories.
  International Journal of Geographical Information Science 35(7):1392-1424, 2021 [abstract] [bibtex] [pdf] [url]
3. Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.
  Range Majorities and Minorities in Arrays.
  Algorithmica 83:1707-1733, 2021 [abstract] [bibtex] [pdf] [url]
4. Gonzalo Navarro.
  Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures.
  ACM Computing Surveys 54(2): article 29, 2021 [abstract] [bibtex] [pdf] [url] [fix]
5. Gonzalo Navarro.
  Indexing Highly Repetitive String Collections, Part II: Compressed Indexes.
  ACM Computing Surveys 54(2): article 26, 2021 [abstract] [bibtex] [pdf] [url]
6. Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza.
  On the Approximation Ratio of Ordered Parsings.
  IEEE Transactions on Information Theory 67(2):1008-1026, 2021 [abstract] [bibtex] [pdf] [url]
7. Francisco Claude, Gonzalo Navarro, and Alejandro Pacheco.
  Grammar-Compressed Indexes with Logarithmic Search Time.
  Journal of Computer and System Sciences 118:53-74, 2021 [abstract] [bibtex] [pdf] [url]
8. Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro, Alberto Ordóñez, Simon J. Puglisi, and Yasuo Tabei.
  Block Trees.
  Journal of Computer and System Sciences 117:1-22, 2021 [abstract] [bibtex] [pdf] [url]
9. Felipe Glaria, Cecilia Hernandez, Susana Ladra, Gonzalo Navarro, and Lilian Salinas.
  Compact Structure for Sparse Undirected Graphs based on a Clique Graph Partition.
  Information Sciences 544, 485-499, 2021 [abstract] [bibtex] [pdf] [url]
International conferences
1. Gonzalo Navarro and Cristian Urbina.
  On Stricter Reachable Repetitiveness Measures.
  Proc. SPIRE'21, pages 193-206 [abstract] [bibtex] [pdf] [url]
2. Diego Díaz Domínguez, Gonzalo Navarro, and Alejandro Pacheco.
  An LMS-based Grammar Self-index with Local Consistency Properties.
  Proc. SPIRE'21, pages 100-113 [abstract] [bibtex] [pdf] [url]
3. Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter, Javiel Rojas-Ledesma, and Adrián Soto.
  Worst-Case Optimal Graph Joins in Almost No Space.
  Proc. SIGMOD'21, pages 102-114 [abstract] [bibtex] [pdf] [pdf additional material] [url]
4. Dustin Cobas, Travis Gagie, and Gonzalo Navarro.
  A Fast and Small Subsampled R-index.
  Proc. CPM'21, article 13 [abstract] [bibtex] [pdf] [url]
5. Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, and Massimiliano Rossi.
  PHONI: Streamed Matching Statistics with Multi-Genome References.
  Proc. DCC'21, pages 193-202 [abstract] [bibtex] [pdf] [url]
6. José Fuentes-Sepúlveda, Diego Gatica, Gonzalo Navarro, Andrea Rodríguez, and Diego Seco.
  Compact Representation of Spatial Hierarchies and Topological Relationships.
  Proc. DCC'21, pages 113-122 [abstract] [bibtex] [pdf] [url]
7. Diego Díaz-Domínguez and Gonzalo Navarro.
  A Grammar Compressor for Collections of Reads with Applications to the Construction of the BWT.
  Proc. DCC'21, pages 93-102 [abstract] [bibtex] [pdf] [url]
8. Daniela Campos, Adrián Gómez-Brandón, and Gonzalo Navarro.
  A Disk-Based Index for Trajectories with an In-Memory Compressed Cache.
  Proc. DCC'21, page 340 (poster) [abstract] [bibtex] [pdf] [url]
9. Christina Boucher, Ondrej Cvacho, Travis Gagie, Jan Holub, Giovanni Manzini, Gonzalo Navarro, and Massimiliano Rossi.
  PFP Compressed Suffix Trees.
  Proc. ALENEX'21, pages 60-72 [abstract] [bibtex] [pdf] [url]

2020 (21)

Journal special issues
1. Virgilio Almeida, Gonzalo Navarro, and Sergio Rajsbaum (editors).
  Latin America Regional Special Section.
  Communications of the ACM 63(11):42-107, 2020 [bibtex] [url]
2. Travis Gagie and Gonzalo Navarro (editors).
  Special Issue on Computation over Compressed Data.
  Information and Computation 273, 2020 [bibtex] [url]
International journals
1. Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.
  Optimal-Time Dictionary-Compressed Indexes.
  ACM Transactions on Algorithms 17(1):article 8, 2020 [abstract] [bibtex] [pdf] [url]
2. Daniel Valenzuela, Dmitry Kosolobov, Gonzalo Navarro, and Simon J. Puglisi.
  Lempel-Ziv-like Parsing in Small Space.
  Algorithmica 82(11):3195-3215, 2020 [abstract] [bibtex] [pdf] [url]
3. Gonzalo Navarro and Javiel Rojas-Ledesma.
  Predecessor Search.
  ACM Computing Surveys 53(5):article 105, 2020 [abstract] [bibtex] [pdf] [url]
4. Travis Gagie, Meng He, Gonzalo Navarro, and Carlos Ochoa.
  Tree Path Majority Data Structures.
  Theoretical Computer Science 833:107-119, 2020 [abstract] [bibtex] [pdf] [url]
5. Travis Gagie, Meng He, and Gonzalo Navarro.
  Compressed Dynamic Range Majority and Minority Data Structures.
  Algorithmica 82(7):2063-2086, 2020 [abstract] [bibtex] [pdf] [url]
6. Leo Ferres, José Fuentes-Sepúlveda, Travis Gagie, Meng He, and Gonzalo Navarro.
  Fast and Compact Planar Embeddings.
  Computational Geometry Theory and Applications 89, article 101630, 2020 [abstract] [bibtex] [pdf] [url]
7. Ian Munro, Gonzalo Navarro, Rahul Shah, and Sharma Thankachan.
  Ranked Document Selection.
  Theoretical Computer Science 812:149-159, 2020 [abstract] [bibtex] [pdf] [url]
8. José Fuentes-Sepúlveda, Gonzalo Navarro, and Yakov Nekrich.
  Parallel Computation of the Burrows Wheeler Transform in Compact Space.
  Theoretical Computer Science 812:123-136, 2020 [abstract] [bibtex] [pdf] [url]
9. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.
  Fast Compressed Self-Indexes with Deterministic Linear-Time Construction.
  Algorithmica 82(2):316-337, 2020 [abstract] [bibtex] [pdf] [url]
10. Travis Gagie, Gonzalo Navarro, and Nicola Prezza.
  Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space.
  Journal of the ACM 67(1):article 2, 2020 [abstract] [bibtex] [pdf] [url]
11. Nieves Brisaboa, Ana Cerdeira, Guillermo de Bernardo, Gonzalo Navarro, and Oscar Pedreira.
  Extending General Compact Querieable Representations to GIS Applications.
  Information Sciences 506:196-216, 2020 [abstract] [bibtex] [pdf] [url]
International conferences
1. Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.
  Towards a Definitive Measure of Repetitiveness.
  Proc. LATIN'20, pages 207-219. LNCS 12118 [abstract] [bibtex] [pdf] [url]
2. Gonzalo Navarro.
  Contextual Pattern Matching.
  Proc. SPIRE'20, article 1. LNCS 12303 [abstract] [bibtex] [pdf] [fix] [url]
3. Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Louisa Seelbach Benkner, and Yoshimasa Takabatake.
  Practical Random Access to SLP-Compressed Texts.
  Proc. SPIRE'20, article 16. LNCS 12303 [abstract] [bibtex] [pdf] [url]
4. J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.
  Text Indexing and Searching in Sublinear Time.
  Proc. CPM'20, article 24 [abstract] [bibtex] [pdf] [url]
5. Luís Russo, Ana Correia, Gonzalo Navarro, and Alexandre Francisco.
  Approximating Optimal Bidirectional Macro Schemes.
  Proc. DCC'20, pages 153-162 [abstract] [bibtex] [pdf] [url]
6. Miguel Coimbra, Alexandre Francisco, Luís Russo, Guillermo de Bernardo, Susana Ladra, and Gonzalo Navarro.
  On Dynamic Succinct Graph Representations.
  Proc. DCC'20, pages 213-222 [abstract] [bibtex] [pdf] [url]
7. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and Tirso Rodeiro.
  Semantrix: A Compressed Semantic Matrix.
  Proc. DCC'20, pages 113-122 [abstract] [bibtex] [pdf] [url]
8. Gonzalo Navarro, Juan Reutter, and Javiel Rojas-Ledesma.
  Optimal Joins using Compact Data Structures.
  Proc. ICDT'20, pages 21:1-21:21. [abstract] [bibtex] [pdf] [url]

2019 (21)

International book chapters
1. Travis Gagie and Gonzalo Navarro.
  Compressed Indexes for Repetitive Textual Datasets.
  In Encyclopedia of Big Data Technologies, 2019. Springer. [bibtex] [url]
International journals
1. Gonzalo Navarro, Víctor Sepúlveda, Mauricio Marín, and Senén González.
  Compressed Filesystem for Managing Large Genome Collections.
  Bioinformatics 35(20):4120-4128, 2019 [abstract] [bibtex] [pdf] [url]
2. Carlos Ochoa and Gonzalo Navarro.
  RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy.
  IEEE Transactions on Information Theory 65(5):3160-3164, 2019 [abstract] [bibtex] [pdf] [url]
3. Gonzalo Navarro.
  Document Listing on Repetitive Collections with Guaranteed Performance.
  Theoretical Computer Science 777:58-72, 2019 [abstract] [bibtex] [pdf] [url] [fix]
4. Travis Gagie, Meng He, and Gonzalo Navarro.
  Path Queries on Functions.
  Theoretical Computer Science 770:34-50, 2019 [abstract] [bibtex] [pdf] [url]
5. Antonio Fariña, Miguel Martínez-Prieto, Francisco Claude, Gonzalo Navarro, Juan Lastra-Díaz, Nicola Prezza, and Diego Seco.
  On the Reproducibility of Experiments of Indexing Repetitive Document Collections.
  Information Systems 83:181-194, 2019 [abstract] [bibtex] [pdf] [url]
6. Daniel Inostroza, Cecilia Hernández, Diego Seco, Gonzalo Navarro, and Alvaro Olivera.
  Cell Cycle and Protein Complex Dynamics in Discovering Signaling Pathways.
  Journal of Bioinformatics and Computational Biology 17(3):1950011, 2019 [abstract] [bibtex] [pdf] [url]
7. Héctor Ferrada and Gonzalo Navarro.
  Lempel-Ziv Compressed Structures for Document Retrieval.
  Information and Computation 265:1-25, 2019 [abstract] [bibtex] [pdf] [url]
8. Gonzalo Navarro and Nicola Prezza.
  Universal Compressed Text Indexing.
  Theoretical Computer Science 762:41-50, 2019 [abstract] [bibtex] [pdf] [url]
9. Nieves Brisaboa, Adrián Gómez-Brandón, Gonzalo Navarro, and José Paramá.
  GraCT: A Grammar-based Compressed Index for Trajectory Data.
  Information Sciences 483:106-135, 2019 [abstract] [bibtex] [pdf] [url]
International conferences
1. Nieves Brisaboa, Ana Cerdeira, Guillermo de Bernardo, and Gonzalo Navarro.
  Improved Compressed String Dictionaries.
  Proc. CIKM'19, pages 29-38 [abstract] [bibtex] [pdf] [url]
2. Manuel Cáceres and Gonzalo Navarro.
  Faster Repetition-Aware Compressed Suffix Trees based on Block Trees.
  Proc. SPIRE'19, pages 434-451. LNCS 11811 [abstract] [bibtex] [pdf] [url]
3. Dustin Cobas and Gonzalo Navarro.
  Fast, Small, and Simple Document Listing on Repetitive Text Collections.
  Proc. SPIRE'19, pages 482-498. LNCS 11811 [abstract] [bibtex] [pdf] [url]
4. José Fuentes, Gonzalo Navarro, and Diego Seco.
  Implementing the Topological Model Succinctly.
  Proc. SPIRE'19, pages 499-512. LNCS 11811 [abstract] [bibtex] [pdf] [url]
5. Diego Arroyuelo, Guillermo de Bernardo, Travis Gagie, and Gonzalo Navarro.
  Faster Dynamic Compressed d-ary Relations.
  Proc. SPIRE'19, pages 419-433, LNCS 11811 [abstract] [bibtex] [pdf] [url]
6. Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, and Yoshimasa Takabatake.
  Rpair: Scaling up RePair with Rsync.
  Proc. SPIRE'19, pages 35-44, LNCS 11811 [abstract] [bibtex] [pdf] [url]
7. Diego Díaz-Domínguez, Travis Gagie, and Gonzalo Navarro.
  Simulating the DNA Overlap Graph in Succinct Space.
  Proc. CPM'19, pages 27:1-27:20 [abstract] [bibtex] [pdf] [url]
8. Gonzalo Navarro and Víctor Sepúlveda.
  Practical Indexing of Repetitive Collections using Relative Lempel-Ziv.
  Proc. DCC'19, pages 201-210 [abstract] [bibtex] [pdf] [url] [fix]
9. Jarno Alanko, Travis Gagie, Gonzalo Navarro, and Louisa Seelbach Benkner.
  Tunneling on Wheeler Graphs.
  Proc. DCC'19, pages 122-131 [abstract] [bibtex] [pdf] [url]
10. José Fuentes-Sepúlveda, Gonzalo Navarro, and Yakov Nekrich.
  Space-Efficient Computation of the Burrows-Wheeler Transform.
  Proc. DCC'19, pages 132-141 [abstract] [bibtex] [pdf] [url]
11. Nieves Brisaboa, Antonio Fariña, Adrián Gómez-Brandón, Gonzalo Navarro, and Tirso Rodeiro.
  Dv2v: A Dynamic Variable-to-Variable Compressor.
  Proc. DCC'19, pages 83-92 [abstract] [bibtex] [pdf] [url]

2018 (14)

International books
1. Travis Gagie, Alistair Moffat, Gonzalo Navarro, and Ernesto Cuadros (editors).
  Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018).
  Lima, Peru, October 2018.
  LNCS Series, vol. 11147. [bibtex] [contents] [url]
2. Gonzalo Navarro, David Sankoff, and Binhai Zhu (editors).
  Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018).
  Qingdao, China, July 2018.
  LIPIcs Series, vol. 105 [bibtex] [contents] [url]
International book chapters
1. Nieves Brisboa, Ana Cerdeira, and Gonzalo Navarro.
  Managing Compressed Structured Text.
  In Encyclopedia of Database Systems, 2nd edition, 2018. Springer. [bibtex] [url]
2. Roberto Konow and Gonzalo Navarro.
  Text Index Compression.
  In Encyclopedia of Database Systems, 2nd edition, 2018. Springer. [bibtex] [url]
Journal special issues
1. Travis Gagie and Gonzalo Navarro (editors).
  Special Issue on Compact Data Structures.
  Algorithmica 80(7), 2018 [bibtex] [url]
2. Evangelos Kranakis and Gonzalo Navarro (editors).
  Special Issue on Selected Papers from LATIN 2016.
  Algorithmica 80(3), 2018 [bibtex] [url]
International journals
1. Andrea Farruggia, Travis Gagie, Gonzalo Navarro, Simon J. Puglisi, and Jouni Sirén.
  Relative Suffix Trees.
  The Computer Journal 61(5), 773-788, 2018 [abstract] [bibtex] [pdf] [url]
International conferences
1. Travis Gagie, Meng He, and Gonzalo Navarro.
  Tree Path Majority Data Structures.
  Proc. ISAAC'18, article 68, LIPICs 123 [abstract] [bibtex] [pdf] [url]
2. Travis Gagie, Gonzalo Navarro, and Nicola Prezza.
  On the Approximation Ratio of Lempel-Ziv Parsing.
  Proc. LATIN'18, pages 490-503, LNCS 10807 [abstract] [bibtex] [pdf] [url]
3. Alexandre Francisco, Travis Gagie, Susana Ladra, and Gonzalo Navarro.
  Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication.
  Proc. DCC'18, pages 309-316 [abstract] [bibtex] [pdf] [url]
4. Daniel Nunes, Felipe Louza, Simon Gog, Mauricio Ayala-Rincón, and Gonzalo Navarro.
  A Grammar Compression Algorithm based on Induced Suffix Sorting.
  Proc. DCC'18, pages 42-51 [abstract] [bibtex] [pdf] [url]
5. Nieves Brisaboa, Guillermo de Bernardo, Gonzalo Navarro, Tirso Rodeiro, and Diego Seco.
  Compact Representation of Event Sequences.
  Proc. DCC'18, pages 239-248 [abstract] [bibtex] [pdf] [url]
6. Nieves Brisaboa, Travis Gagie, Adrián Gómez-Brandón and Gonzalo Navarro.
  Two-Dimensional Block Trees.
  Proc. DCC'18, pages 229-238 [abstract] [bibtex] [pdf] [url]
7. Travis Gagie, Gonzalo Navarro, and Nicola Prezza.
  Optimal-Time Text Indexing in BWT-runs Bounded Space.
  Proc. SODA'18, pages 1459-1477 [abstract] [bibtex] [pdf] [url] [fix]

2017 (21)

International journals
1. Cecilia Hernandez, Carlos Mella, Gonzalo Navarro, Alvaro Olivera-Napa, and Jaime Araya.
  Protein Complex Prediction via Dense Subgraphs and False Positive Analysis.
  Plos ONE 12(9):e0183460, 2017 [abstract] [bibtex] [pdf] [url]
2. Nieves Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, and Gonzalo Navarro.
  Compressed Representation of Dynamic Binary Relations with Applications.
  Information Systems 69:106-123, 2017 [abstract] [bibtex] [pdf] [url]
3. Travis Gagie, Aleksi Hartikainen, Kalle Karhu, Juha Kärkkäinen, Gonzalo Navarro, Simon J. Puglisi, and Jouni Sirén.
  Document Retrieval on Repetitive Collections.
  Information Retrieval 20:253-291, 2017 [abstract] [bibtex] [pdf] [url]
4. Ian Munro, Gonzalo Navarro, Jesper Sindahl Nielsen, Rahul Shah, and Sharma Thankachan.
  Top-k Term-Proximity in Succinct Space.
  Algorithmica 78(2):379-393, 2017 [abstract] [bibtex] [pdf] [url]
5. Sandra Alvarez-Garcia, Guillermo de Bernardo, Nieves Brisaboa, and Gonzalo Navarro.
  A Succinct Data Structure for Self-indexing Ternary Relations.
  Journal of Discrete Algorithms 43:38-53, 2017 [abstract] [bibtex] [pdf] [url]
6. Alberto Ordóñez, Gonzalo Navarro, and Nieves Brisaboa.
  Grammar Compressed Sequences with Rank/Select Support.
  Journal of Discrete Algorithms 43:54-71, 2017 [abstract] [bibtex] [pdf] [url]
7. Héctor Ferrada and Gonzalo Navarro.
  Improved Range Minimum Queries.
  Journal of Discrete Algorithms 43:72-80, 2017 [abstract] [bibtex] [pdf] [url]
8. Simon Gog, Roberto Konow, and Gonzalo Navarro.
  Practical Compact Indexes for Top-k Document Retrieval.
  ACM Journal of Experimental Algorithmics 22(1):article 1.2, 2017 [abstract] [bibtex] [pdf] [url]
9. Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Rao Satti.
  Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries.
  ACM Transactions on Algorithms 13(2):article 28, 2017 [abstract] [bibtex] [pdf] [url]
10. Gonzalo Navarro and Yakov Nekrich.
  Time-Optimal Top-k Document Retrieval.
  SIAM Journal on Computing 46(1):89-113, 2017 [abstract] [bibtex] [pdf] [url]
11. Gonzalo Navarro, Rodrigo Paredes, Nora Reyes, and Cristian Bustos.
  An Empirical Evaluation of Intrinsic Dimension Estimators.
  Information Systems 64:206-218, 2017 [abstract] [bibtex] [pdf] [url]
12. Roberto Konow, Gonzalo Navarro, Charles Clarke, and Alejandro López-Ortíz.
  Inverted Treaps.
  ACM Transactions on Information Systems 35(3):article 22, 2017 [abstract] [bibtex] [pdf] [url]
International conferences
1. Gonzalo Navarro.
  A Self-Index on Block Trees.
  Proc. SPIRE'17, pages 278-289. LNCS 10508 [abstract] [bibtex] [pdf] [url] [fix]
2. Diego Arroyuelo, Rodrigo Canovas, Gonzalo Navarro, and Rajeev Raman.
  LZ78 Compression in Low Main Memory Space.
  Proc. SPIRE'17, pages 38-50. LNCS 10508 [abstract] [bibtex] [pdf] [url] [fix]
3. Nieves Brisaboa, Travis Gagie, Adrián Gómez-Brandón, Gonzalo Navarro, and Jose Parama
  Efficient Compression and Indexing of Trajectories.
  Proc. SPIRE'17, pages 103-115. LNCS 10508 [abstract] [bibtex] [pdf] [url]
4. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.
  Fast Compressed Self-Indexes with Deterministic Linear-Time Construction.
  Proc. ISAAC'17, article 57. LIPIcs 92 [abstract] [bibtex] [pdf] [url]
5. Gonzalo Navarro.
  Document Listing on Repetitive Collections with Guaranteed Performance.
  Proc. CPM'17, article 4. LIPIcs 78 [abstract] [bibtex] [pdf] [url]
6. Travis Gagie, Meng He, and Gonzalo Navarro.
  Path Queries on Functions.
  Proc. CPM'17, article 5. LIPIcs 78. [abstract] [bibtex] [pdf] [url]
7. Leo Ferres, José Fuentes, Travis Gagie, Meng He, and Gonzalo Navarro.
  Fast and Compact Planar Embeddings.
  Proc. WADS'17, pages 385-396. LNCS 10387 [abstract] [bibtex] [pdf] [url]
8. Travis Gagie, Meng He, and Gonzalo Navarro.
  Compressed Dynamic Range Majority Data Structures.
  Proc. DCC'17, pages 260-269 [abstract] [bibtex] [pdf] [url]
9. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.
  Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time.
  Proc. SODA'17, pages 408-424 [abstract] [bibtex] [pdf] [url] [fix]

2016 (19)

International books
1. Gonzalo Navarro.
  Compact Data Structures -- A practical approach.
  Cambridge University Press, 570 pages, 2016 [web page] [bibtex] [url]
2. Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez (editors).
  Proceedings of the 12th Latin American Symposium on Theoretical Informatics (LATIN 2016).
  Ensenada, Mexico, April 2016.
  Springer-Verlag LNCS Series, vol. 9644 [bibtex] [contents] [url]
International book chapters
1. Gonzalo Navarro and Kunihiko Sadakane.
  Compressed Tree Representations.
  In M. Kao (editor), Encyclopedia of Algorithms, 2nd edition, pages 397-401, 2016. Springer. [bibtex] [url]
2. Gonzalo Navarro.
  Approximate String Matching.
  In M. Kao (editor), Encyclopedia of Algorithms, 2nd edition, pages 102-106, 2016. Springer. [bibtex] [url]
3. Gonzalo Navarro.
  Approximate Regular Expression Matching.
  In M. Kao (editor), Encyclopedia of Algorithms, 2nd edition, pages 99-102, 2016. Springer. [bibtex] [url]
4. Veli Mäkinen and Gonzalo Navarro.
  Compressed Text Indexing.
  In M. Kao (editor), Encyclopedia of Algorithms, 2nd edition, pages 394-397, 2016. Springer. [bibtex] [url]
International journals
1. Joshimar Córdova and Gonzalo Navarro.
  Simple and Efficient Fully-Functional Succinct Trees.
  Theoretical Computer Science 656PB:135-145, 2016 [abstract] [bibtex] [pdf] [url]
2. Gonzalo Navarro and Sharma Thankachan.
  Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  Theoretical Computer Science 638:108-111, 2016 [abstract] [bibtex] [pdf] [url]
3. Gonzalo Navarro and Nora Reyes.
  New Dynamic Metric Indices for Secondary Memory.
  Information Systems 59:48-78, 2016 [abstract] [bibtex] [pdf] [url]
4. Francisco Claude, Antonio Fariña, Miguel A. Martínez, and Gonzalo Navarro.
  Universal Indexes for Highly Repetitive Document Collections.
  Information Systems 61:1-23, 2016 [abstract] [bibtex] [pdf] [url]
5. Nieves Brisaboa, Guillermo de Bernardo, Roberto Konow, Gonzalo Navarro, and Diego Seco.
  Aggregated 2D Range Queries on Clustered Points.
  Information Systems 60:34-49, 2016 [abstract] [bibtex] [pdf] [url]
6. Gonzalo Navarro and Sharma Thankachan.
  Optimal Encodings for Range Majority Queries.
  Algorithmica 74(3):1082-1098, 2016 [abstract] [bibtex] [pdf] [url] [fix]
7. Gonzalo Navarro and Alberto Ordóñez.
  Faster Compressed Suffix Trees for Repetitive Collections.
  ACM Journal of Experimental Algorithmics 21(1):article 1.8, 2016 [abstract] [bibtex] [pdf] [url]
8. Miguel A. Martínez-Prieto, Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, and Gonzalo Navarro.
  Practical Compressed String Dictionaries.
  Information Systems 56:73-108, 2016 [abstract] [bibtex] [pdf] [url]
International conferences
1. Antonio Fariña, Travis Gagie, Giovanni Manzini, Gonzalo Navarro, and Alberto Ordóñez.
  Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes.
  In Proc. SPIRE'16, pages 50-60. LNCS 9954 [abstract] [bibtex] [pdf] [url]
2. Nieves Brisaboa, Ana Cerdeira-Pena, Narciso López-López, Gonzalo Navarro, Miguel Penabad, and Fernando Silva-Coira.
  Efficient Representation of Multidimensional Data over Hierarchical Domains.
  In Proc. SPIRE'16, pages 191-203. LNCS 9954 [abstract] [bibtex] [pdf] [url]
3. Nieves Brisaboa, Adrián Gómez-Brandón, Gonzalo Navarro, and José Paramá.
  GraCT: A Grammar based Compressed Representation of Trajectories.
  In Proc. SPIRE'16, pages 218-230. LNCS 9954 [abstract] [bibtex] [pdf] [url]
4. Joshimar Córdova and Gonzalo Navarro.
  Practical Dynamic Entropy-Compressed Bitvectors with Applications.
  Proc. SEA'16, pages 105-117. LNCS 9685 [abstract] [bibtex] [pdf] [url]
5. Héctor Ferrada and Gonzalo Navarro.
  Improved Range Minimum Queries.
  Proc. DCC'16, pages 516-525 [abstract] [bibtex] [pdf] [url]

2015 (16)

International journals
1. Travis Gagie, Gonzalo Navarro, Yakov Nekrich, and Alberto Ordóñez.
  Efficient and Compact Representations of Prefix Codes.
  IEEE Transactions on Information Theory 61(9):4999-5011, 2015 [abstract] [bibtex] [pdf] [url]
2. Sandra Álvarez-García, Nieves Brisaboa, Javier Fernández, Miguel Martínez-Prieto, and Gonzalo Navarro.
  Compressed Vertical Partitioning for Efficient RDF Management.
  Knowledge and Information Systems 44(2):439-474, 2015 [abstract] [bibtex] [pdf] [url]
3. Djamal Belazzougui and Gonzalo Navarro.
  Optimal Lower and Upper Bounds for Representing Sequences.
  ACM Transactions on Algorithms 11(4):article 31, 2015 [abstract] [bibtex] [pdf] [url]
4. Simon Gog, Gonzalo Navarro, and Matthias Petri.
  Improved and Extended Locating Functionality on Compressed Suffix Arrays.
  Journal of Discrete Algorithms 32:53-63, 2015 [abstract] [bibtex] [pdf] [url]
5. Gonzalo Navarro and Sharma Thankachan.
  Bottom-k Document Retrieval.
  Journal of Discrete Algorithms 32:69-74, 2015 [abstract] [bibtex] [pdf] [url]
6. Edgar Chávez, Mario Graff, Gonzalo Navarro, and Eric Sadit Téllez.
  Near Neighbor Searching with K Nearest References.
  Information Systems 51:43-61, 2015 [abstract] [bibtex] [pdf] [url]
7. Young-Hwan Kim, Roberto Konow, Diego Dujovne, Thierry Turletti, Walid Dabbous, and Gonzalo Navarro.
  PcapWT: An Efficient Packet Extraction Tool for Large Volume Network Traces.
  Computer Networks 79:91-102, 2015 [abstract] [bibtex] [pdf] [url]
8. Diego Arroyuelo, Francisco Claude, Sebastian Maneth, Veli Mäkinen, Gonzalo Navarro, Kim Nguyễn, Jouni Sirén, and Niko Välimäki.
  Fast In-Memory XPath Search using Compressed Indexes.
  Software Practice and Experience 45(3):399-434, 2015 [abstract] [bibtex] [pdf] [url]
9. Cristobal Navarro, Fabrizio Canfora, Nancy Hitschfeld, and Gonzalo Navarro.
  Parallel Family Trees for Transfer Matrices in the Potts Model.
  Computer Physics Communications 187:55-71, 2015 [abstract] [bibtex] [pdf] [url]
10. Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez.
  The Wavelet Matrix: An Efficient Wavelet Tree for Large Alphabets.
  Information Systems 47:15-32, 2015 [abstract] [bibtex] [pdf] [url] [fix]
International conferences
1. Cristian Bustos, Gonzalo Navarro, Nora Reyes, and Rodrigo Paredes.
  An Empirical Evaluation of Intrinsic Dimensionality Estimators.
  Proc. SISAP'15, pages 125-137. LNCS 9371. [abstract] [bibtex] [pdf] [url]
2. Nieves Brisaboa, Ana Cerdeira, Antonio Fariña, and Gonzalo Navarro.
  A Compact RDF Store using Suffix Arrays.
  Proc. SPIRE'15, pages 103-115. LNCS 9309. [abstract] [bibtex] [pdf] [url]
3. Gonzalo Navarro and Sharma Thankachan.
  Reporting Consecutive Substring Occurrences under Bounded Gap Constraints.
  Proc. CPM'15, pages 367-373. LNCS 9133 [abstract] [bibtex] [pdf] [url]
4. Travis Gagie, Aleksi Hartikainen, Juha Kärkkäinen, Gonzalo Navarro, Simon Puglisi, and Jouni Sirén.
  Document Counting in Compressed Space.
  Proc. DCC'15, pages 103-112 [abstract] [bibtex] [pdf] [url]
5. Travis Gagie, Javier González-Nova, Susana Ladra, Gonzalo Navarro, and Diego Seco.
  Faster Compressed Quadtrees.
  Proc. DCC'15, pages 93-102 [abstract] [bibtex] [pdf] [url]
6. Simon Gog and Gonzalo Navarro.
  Improved Single-Term Top-k Document Retrieval.
  Proc. ALENEX'15, pages 24-32 [abstract] [bibtex] [pdf] [url]

2014 (31)

Journal special issues
1. Gonzalo Navarro and Vladimir Pestov (editors).
  Special Issue on Selected Papers from SISAP 2012.
  Information Systems 45:35-68, 2014. [bibtex] [url]
International journals
1. Gonzalo Navarro, Simon Puglisi, and Daniel Valenzuela.
  General Document Retrieval in Compact Space.
  ACM Journal of Experimental Algorihtmics 19(2):article 3, 2014 [abstract] [bibtex] [pdf] [url]
2. Gonzalo Navarro and Yakov Nekrich.
  Optimal Dynamic Sequence Representations.
  SIAM Journal on Computing 43(5):1781--1806, 2014 [abstract] [bibtex] [pdf] [url]
3. Diego Arroyuelo, Carolina Bonacic, Veronica Gil-Costa, Mauricio Marin, and Gonzalo Navarro.
  Distributed Text Search using Suffix Arrays.
  Parallel Computing 40(9):471-495, 2014 [abstract] [bibtex] [pdf] [url]
4. Djamal Belazzougui and Gonzalo Navarro.
  Alphabet-Independent Compressed Text Indexing.
  ACM Transactions on Algorithms 10(4):article 23, 2014 [abstract] [bibtex] [pdf] [url]
5. Gonzalo Navarro and Sharma Thankachan.
  New Space/Time Tradeoffs for Top-k Document Retrieval on Sequences.
  Theoretical Computer Science 542:83-97, 2014 [abstract] [bibtex] [pdf] [url]
6. Nieves Brisaboa, Ana Cerdeira-Pena, and Gonzalo Navarro.
  XXS: Efficient XPath Evaluation on Compressed XML Documents.
  ACM Transactions on Information Systems 32(3):article 13, 2014 [abstract] [bibtex] [pdf] [url]
7. Cecilia Hernández and Gonzalo Navarro.
  Compressed Representations for Web and Social Graphs.
  Knowledge and Information Systems 40(2):279-313, 2014 [abstract] [bibtex] [pdf] [url] [fix]
8. Jérémy Barbay, Timothy Chan, Gonzalo Navarro, and Pablo Pérez-Lantero.
  Maximum-Weight Planar Boxes in O(n^2) Time (and Better).
  Information Processing Letters 114(8):437-445, 2014 [abstract] [bibtex] [pdf] [url]
9. Rodrigo González, Gonzalo Navarro, and Héctor Ferrada.
  Locally Compressed Suffix Arrays.
  ACM Journal of Experimental Algorithmics 19(1):article 1, 2014 [abstract] [bibtex] [pdf] [url] [fix]
10. Gonzalo Navarro and Kunihiko Sadakane.
  Fully-Functional Static and Dynamic Succinct Trees.
  ACM Transactions on Algorithms 10(3):article 16, 2014 [abstract] [bibtex] [pdf] [url] [fix]
11. Pooya Davoodi, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.
  Encoding Range Minima and Range Top-2 Queries.
  Philosophical Transactions of the Royal Society A 372:20130131, 2014 [abstract] [bibtex] [pdf] [url]
12. Gonzalo Navarro.
  Spaces, Trees and Colors: The Algorithmic Landscape of Document Retrieval on Sequences.
  ACM Computing Surveys 46(4):article 52, 2014 [abstract] [bibtex] [pdf] [url]
13. Jérémy Barbay, Francisco Claude, Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.
  Efficient Fully-Compressed Sequence Representations.
  Algorithmica 69(1):232-268, 2014 [abstract] [bibtex] [pdf] [url]
14. Gonzalo Navarro.
  Wavelet Trees for All.
  Journal of Discrete Algorithms 25:2-20, 2014 [abstract] [bibtex] [pdf] [url] [fix]
15. Nieves Brisaboa, Susana Ladra, and Gonzalo Navarro.
  Compact Representation of Web Graphs with Extended Functionality.
  Information Systems 39(1):152-174, 2014 [abstract] [bibtex] [pdf] [url]
16. Arash Farzan, Travis Gagie, and Gonzalo Navarro.
  Entropy-Bounded Representation of Point Grids.
  Computational Geometry: Theory and Applications 47(1):1-14, 2014 [abstract] [bibtex] [pdf] [url]
International conferences
1. Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.
  Asymptotically Optimal Encodings for Range Selection.
  Proc. FSTTCS'14, pages 291-302 [abstract] [bibtex] [pdf] [url]
2. Ian Munro, Gonzalo Navarro, Jesper Sindahl Nielsen, Rahul Shah, and Sharma Thankachan.
  Top-k Term-Proximity in Succinct Space.
  Proc. ISAAC'14, pages 169-180. LNCS 8889 [abstract] [bibtex] [pdf] [url]
3. Gonzalo Navarro and Nora Reyes.
  Dynamic List of Clusters in Secondary Memory.
  Proc. SISAP'14, pages 94-105. LNCS 8821 [abstract] [bibtex] [pdf] [url]
4. Gonzalo Navarro and Alberto Ordóñez.
  Grammar Compressed Sequences with Rank/Select Support.
  Proc. SPIRE'14, pages 31-44. LNCS 8799 [abstract] [bibtex] [pdf] [url]
5. Nieves Brisaboa, Guillermo de Bernardo, Roberto Konow, and Gonzalo Navarro.
  K^2-Treaps: Range Top-k Queries in Compact Space.
  Proc. SPIRE'14, pages 215-226. LNCS 8799 [abstract] [bibtex] [pdf] [url]
6. Héctor Ferrada and Gonzalo Navarro.
  Efficient Compressed Indexing for Approximate Top-k String Retrieval.
  Proc. SPIRE'14, pages 18-30. LNCS 8799 [abstract] [bibtex] [pdf] [url]
7. Francisco Claude, Roberto Konow, and Gonzalo Navarro.
  Efficient Indexing and Representation of Web Access Logs.
  Proc. SPIRE'14, pages 65-76. LNCS 8799 [abstract] [bibtex] [pdf] [url]
8. Gonzalo Navarro, Simon Puglisi, and Jouni Sirén.
  Document Retrieval on Repetitive Collections.
  Proc. ESA'14, pages 725-736. LNCS 8737 [abstract] [bibtex] [pdf] [url]
9. Ian Munro, Gonzalo Navarro, Rahul Shah, and Sharma Thankachan.
  Ranked Document Selection.
  Proc. SWAT'14, pages 344-356. LNCS 8503 [abstract] [bibtex] [pdf] [url]
10. Simon Gog and Gonzalo Navarro.
  Improved and Extended Locating Functionality on Compressed Suffix Arrays.
  Proc. SEA'14, pages 436-447. LNCS 8504 [abstract] [bibtex] [pdf] [url]
11. Gonzalo Navarro and Alberto Ordóñez.
  Faster Compressed Suffix Trees for Repetitive Text Collections.
  Proc. SEA'14, pages 424-435. LNCS 8504 [abstract] [bibtex] [pdf] [url]
12. Gonzalo Navarro and Sharma V. Thankachan.
  Encodings for Range Majority Queries.
  Proc. CPM'14, pages 262-272. LNCS 8486 [abstract] [bibtex] [pdf] [url]
13. Gonzalo Navarro and Luís Russo.
  Fast Fully-Compressed Suffix Trees.
  Proc. DCC'14, pages 283-291 [abstract] [bibtex] [pdf] [url]
14. Sandra Álvarez-García, Nieves Brisaboa, Guillermo de Bernardo, and Gonzalo Navarro.
  Interleaved K2-tree: Indexing and Navigating Ternary Relations.
  Proc. DCC'14, pages 342-351 [abstract] [bibtex] [pdf] [url]

2013 (22)

International journals
1. Jérémy Barbay and Gonzalo Navarro.
  On Compressing Permutations and Adaptive Sorting.
  Theoretical Computer Science 513:109-123, 2013 [abstract] [bibtex] [pdf] [url]
2. Jérémy Barbay, Francisco Claude, and Gonzalo Navarro.
  Compact Binary Relation Representations with Rich Functionality.
  Information and Computation 232:19-37, 2013 [abstract] [bibtex] [pdf] [url]
3. Andrés Abeliuk, Rodrigo Cánovas, and Gonzalo Navarro.
  Practical Compressed Suffix Trees.
  Algorithms 6(2):319-351, 2013 [abstract] [bibtex] [pdf] [url] [fix]
4. Eric Sadit Tellez, Edgar Chavez, and Gonzalo Navarro.
  Succinct Nearest Neighbor Search.
  Information Systems 38(7):1019-1030, 2013 [abstract] [bibtex] [pdf] [url]
5. Travis Gagie, Juha Kärkkäinen, Gonzalo Navarro, and Simon Puglisi.
  Colored Range Queries and Document Retrieval.
  Theoretical Computer Science 483:36-50, 2013 [abstract] [bibtex] [pdf] [url]
6. Sebastian Kreft and Gonzalo Navarro.
  On Compressing and Indexing Repetitive Sequences.
  Theoretical Computer Science 483:115-133, 2013 [abstract] [bibtex] [pdf] [url]
7. Gonzalo Navarro, Yakov Nekrich, and Luís Russo.
  Space-Efficient Data-Analysis Queries on Grids.
  Theoretical Computer Science 482:60-72, 2013 [abstract] [bibtex] [pdf] [url]
8. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  Space-Efficient Representations of Rectangle Datasets Supporting Orthogonal Range Querying.
  Information Systems 38(5):635-655, 2013 [abstract] [bibtex] [pdf] [url]
9. Djamal Belazzougui, Gonzalo Navarro, and Daniel Valenzuela.
  Improved Compressed Indexes for Full-Text Document Retrieval.
  Journal of Discrete Algorithms 18:3-13, 2013 [abstract] [bibtex] [pdf] [url]
10. Nieves Brisaboa, Susana Ladra, and Gonzalo Navarro.
  DACs: Bringing Direct Access to Variable-Length Codes.
  Information Processing and Management 49(1):392-404, 2013 [abstract] [bibtex] [pdf] [url]
International conferences
1. Gonzalo Navarro and Sharma Thankachan.
  Top-k Document Retrieval in Compact Space and Near-Optimal Time.
  Proc. ISAAC'13, pages 394-404. LNCS 8283 [abstract] [bibtex] [pdf] [url]
2. Gonzalo Navarro and Sharma Thankachan.
  Faster Top-k Document Retrieval in Optimal Space.
  Proc. SPIRE'13, pages 255-262. LNCS 8214 [abstract] [bibtex] [pdf] [url]
3. Héctor Ferrada and Gonzalo Navarro.
  A Lempel-Ziv Compressed Structure for Document Listing.
  Proc. SPIRE'13, pages 116-128. LNCS 8214 [abstract] [bibtex] [pdf] [url]
4. Guillermo De Bernardo, Sandra Alvarez-García, Nieves Brisaboa, Gonzalo Navarro and Oscar Pedreira.
  Compact Querieable Representations of Raster Data.
  Proc. SPIRE'13, pages 96-108. LNCS 8214 [abstract] [bibtex] [pdf] [url]
5. Jérémy Barbay, Timothy Chan, Gonzalo Navarro, and Pablo Pérez-Lantero.
  Maximum-Weight Planar Boxes in O(n^2) Time (and Better).
  Proc. CCCG'13, pages 151-156 [abstract] [bibtex] [pdf] [url]
6. Roberto Konow, Gonzalo Navarro, Charles Clarke, and Alejandro López-Ortíz.
  Faster and Smaller Inverted Indices with Treaps.
  Proc. ACM SIGIR'13, pages 193-202 [abstract] [bibtex] [pdf] [url]
7. Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.
  Encodings for Range Selection and Top-k Queries.
  Proc. ESA'13, pages 553-564. LNCS 8125 [abstract] [bibtex] [pdf] [url]
8. Djamal Belazzougui, Travis Gagie, and Gonzalo Navarro.
  Better Space Bounds for Parameterized Range Majority and Minority.
  Proc. WADS'13, pages 121-132. LNCS 8037 [abstract] [bibtex] [pdf] [url]
9. Travis Gagie, Kalle Karhu, Gonzalo Navarro, Simon Puglisi, and Jouni Sirén.
  Document Listing on Repetitive Collections.
  Proc. CPM'13, pages 107-119. LNCS 7922 [abstract] [bibtex] [pdf] [url]
10. Roberto Konow and Gonzalo Navarro.
  Faster Compact Top-k Document Retrieval.
  Proc. DCC'13, pages 351-360 [abstract] [bibtex] [pdf] [url] [fix]
11. Gonzalo Navarro and Alberto Ordóñez.
  Compressing Huffman Models on Large Alphabets.
  Proc. DCC'13, pages 381-390 [abstract] [bibtex] [pdf] [url]
12. Gonzalo Navarro and Yakov Nekrich.
  Optimal Dynamic Sequence Representations.
  Proc. SODA'13, pages 865-876 [abstract] [bibtex] [pdf] [url] [fix]

2012 (25)

International books
1. Gonzalo Navarro and Vladimir Pestov (editors).
  Proceedings of the 5th International Workshop on Similarity Search and Applications (SISAP 2012).
  Toronto, Canada, August 2012.
  Springer-Verlag LNCS Series, vol. 7404 [bibtex] [contents] [url]
International journals
1. Nieves Brisaboa, Antonio Fariña, Susana Ladra, and Gonzalo Navarro.
  Implicit Indexing of Natural Language Text by Reorganizing Bytecodes.
  Information Retrieval 15(6):527-557, 2012 [abstract] [bibtex] [pdf] [url]
2. Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro.
  LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  Theoretical Computer Science 459:26-41, 2012 [abstract] [bibtex] [pdf] [url]
3. Travis Gagie, Gonzalo Navarro, and Simon Puglisi.
  New Algorithms on Wavelet Trees and Applications to Information Retrieval.
  Theoretical Computer Science 426-427:25-41, 2012 [abstract] [bibtex] [pdf] [url]
4. Antonio Fariña, Nieves Brisaboa, Gonzalo Navarro, Francisco Claude, Ángeles Places, and Eduardo Rodríguez.
  Word-based Self-Indexes for Natural Language Text.
  ACM Transactions on Information Systems 30(1):article 1, 2012 [abstract] [bibtex] [pdf] [url]
5. Francisco Claude, Gonzalo Navarro, Hannu Peltola, Leena Salmela, and Jorma Tarhio.
  String Matching with Alphabet Sampling.
  Journal of Discrete Algorithms 11:37-50, 2012 [abstract] [bibtex] [pdf] [url]
6. Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Boosting Text Compression with Word-Based Statistical Encoding.
  The Computer Journal 55(1):111-131, 2012 [abstract] [bibtex] [pdf] [url] [fix]
7. Diego Arroyuelo, Gonzalo Navarro, and Kunihiko Sadakane.
  Stronger Lempel-Ziv Based Compressed Text Indexing.
  Algorithmica 62(1):54-101, 2012 [abstract] [bibtex] [pdf] [url] [fix]
International conferences
1. Gonzalo Navarro.
  Indexing Highly Repetitive Collections.
  Proc. IWOCA'12, pages 274-279. LNCS 7643 [abstract] [bibtex] [pdf] [url]
2. Francisco Claude and Gonzalo Navarro.
  Improved Grammar-Based Compressed Indexes.
  Proc. SPIRE'12, pages 180-192. LNCS 7608 [abstract] [bibtex] [pdf] [url]
3. Andrés Abeliuk and Gonzalo Navarro.
  Compressed Suffix Trees for Repetitive Texts.
  Proc. SPIRE'12, pages 30-41. LNCS 7608 [abstract] [bibtex] [pdf] [url]
4. Cecilia Hernández and Gonzalo Navarro.
  Compressed Representation of Web and Social Networks via Dense Subgraphs.
  Proc. SPIRE'12, pages 264-276. LNCS 7608 [abstract] [bibtex] [pdf] [url]
5. Francisco Claude and Gonzalo Navarro.
  The Wavelet Matrix.
  Proc. SPIRE'12, pages 167-179. LNCS 7608 [abstract] [bibtex] [pdf] [url]
6. Roberto Konow and Gonzalo Navarro.
  Dual-Sorted Inverted Lists in Practice.
  Proc. SPIRE'12, pages 295-306. LNCS 7608 [abstract] [bibtex] [pdf] [url]
7. Nieves Brisaboa, Gonzalo Navarro, and Alberto Ordóñez.
  Smaller Self-Indexes for Natural Language.
  Proc. SPIRE'12, pages 372-378. LNCS 7608 [abstract] [bibtex] [pdf] [url]
8. Nieves Brisaboa, Ana Cerdeira, Gonzalo Navarro, and Oscar Pedreira.
  Ranked Document Retrieval in (Almost) No Space.
  Proc. SPIRE'12, pages 155-160. LNCS 7608 [abstract] [bibtex] [pdf] [url]
9. Jérémy Barbay, Gonzalo Navarro, and Pablo Pérez-Lantero.
  Adaptive Techniques to find Optimal Planar Boxes.
  Proc. CCCG'12, pages 79-84 [abstract] [bibtex] [pdf] [url]
10. Djamal Belazzougui and Gonzalo Navarro.
  New Lower and Upper Bounds for Representing Sequences.
  Proc. ESA'12, pages 181-192. LNCS 7501 [abstract] [bibtex] [pdf] [url]
11. Gonzalo Navarro.
  Wavelet Trees for All.
  Proc. CPM'12, pages 2-26. LNCS 7354 [abstract] [bibtex] [pdf] [url]
12. Yakov Nekrich and Gonzalo Navarro.
  Sorted Range Reporting.
  Proc. SWAT'12, pages 271-282. LNCS 7357 [abstract] [bibtex] [pdf] [url]
13. Gonzalo Navarro and Eliana Providel.
  Fast, Small, Simple Rank/Select on Bitmaps.
  Proc. SEA'12, pages 295-306. LNCS 7276 [abstract] [bibtex] [pdf] [url]
14. Gonzalo Navarro and Daniel Valenzuela.
  Space-Efficient Top-k Document Retrieval.
  Proc. SEA'12, pages 307-319. LNCS 7276 [abstract] [bibtex] [pdf] [url]
15. Nieves Brisaboa, Guillermo de Bernardo, and Gonzalo Navarro.
  Compressed Dynamic Binary Relations.
  Proc. DCC'12, pages 52-61 [abstract] [bibtex] [pdf] [url]
16. Gonzalo Navarro and Yakov Nekrich.
  Top-k Document Retrieval in Optimal Time and Linear Space.
  Proc. SODA'12, pages 1066-1078. [abstract] [bibtex] [pdf] [url]
National conferences
1. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  Indexación mediante Arrays de Sufijos para Recuperación de Información Geográfica.
  Proc. CERI'12. [abstract] [bibtex] [pdf] [url]

2011 (22)

International book chapters
1. Ricardo Baeza-Yates, Gonzalo Navarro, and Nivio Ziviani.
  Documents: Languages and Properties.
  In Modern Information Retrieval (2nd edition). Chapter 6, pages 203-254, 2011. Addison-Wesley. [bibtex] [url]
2. Ricardo Baeza-Yates and Gonzalo Navarro.
  Queries: Languages and Properties.
  In Modern Information Retrieval (2nd edition). Chapter 7, pages 255-280, 2011. Addison-Wesley. [bibtex] [url]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  Indexing and Searching.
  In Modern Information Retrieval (2nd edition). Chapter 9, pages 337-398, 2011. Addison-Wesley. [bibtex] [url]
International journals
1. Francisco Claude and Gonzalo Navarro.
  Self-Indexed Grammar-Based Compression.
  Fundamenta Informaticae 111(3):313-337, 2011 [abstract] [bibtex] [pdf] [url]
2. Marcos Kiwi, Gonzalo Navarro, and Claudio Telha.
  On-line Approximate String Matching with Bounded Errors.
  Theoretical Computer Science 412(45):6359--6370, 2011 [abstract] [bibtex] [pdf] [url]
3. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Fully-Compressed Suffix Trees.
  ACM Transactions on Algorithms 7(4): article 53, 2011 [abstract] [bibtex] [pdf] [url]
4. Gonzalo Navarro, Rodrigo Paredes, Patricio Poblete, and Peter Sanders.
  Stronger Quickheaps.
  International Journal on Foundations of Computer Science 22(4):945-969, 2011. [abstract] [bibtex] [pdf] [url]
5. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Improving Semistatic Compression via Phrase-based Modeling.
  Information Processing and Management 47(4):545-559, 2011 [abstract] [bibtex] [pdf] [url]
6. Diego Arroyuelo and Gonzalo Navarro.
  Space-Efficient Construction of Lempel-Ziv Compressed Text Indexes.
  Information and Computation 209(7):1070-1102, 2011 [abstract] [bibtex] [pdf] [url]
7. Gonzalo Navarro and Roberto Uribe.
  Fully Dynamic Metric Access Methods based on Hyperplane Partitioning.
  Information Systems 36(4):734-747, 2011 [abstract] [bibtex] [pdf] [url]
International conferences
1. Cecilia Hernández and Gonzalo Navarro.
  Compression of Web and Social Graphs supporting Neighbor and Community Queries.
  Proc. SNA-KDD'11. [abstract] [bibtex] [pdf]
2. Francisco Claude, Antonio Fariña, Miguel Martínez-Prieto, and Gonzalo Navarro.
  Indexes for Highly Repetitive Document Collections.
  Proc. ACM CIKM'11, pages 463-468 [abstract] [bibtex] [pdf] [url]
3. Matthias Petri, Gonzalo Navarro, Shane Culpepper, and Simon Puglisi.
  Backwards Search in Context Bound Text Transformations.
  Proc. CCP'11, pages 82-91. [abstract] [bibtex] [pdf] [url]
4. Djamal Belazzougui and Gonzalo Navarro.
  Improved Compressed Indexes for Full-Text Document Retrieval.
  Proc. SPIRE'11 pages 286-297. LNCS 7024 [abstract] [bibtex] [pdf] [url] [fix]
5. Gonzalo Navarro and Luís Russo.
  Space-Efficient Data-Analysis Queries on Grids.
  Proc. ISAAC'11, pages 323-332. LNCS 7074 [abstract] [bibtex] [pdf] [url]
6. Djamal Belazzougui and Gonzalo Navarro.
  Alphabet-Independent Compressed Text Indexing.
  Proc. ESA'11, pages 748-759. LNCS 6942 [abstract] [bibtex] [pdf] [url] [fix]
7. Eric Sadit, Edgar Chávez, and Gonzalo Navarro.
  Succinct Nearest Neighbor Search.
  Proc. SISAP'11, pages 33-40. [abstract] [bibtex] [pdf] [url]
8. Sebastián Kreft and Gonzalo Navarro.
  Self-Indexing Based on LZ77.
  Proc. CPM'11, pages 41-54. LNCS 6661. [abstract] [bibtex] [pdf] [url]
9. Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro.
  LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  Proc. CPM'11, pages 285-298. LNCS 6661. [abstract] [bibtex] [pdf] [url]
10. Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, Miguel Martínez-Prieto, and Gonzalo Navarro.
  Compressed String Dictionaries.
  Proc. SEA'11, pages 136-147. LNCS 6630. [abstract] [bibtex] [pdf] [url]
11. Gonzalo Navarro, Simon Puglisi, and Daniel Valenzuela.
  Practical Compressed Document Retrieval.
  Proc. SEA'11, pages 193-205. LNCS 6630. [abstract] [bibtex] [pdf] [url]
National conferences
1. Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, Miguel Martínez-Prieto, and Gonzalo Navarro.
  Compresión y Consulta de Diccionarios de Texto en Grandes Colecciones de Datos.
  Proc. JISBD'11, pages 31-44. In Spanish. [abstract] [bibtex] [pdf]

2010 (29)

International book chapters
1. Francisco Claude and Gonzalo Navarro.
  Extended Compact Web Graph Representations.
  In Tapio Elomaa, Heikki Mannila, and Pekka Orponen (editors) Algorithms and Applications (Ukkonen Festschrift). Pages 77-91, 2010.
  Springer, LNCS 6060. [abstract] [bibtex] [pdf] [url]
Journal special issues
1. Edgar Chávez and Gonzalo Navarro (editors).
  Letters on Similarity Search in Metric Spaces.
  ACM SIGSPATIAL Special 2(2):1-39, 2010. [bibtex]
International journals
1. Diego Arroyuelo and Gonzalo Navarro.
  Practical Approaches to Reduce the Space Requirement of Lempel-Ziv-Based Compressed Text Indices.
  ACM Journal of Experimental Algorithmics 15(1.5), 2010. 54 pages [abstract] [bibtex] [pdf] [url]
2. Lucian Ilie, Gonzalo Navarro, and Liviu Tinta.
  The Longest Common Extension Problem Revisited and Applications to Approximate String Searching.
  Journal of Discrete Algorithms 8(4):418-428, 2010. [abstract] [bibtex] [pdf] [url]
3. Francisco Claude and Gonzalo Navarro.
  Fast and Compact Web Graph Representations.
  ACM Transactions on the Web 4(4):article 16, 2010. [abstract] [bibtex] [pdf] [url]
4. Edgar Chávez and Gonzalo Navarro.
  Fundamentals of the Problem.
  ACM SIGSPATIAL Special 2(2):2-7, 2010. [bibtex] [pdf] [url]
5. Gonzalo Navarro and Rodrigo Paredes.
  On Sorting, Heaps, and Minimum Spanning Trees.
  Algorithmica 57(4):585-620, 2010. [abstract] [bibtex] [pdf] [url]
6. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki.
  Storage and Retrieval of Highly Repetitive Sequence Collections.
  Journal of Computational Biology 17(3):281-308, 2010. [abstract] [bibtex] [pdf] [url]
7. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Dynamic Lightweight Text Compression.
  ACM Transactions on Information Systems 28(3):article 10, 2010. [abstract] [bibtex] [pdf] [url]
International conferences
1. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  Range Queries over a Compact Representation of Minimum Bounding Rectangles.
  Proc. SeCoGIS'10, pages 33-42. LNCS 6413. [abstract] [bibtex] [pdf] [url]
2. Jérémy Barbay, Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.
  Alphabet Partitioning for Compressed Rank/Select and Applications.
  Proc. ISAAC'10, part II, pages 315-326. LNCS 6507. [abstract] [bibtex] [pdf] [url]
3. Arash Farzan, Travis Gagie and Gonzalo Navarro.
  Entropy-Bounded Representation of Point Grids.
  Proc. ISAAC'10, part II, pages 327-338. LNCS 6507. [abstract] [bibtex] [pdf] [url] [fix]
4. Shane Culpepper, Gonzalo Navarro, Simon Puglisi, and Andrew Turpin.
  Top-k Ranked Document Search in General Text Databases.
  Proc. ESA'10, part II, pages 194-205. LNCS 6347. [abstract] [bibtex] [pdf] [url]
5. Travis Gagie, Gonzalo Navarro, and Simon Puglisi.
  Colored Range Queries and Document Retrieval.
  Proc. SPIRE'10, pages 67-81. LNCS 6393. [abstract] [bibtex] [pdf] [url]
6. Gonzalo Navarro and Simon Puglisi.
  Dual-Sorted Inverted Lists.
  Proc. SPIRE'10, pages 310-322. LNCS 6393. [abstract] [bibtex] [pdf] [url]
7. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Parallel and Distributed Compressed Indexes.
  Proc. CPM'10, pages 348-360. LNCS 6129. [abstract] [bibtex] [pdf] [url]
8. Francisco Claude, Antonio Fariña, Miguel Martínez-Prieto, and Gonzalo Navarro.
  Compressed q-gram Indexing for Highly Repetitive Biological Sequences.
  Proc. IEEE BIBE'10, pages 86-91. [abstract] [bibtex] [pdf] [url]
9. Nieves Brisaboa, Ana Cerdeira, Gonzalo Navarro, and Gabriella Pasi.
  An Efficient Implementation of a Flexible XPath Extension.
  Proc. RIAO'10. [abstract] [bibtex] [pdf] [url]
10. Jérémy Barbay, Francisco Claude, and Gonzalo Navarro.
  Compact Rich-Functional Binary Relation Representations.
  Proc. LATIN'10, pages 170-183. LNCS 6034. [abstract] [bibtex] [pdf] [fix] [url]
11. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  A Fun Application of Compact Data Structures to Indexing Geographic Data.
  Proc. FUN'10, pages 77-88. LNCS 6099. [abstract] [bibtex] [pdf] [url]
12. Rodrigo Cánovas and Gonzalo Navarro.
  Practical Compressed Suffix Trees.
  Proc. SEA'10, pages 94-105. LNCS 6049. [abstract] [bibtex] [pdf] [url]
13. Diego Arroyuelo, Francisco Claude, Sebastian Maneth, Veli Mäkinen, Gonzalo Navarro, Kim Nguyễn, Jouni Sirén, and Niko Välimäki.
  Fast In-Memory XPath Search over Compressed Text and Tree Indexes.
  Proc. ICDE'10, pages 417-428. [abstract] [bibtex] [pdf] [url]
14. Sebastián Kreft and Gonzalo Navarro.
  LZ77-like Compression with Fast Random Access.
  Proc. DCC'10, pages 239-248. [abstract] [bibtex] [pdf] [url]
15. Nieves Brisaboa, Antonio Fariña, Juan López, Gonzalo Navarro, and Eduardo López.
  A New Searchable Variable-to-Variable Compressor.
  Proc. DCC'10, pages 199-208. [abstract] [bibtex] [pdf] [url]
16. Kunihiko Sadakane and Gonzalo Navarro.
  Fully-Functional Succinct Trees.
  Proc. SODA'10, pages 134-149. [abstract] [bibtex] [pdf] [fix] [url]
17. Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, and Kunihiko Sadakane.
  Succinct Trees in Practice.
  Proc. ALENEX'10, pages 84-97. [abstract] [bibtex] [pdf] [url]
18. Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.
  Fast and Compact Prefix Codes.
  Proc. SOFSEM'10, pages 419-427. LNCS 5901. [abstract] [bibtex] [pdf] [url]
National conferences
1. Jérémy Barbay, Carlos Bedregal, and Gonzalo Navarro.
  Improving Text Indexes Using Compressed Permutations.
  Proc. JCC'10. [abstract] [bibtex] [pdf]
2. Nieves Brisaboa, Ana Cerdeira, Gonzalo Navarro, and Gabriella Pasi.
  Estrategias de Optimización de Consultas XPath Flexibles sobre XML Wavelet Trees.
  Proc. CERI'10, pages 207-218. [abstract] [bibtex] [pdf]

2009 (28)

International book chapters
1. Gonzalo Navarro.
  Text Index Compression.
  In Ling Liu and M. Tamer Özsu (editors), Encyclopedia of Database Systems, pages 3051-3055, 2009. Springer. [bibtex]
2. Gonzalo Navarro.
  Managing Compressed Structured Text.
  In Ling Liu and M. Tamer Özsu (editors), Encyclopedia of Database Systems, pages 1679-1684, 2009. Springer. [bibtex]
Journal special issues
1. Edgar Chávez and Gonzalo Navarro (editors).
  Special Issue on Selected Papers from SISAP 2008.
  Journal of Discrete Algorithms 7(1):1-77, 2009. [bibtex] [editorial]
International journals
1. Rodrigo González and Gonzalo Navarro.
  A Compressed Text Index on Secondary Memory.
  Journal of Combinatorial Mathematics and Combinatorial Computing 71:127-154, 2009. [abstract] [bibtex] [pdf] [fix]
2. Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro.
  Faster Entropy-Bounded Compressed Suffix Trees.
  Theoretical Computer Science 410(51):5354-5364, 2009. [abstract] [bibtex] [pdf] [fix]
3. Luís Russo, Gonzalo Navarro, Arlindo Oliveira, and Pedro Morales.
  Approximate String Matching with Compressed Indexes.
  Algorithms 2(3), 1105-1136, 2009. [abstract] [bibtex] [pdf]
4. Rodrigo González and Gonzalo Navarro.
  Rank/Select on Dynamic Compressed Sequences and Applications.
  Theoretical Computer Scienc 410(43):4414-4422, 2009. [abstract] [bibtex] [pdf]
5. Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes.
  Speeding up Spatial Approximation Search in Metric Spaces.
  ACM Journal of Experimental Algorithmics 14:article 3.6, 2009. 21 pages. [abstract] [bibtex] [pdf]
6. Amihood Amir and Gonzalo Navarro.
  Parameterized Matching on Non-linear Structures.
  Information Processing Letters 109(15):864-867, 2009. [abstract] [bibtex] [pdf]
7. Paolo Ferragina, Rodrigo González, Gonzalo Navarro, and Rossano Venturini.
  Compressed Text Indexes: From Theory to Practice.
  ACM Journal of Experimental Algorithmics 13:article 12, 2009. 30 pages. [abstract] [bibtex] [pdf]
8. Benjamin Bustos and Gonzalo Navarro.
  Improving the Space Cost of k-NN Search in Metric Spaces by Using Distance Estimators.
  Multimedia Tools and Applications 41(2):215-233, 2009. [abstract] [bibtex] [pdf]
9. Gonzalo Navarro.
  Implementing the LZ-index: Theory versus Practice.
  ACM Journal of Experimental Algorithmics 13:article 2, 49 pages, 2009. [abstract] [bibtex] [pdf]
National and regional journals
1. Joaquín Adiego, Gonzalo Navarro, and Pablo de la Fuente.
  A Prototype for Querying LZCS Transformed Documents. In Spanish.
  IEEE Latin America Transactions 7(3):353-360, 2009. [abstract] [bibtex] [pdf]
International conferences
1. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  A New Point Access Method based on Wavelet Trees.
  Proc. SeCoGIS'09, pages 297-306. LNCS 5833. [abstract] [bibtex] [pdf]
2. Nieves Brisaboa, Ana Cerdeira, and Gonzalo Navarro.
  A Compressed Self-Indexed Representation of XML Documents.
  Proc. ECDL'09, pages 273-284. LNCS 5714. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro.
  Combining Text Compression and String Matching: The Miracle of Self-Indexing.
  Proc. PSC'09, page 1. Abstract of invited talk. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  Analyzing Metric Space Indexes: What For?
  Proc. SISAP'09, pages 3-10. [abstract] [bibtex] [pdf] [fix]
5. Gonzalo Navarro and Nora Reyes.
  Dynamic Spatial Approximation Trees for Massive Data.
  Proc. SISAP'09, pages 81-88. [abstract] [bibtex] [pdf]
6. Roberto Uribe and Gonzalo Navarro.
  EGNAT: A Fully Dynamic Metric Access Method for Secondary Memory.
  Proc. SISAP'09, pages 57-64. [abstract] [bibtex] [pdf]
7. Nieves Brisaboa, Susana Ladra, and Gonzalo Navarro.
  K2-trees for Compact Web Graph Representation.
  Proc. SPIRE'09, pages 18-30. LNCS 5721. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro and Leena Salmela.
  Indexing Variable Length Substrings for Exact and Approximate Matching.
  Proc. SPIRE'09, pages 214-221. LNCS 5721. [abstract] [bibtex] [pdf]
9. Nieves Brisaboa, Susana Ladra, and Gonzalo Navarro.
  Directly Addressable Variable-Length Codes.
  Proc. SPIRE'09, pages 122-130. LNCS 5721. [abstract] [bibtex] [pdf]
10. Francisco Claude and Gonzalo Navarro.
  Self-Indexed Text Compression using Straight-Line Programs.
  Proc. MFCS'09, pages 235-246. LNCS 5734. [abstract] [bibtex] [pdf]
11. Gonzalo Navarro.
  Implementation and Application of Automata in String Processing.
  Proc. CIAA'09, page 1. LNCS 5642. Abstract of invited talk. [abstract] [bibtex] [pdf]
12. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki.
  Storage and Retrieval of Individual Genomes.
  Proc. RECOMB'09, pages 121-137. [abstract] [bibtex] [pdf]
13. Jérémy Barbay and Gonzalo Navarro.
  Compressed Representations of Permutations, and Applications.
  Proc. STACS'09, pages 111-122. [abstract] [bibtex] [pdf]
National and regional conferences
1. Norma Herrera and Gonzalo Navarro.
  Árboles de Sufijos Comprimidos en Memoria Secundaria.
  Proc. CLEI'09. In Spanish. [abstract] [bibtex] [pdf]
2. Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco.
  Indexación Espacial de Puntos Empleando Wavelet Trees.
  Proc. JISBD'09, pages 225-236. In Spanish. [abstract] [bibtex] [pdf]

2008 (23)

International books
1. Edgar Chávez and Gonzalo Navarro (editors).
  Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP 2008).
  Cancun, Mexico, April 2008.
  IEEE Computer Society Press. [bibtex] [contents]
International book chapters
1. Gonzalo Navarro.
  Approximate Regular Expression Matching.
  In M. Kao (editor), Encyclopedia of Algorithms, pages 46-48, 2008. Springer. [bibtex]
2. Veli Mäkinen and Gonzalo Navarro.
  Compressed Text Indexing.
  In M. Kao (editor), Encyclopedia of Algorithms, pages 176-178, 2008. Springer. [bibtex]
3. Gonzalo Navarro.
  Sequential Approximate String Matching.
  In M. Kao (editor), Encyclopedia of Algorithms, pages 818-820, 2008. Springer. [bibtex]
International journals
1. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  New Adaptive Compressors for Natural Language Text.
  Software Practice and Experience 38(13):1429-1450, 2008. [abstract] [bibtex] [pdf]
2. Veli Mäkinen and Gonzalo Navarro.
  Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
  ACM Transactions on Algorithms 4(3):article 32, 2008. 38 pages. [abstract] [bibtex] [pdf] [fix]
3. Edgar Chávez, Karina Figueroa, and Gonzalo Navarro.
  Effective Proximity Retrieval by Ordering Permutations.
  IEEE Transactions on Pattern Analysis and Machine Intelligence 30(9):1647-1658, 2008. [abstract] [bibtex] [pdf] [shorter pdf w/o appendix]
4. Gonzalo Navarro and Nora Reyes.
  Dynamic Spatial Approximation Trees.
  ACM Journal of Experimental Algorithmics 12, article 1.5, 68 pages, 2008. [abstract] [bibtex] [pdf]
International conferences
1. Francisco Claude and Gonzalo Navarro.
  Practical Rank/Select Queries over Arbitrary Sequences.
  Proc. SPIRE'08, pages 176-187. LNCS 5280. [abstract] [bibtex] [pdf]
2. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, Ángeles Places, and Eduardo Rodríguez.
  Self-Indexing Natural Language.
  Proc. SPIRE'08, pages 121-132. LNCS 5280. [abstract] [bibtex] [pdf]
3. Jouni Sirén, Niko Välimäki, Veli Mäkinen, and Gonzalo Navarro.
  Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections.
  Proc. SPIRE'08, pages 164-175. LNCS 5280. [abstract] [bibtex] [pdf]
4. Francisco Claude, Gonzalo Navarro, Hannu Peltola, Leena Salmela, and Jorma Tarhio.
  Speeding Up Pattern Matching by Text Sampling.
  Proc. SPIRE'08, pages 87-98. LNCS 5280. [abstract] [bibtex] [pdf]
5. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Indexed Hierarchical Approximate String Matching.
  Proc. SPIRE'08, pages 144-154. LNCS 5280. [abstract] [bibtex] [pdf]
6. Nieves Brisaboa, Antonio Fariña, Susana Ladra, and Gonzalo Navarro.
  Reorganizing Compressed Text.
  Proc. ACM SIGIR'08, pages 139-146. [abstract] [bibtex] [pdf]
7. Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro.
  An(other) Entropy-Bounded Compressed Suffix Tree.
  Proc. CPM'08, pages 152-165. LNCS 5029. [abstract] [bibtex] [pdf]
8. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Dynamic Fully-Compressed Suffix Trees.
  Proc. CPM'08, pages 191-203. LNCS 5029. [abstract] [bibtex] [pdf]
9. Marcos Kiwi, Gonzalo Navarro, and Claudio Telha.
  On-line Approximate String Matching with Bounded Errors.
  Proc. CPM'08, pages 130-142. LNCS 5029. [abstract] [bibtex] [pdf]
10. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Fully-Compressed Suffix Trees.
  Proc. LATIN'08, pages 362-373. LNCS 4957. [abstract] [bibtex] [pdf]
11. Rodrigo González and Gonzalo Navarro.
  Improved Dynamic Rank-Select Entropy-Bound Structures.
  Proc. LATIN'08, pages 374-386. LNCS 4967. [abstract] [bibtex] [pdf] [fix]
12. Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Word-based Statistical Compressors as Natural Language Compression Boosters.
  Proc. DCC'08, pages 162-171. [abstract] [bibtex] [pdf]
13. Veli Mäkinen and Gonzalo Navarro.
  On Self-Indexing Images --- Image Compression with Added Value.
  Proc. DCC'08, pages 422-431. [abstract] [bibtex] [pdf]
14. Gonzalo Navarro and Luís Russo.
  Re-Pair Achieves High-Order Entropy.
  Proc. DCC'08, page 537 (poster). [abstract] [bibtex] [pdf]
National and regional conferences
1. Joaquín Adiego, Gonzalo Navarro, and Pablo de la Fuente.
  Un Prototipo para la Consulta sobre Documentos Transformados con LZCS.
  Proc. JISBD'08, pages 87-98. In Spanish. [abstract] [bibtex] [pdf]

2007 (16)

International books
1. Martin Farach-Colton, Jesus Favela, Genoveva Vargas, Vibhu Mittal, and Gonzalo Navarro (editors).
  Proceedings of the 8th Mexican International Conference on Computer Science (ENC 2007).
  Morelia, Mexico, September 2007.
  IEEE Computer Society Press. [bibtex]
International journals
1. Veli Mäkinen and Gonzalo Navarro.
  Rank and Select Revisited and Extended.
  Theoretical Computer Science 387(3):332-347, 2007. [abstract] [bibtex] [pdf] [fix]
2. Gonzalo Navarro, Rodrigo Paredes, and Edgar Chávez.
  t-Spanners for Metric Space Searching.
  Data and Knowledge Engineering 63(3):820-854, 2007. [abstract] [bibtex] [pdf]
3. Paolo Ferragina, Giovani Manzini, Veli Mäkinen, and Gonzalo Navarro.
  Compressed Representations of Sequences and Full-Text Indexes.
  ACM Transactions on Algorithms 3(2), article 20, 24 pages, 2007. [abstract] [bibtex] [pdf]
4. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro.
  Rotation and Lighting Invariant Template Matching.
  Information and Computation 205(7):1096-1113, 2007. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro and Veli Mäkinen.
  Compressed Full-Text Indexes.
  ACM Computing Surveys 39(1), article 2, 61 pages, 2007. [abstract] [bibtex] [pdf] [fix]
6. Joaquín Adiego, Gonzalo Navarro, and Pablo de la Fuente.
  Lempel-Ziv Compression of Highly Structured Documents.
  Journal of the American Society for Information Systems and Technology 58(4):461-478, 2007. [abstract] [bibtex] [pdf]
7. Joaquín Adiego, Gonzalo Navarro, and Pablo de la Fuente.
  Using Structural Contexts to Compress Semistructured Text Collections.
  Information Processing and Management 43:769-790, 2007. [abstract] [bibtex] [pdf]
8. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Lightweight Natural Language Text Compression.
  Information Retrieval 10:1-33, 2007. [abstract] [bibtex] [pdf]
International conferences
1. Rodrigo González and Gonzalo Navarro.
  A Compressed Text Index on Secondary Memory.
  Proc. IWOCA'07, pages 80-91. [abstract] [bibtex] [pdf]
2. Diego Arroyuelo and Gonzalo Navarro.
  Smaller and Faster Lempel-Ziv Indices.
  Proc. IWOCA'07, pages 11-20. [abstract] [bibtex] [pdf]
3. Francisco Claude and Gonzalo Navarro.
  A Fast and Compact Web Graph Representation.
  Proc. SPIRE'07, pages 105-116. LNCS 4726. [abstract] [bibtex] [pdf]
4. Luís Russo, Gonzalo Navarro, and Arlindo Oliveira.
  Approximate String Matching with Lempel-Ziv Compressed Indexes.
  Proc. SPIRE'07, pages 264-275. LNCS 4726. [abstract] [bibtex] [pdf]
5. Veli Mäkinen and Gonzalo Navarro
  Implicit Compression Boosting with Applications to Self-Indexing.
  Proc. SPIRE'07, pages 214-226. LNCS 4726. [abstract] [bibtex] [pdf]
6. Rodrigo González and Gonzalo Navarro.
  Compressed Text Indexes with Fast Locate.
  Proc. CPM'07, pages 216-227. LNCS 4580. [abstract] [bibtex] [pdf] [fix]
7. Diego Arroyuelo and Gonzalo Navarro.
  A Lempel-Ziv Text Index on Secondary Storage.
  Proc. CPM'07, pages 83-94. LNCS 4580. [abstract] [bibtex] [pdf] [fix]

2006 (15)

International books
1. Gonzalo Navarro, Leopoldo Bertossi, and Yoshiharu Kohayakawa (editors).
  Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006).
  Santiago, Chile, August 2006.
  Springer. [bibtex] [contents]
International journals
1. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro.
  Flexible Music Retrieval in Sublinear Time.
  International Journal of Foundations of Computer Science 17(6):1345-1364, 2006. [abstract] [bibtex] [pdf]
2. Heikki Hyyrö and Gonzalo Navarro.
  Bit-Parallel Computation of Local Similarity Score Matrices with Unitary Weights.
  International Journal of Foundations of Computer Science 17(6):1325-1344, 2006. [abstract] [bibtex] [pdf]
3. Szymon Grabowski, Gonzalo Navarro, Rafal Przywarski, Alejandro Salinger, and Veli Mäkinen.
  A Simple Alphabet-Independent FM-Index.
  International Journal of Foundations of Computer Science 17(6):1365-1384, 2006. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro and Edgar Chávez.
  A Metric Index for Approximate String Matching.
  Theoretical Computer Science 352 (1-3):266-279, 2006. [abstract] [bibtex] [pdf]
International conferences
1. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Improving Semistatic Compression via Pair-Based Coding.
  Proc. PSI'06, pages 124-134. LNCS 4378. [abstract] [bibtex] [pdf]
2. Rafal Przywarski, Szymon Grabowski, Gonzalo Navarro, and Alejandro Salinger.
  FM-KZ: An Even Simpler Alphabet-Independent FM-Index.
  Proc. PSC'06, pages 226-240. [abstract] [bibtex] [pdf]
3. Veli Mäkinen and Gonzalo Navarro.
  Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
  Proc. CPM'06, pages 307-318. LNCS 4009. [abstract] [bibtex] [pdf]
4. Diego Arroyuelo, Gonzalo Navarro, and Kunihiko Sadakane.
  Reducing the Space Requirement of LZ-index.
  Proc. CPM'06, pages 319-330. LNCS 4009. [abstract] [bibtex] [pdf]
5. Rodrigo González and Gonzalo Navarro.
  Statistical Encoding of Succinct Data Structures.
  Proc. CPM'06, pages 295-306. LNCS 4009. [abstract] [bibtex] [pdf]
6. Roberto Uribe, Gonzalo Navarro, Ricardo Barrientos, and Mauricio Marín.
  An Index Data Structure for Searching in Metric Space Databases.
  Proc. ICCS'06, pages 611-617. LNCS 3991. [abstract] [bibtex] [pdf]
7. Rodrigo Paredes and Gonzalo Navarro.
  Optimal Incremental Sorting.
  Proc. ALENEX'06, pages 171-182. [abstract] [bibtex] [pdf]
8. Rodrigo Paredes, Edgar Chávez, Karina Figueroa, and Gonzalo Navarro.
  Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces.
  Proc. WEA'06, pages 85-97. LNCS 4007. [abstract] [bibtex] [pdf]
9. Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes.
  On the Least Cost For Proximity Searching in Metric Spaces.
  Proc. WEA'06, pages 279-290. LNCS 4007. [abstract] [bibtex] [pdf]
10. Veli Mäkinen and Gonzalo Navarro.
  Position-Restricted Substring Searching.
  Proc. LATIN'06, pages 703-714. LNCS 3887. [abstract] [bibtex] [pdf] [fix]

2005 (30)

International books
1. Mariano Consens and Gonzalo Navarro, editors.
  Proceedings of the 12th International Symposium on String Processing and Information Retrieval (SPIRE 2005).
  Buenos Aires, Argentina, November 2005.
  Springer Lecture Notes in Computer Science Series, vol. 3772 [bibtex] [contents]
International book chapters
1. Gonzalo Navarro.
  Text Databases.
  In L. Rivero, J. Doorn and V. Ferraggine (editors), Encyclopedia of Database Technologies and Applications, pages 688-694, 2005.
  Idea Group Inc., Pennsylvania, USA. ISBN 1-59140-560-2. [bibtex] [pdf]
2. Edgar Chávez and Gonzalo Navarro.
  Metric Databases.
  In L. Rivero, J. Doorn and V. Ferraggine (editors), Encyclopedia of Database Technologies and Applications, pages 367-372, 2005.
  Idea Group Inc., Pennsylvania, USA. ISBN 1-59140-560-2. [bibtex] [pdf]
International journals
1. Heikki Hyyrö, Kimmo Fredriksson, and Gonzalo Navarro.
  Increased Bit-Parallelism for Approximate and Multiple String Matching.
  ACM Journal of Experimental Algorithmics 10, article 2.6, 27 pages, 2005. [abstract] [bibtex] [pdf]
2. Kimmo Fredriksson, Gonzalo Navarro, and Esko Ukkonen.
  Sequential and Indexed Two-Dimensional Combinatorial Template Matching Allowing Rotations.
  Theoretical Computer Science 347(1-2):239-275, 2005. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro and Jorma Tarhio.
  LZgrep: A Boyer-Moore String Matching Tool for Ziv-Lempel Compressed Text.
  Software Practice and Experience 35(12):1107-1130, 2005. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro and Nieves Brisaboa.
  New Bounds on D-ary Optimal Codes.
  Information Processing Letters 96(5):178-184, 2005. [abstract] [bibtex] [pdf]
5. Veli Mäkinen and Gonzalo Navarro.
  Succinct Suffix Arrays based on Run-Length Encoding.
  Nordic Journal of Computing 12(1):40-66, 2005 [abstract] [bibtex] [pdf]
6. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen.
  Transposition Invariant String Matching.
  Journal of Algorithms 56(2):124-153, 2005. [abstract] [bibtex] [pdf]
7. Kjell Lemström, Gonzalo Navarro and Yoan Pinzon.
  Practical Algorithms for Transposition-Invariant String-Matching.
  Journal of Discrete Algorithms 3(2-4):267-292, 2005. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro, Erkki Sutinen and Jorma Tarhio.
  Indexing Text with Approximate q-grams.
  Journal of Discrete Algorithms 3(2-4):157-175, 2005. [abstract] [bibtex] [pdf]
9. Maxime Crochemore, Costas Iliopoulos, Gonzalo Navarro, Yoan Pinzon and Alejandro Salinger.
  Bit-parallel (delta,gamma)-Matching Suffix Automata.
  Journal of Discrete Algorithms 3(2-4):198-214, 2005. [abstract] [bibtex] [pdf]
10. Edgar Chávez and Gonzalo Navarro.
  A Compact Space Decomposition for Effective Metric Indexing.
  Pattern Recognition Letters 26(9):1363-1376, 2005. [abstract] [bibtex] [pdf]
11. Heikki Hyyrö and Gonzalo Navarro.
  Bit-Parallel Witnesses and their Applications to Approximate String Matching.
  Algorithmica 41(3):203-231, 2005. [abstract] [bibtex] [pdf] [fix]
National and regional journals
1. Roberto Uribe, Fabián Granero, and Gonzalo Navarro.
  Voronoi-Tree: Optimización y Dinamismo. In Spanish.
  Revista de la SCCC, 6(1), 2005. Chile. [abstract] [bibtex] [pdf]
International conferences
1. Gilberto Gutiérrez, Gonzalo Navarro, Andrea Rodríguez, Alejandro González, and José Orellana.
  A Spatio-Temporal Access Method based on Snapshots and Events.
  Proc. ACM GIS'05, pages 115-124. [abstract] [bibtex] [pdf]
2. Diego Arroyuelo and Gonzalo Navarro.
  Space-efficient Construction of LZ-index.
  Proc. ISAAC'05, pages 1143-1152. LNCS 3827. [abstract] [bibtex] [pdf]
3. Edgar Chávez, Karina Figueroa, and Gonzalo Navarro.
  Proximity Searching in High Dimensional Spaces with a Proximity Preserving Order.
  Proc. MICAI'05, pages 405-414. LNAI 3789. [abstract] [bibtex] [pdf]
4. Kimmo Fredriksson, Veli Mäkinen, and Gonzalo Navarro.
  Flexible Music Retrieval in Sublinear Time.
  Proc. PSC'05, pages 174-188. [abstract] [bibtex] [pdf]
5. Heikki Hyyrö and Gonzalo Navarro.
  Bit-Parallel Computation of Local Similarity Score Matrices with Unitary Weights.
  Proc. PSC'05, pages 95-108. [abstract] [bibtex] [pdf]
6. Szymon Grabowski, Veli Mäkinen, Gonzalo Navarro, and Alejandro Salinger.
  A Simple Alphabet-Independent FM-Index.
  Proc. PSC'05, pages 230-244. [abstract] [bibtex] [pdf]
7. Joaquín Adiego, Pablo de la Fuente, and Gonzalo Navarro.
  Combining Structural and Textual Contexts for Compressing Semistructured Databases.
  Proc. ENC'05, pages 68-73. IEEE CS Press. [abstract] [bibtex] [pdf]
8. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Efficiently Decodable and Searchable Natural Language Adaptive Compression.
  Proc. SIGIR'05, pages 234-241. [abstract] [bibtex] [pdf]
9. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Compressing Dynamic Text Collections via Phrase-Based Coding.
  Proc. ECDL'05, pages 462-474. LNCS 3652. [abstract] [bibtex] [pdf]
10. Veli Mäkinen and Gonzalo Navarro.
  Succinct Suffix Arrays based on Run-Length Encoding.
  Proc. CPM'05, pages 45-56. LNCS 3537. [abstract] [bibtex] [pdf]
11. Rodrigo González, Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro.
  Practical Implementation of Rank and Select Queries.
  Poster Proceedings Volume of WEA'05, pages 27-38 (poster). CTI Press and Ellinika Grammata (Greece). [abstract] [bibtex] [pdf]
12. Carlos Avendaño, Claudia Feregrino and Gonzalo Navarro.
  Approximate Searching on Compressed Text.
  Proc. CONIELECOMP'05, pages 258-261. IEEE CS Press. [abstract] [bibtex] [pdf]
National and regional conferences
1. Roberto Uribe, Fabián Granero, and Gonzalo Navarro.
  Voronoi-Tree: Optimización y Dinamismo. In Spanish.
  Proc. Encuentro Chileno de Computación, JCC'05, 2005. In CD-ROM. [abstract] [bibtex] [pdf]
2. Verónica Ludueña and Gonzalo Navarro.
  Utilización de un Indice Métrico para Búsqueda Aproximada de Patrones. In Spanish.
  Proc. CACIC'05. [abstract] [bibtex] [pdf]
3. Marcelo Barroso, Gonzalo Navarro and Nora Reyes.
  Combinando Clustering con Aproximación Espacial para Búsquedas en Espacios Métricos. In Spanish.
  Proc. CACIC'05. [abstract] [bibtex] [pdf]

2004 (27)

International books
1. Gonzalo Navarro, editor.
  Proceedings of the XXIV International Conference of the Chilean Computer Science Society (SCCC 2004).
  Arica, Chile, November 2004. IEEE Computer Science Press. [bibtex] [contents]
International book chapters
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  Modeling Text Databases.
  In R. Baeza-Yates, J. Glaz, H. Gzyl, J. Husler and J.L. Palacios (editors), Recent Advances in Applied Probability.
  Springer, pages 1-25, 2004. [abstract] [bibtex]
2. Lucian Ilie, Gonzalo Navarro, and Sheng Yu.
  On NFA reductions.
  In J. Karhumaki, H. Maurer, G. Paun, G. Rozenberg (editors), Theory is Forever (Salomaa Festschrift).
  Lecture Notes in Computer Science 3113, Springer-Verlag, Berlin, Heidelberg, 2004, pages 112-124. [abstract] [bibtex]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  Text Searching: Theory and Practice.
  In C. Martin-Vide, V. Mitrana and G. Paun (editors), Formal Languages and Applications.
  Springer, Berlin, 2004, pages 565-597. ISBN 3-540-20907-7. [bibtex]
International journals
1. Gonzalo Navarro.
  Approximate Regular Expression Searching with Arbitrary Integer Weights.
  Nordic Journal of Computing 11(4): 356-373, 2004. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Mathieu Raffinot.
  New Techniques for Regular Expression Searching.
  Algorithmica 41(2):89-116, 2004. [abstract] [bibtex] [pdf]
3. Kimmo Fredriksson and Gonzalo Navarro.
  Average-Optimal Single and Multiple Approximate String Matching.
  ACM Journal of Experimental Algorithmics 9, article 1.4, 45 pages, 2004. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  Pattern Matching.
  Journal of Applied Statistics 31(8):925-949, 2004. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro and Mathieu Raffinot.
  Practical and Flexible Pattern Matching over Ziv-Lempel Compressed Text.
  Journal of Discrete Algorithms 2(3):347-371, 2004. [abstract] [bibtex] [pdf]
6. Gonzalo Navarro and Kimmo Fredriksson.
  Average Complexity of Exact and Approximate Multiple String Matching.
  Theoretical Computer Science 321(2-3):283-290, 2004. [abstract] [bibtex] [pdf] [fix]
7. Benjamin Bustos and Gonzalo Navarro.
  Probabilistic Proximity Search Algorithms Based on Compact Partitions.
  Journal of Discrete Algorithms 2(1):115-134, 2004. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro.
  Indexing Text using the Ziv-Lempel Trie.
  Journal of Discrete Algorithms 2(1):87-114, 2004. [abstract] [bibtex] [pdf]
International conferences
1. Veli Mäkinen, Gonzalo Navarro and Kunihiko Sadakane.
  Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.
  Proc. ISAAC'04, pages 681-692. LNCS 3341. [abstract] [bibtex] [pdf]
2. Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro.
  An Alphabet-Friendly FM-index.
  Proc. SPIRE'04, pages 150-160. LNCS 3246. [abstract] [bibtex] [pdf]
3. Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro.
  First Huffman, then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index.
  Proc. SPIRE'04 (abstract), pages 210-211. LNCS 3246. [bibtex] [pdf]
4. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
  Simple, Fast, and Efficient Natural Language Adaptive Compression.
  Proc. SPIRE'04, pages 230-241. LNCS 3246. [abstract] [bibtex] [pdf]
5. Kjell Lemström, Gonzalo Navarro, and Yoan Pinzon.
  Bit-Parallel Branch and Bound Algorithm for Transposition Invariant LCS.
  Proc. SPIRE'04 (abstract), pages 74-75. LNCS 3246. [bibtex] [pdf]
6. Veli Mäkinen and Gonzalo Navarro.
  Run-length FM-index (abstract).
  Proc. DIMACS Workshop: ``The Burrows-Wheeler Transform: Ten Years Later'', August 19-20, 2004, pages 17-19. [abstract] [bibtex] [pdf]
7. Kimmo Fredriksson and Gonzalo Navarro.
  Improved Single and Multiple Approximate String Matching.
  Proc. CPM'04, pages 457-471. LNCS 3109. [abstract] [bibtex] [pdf]
8. Veli Mäkinen and Gonzalo Navarro.
  Compressed Compact Suffix Arrays.
  Proc. CPM'04, pages 420-433. LNCS 3109. [abstract] [bibtex] [pdf]
9. Heikki Hyyrö, Kimmo Fredriksson and Gonzalo Navarro.
  Increased Bit-Parallelism for Approximate String Matching.
  Proc. WEA'04, pages 285-298. LNCS 3059. [abstract] [bibtex] [pdf]
10. Joaquín Adiego, Gonzalo Navarro and Pablo de la Fuente.
  Lempel-Ziv Compression of Structured Text.
  Proc. DCC'04, pages 112-121. [abstract] [bibtex] [pdf]
11. Joaquín Adiego, Pablo de la Fuente and Gonzalo Navarro.
  Merging Prediction by Partial Matching with Structural Contexts Model.
  Proc. DCC'04, page 522 (poster). [bibtex] [pdf]
12. Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro.
  Rotation and Lighting Invariant Template Matching.
  Proc. LATIN'04, pages 39-48. LNCS 2976. [abstract] [bibtex] [pdf]
National and regional conferences
1. Carlos Avendaño, Claudia Feregrino, and Gonzalo Navarro.
  Mejorando un Algoritmo para Búsqueda Aproximada.
  Proc. CIC'04. In Spanish. [abstract] [bibtex] [pdf]
2. Gilberto Gutiérrez, Gonzalo Navarro and Andrea Rodríguez.
  An Access Method for Objects Moving among Fixed Regions.
  Proc. III Chilean Database Workshop, JCC'04. In CD-ROM. [abstract] [bibtex] [pdf]
3. Joaquín Adiego, Pablo de la Fuente and Gonzalo Navarro.
  Una Técnica de Compresión para Documentos de Texto Considerando su Estructura.
  Proc. JISBD'04, pages 399-410. In Spanish. [abstract] [bibtex] [pdf]

2003 (32)

International book chapters
1. Ricardo Baeza-Yates, Benjamin Bustos, Edgar Chávez, Norma Herrera and Gonzalo Navarro.
  Clustering in Metric Spaces with Applications to Information Retrieval.
  In W. Wu, H. Xiong and S. Shekhar (editors), Clustering and Information Retrieval.
  Kluwer Academic Publishers, 2003, pages 1-34. ISBN 1-4020-7682-7. [bibtex]
National and regional book chapters
1. Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro and Eva Lorenzo Iglesias.
  Compresión de Textos en Bases de Datos Digitales.
  In N. Brisaboa (editor), Ingeniería del Software en la Década del 2000.
  Tórculo Artes Gráficas, 2003, pages 169-180. ISBN 84-9602307-9. (Spain) [abstract] [bibtex]
International journals
1. Gonzalo Navarro, Ricardo Baeza-Yates and Jo�o Marcelo Arcoverde.
  Matchsimile: A Flexible Approximate Matching Tool for Searching Proper Names.
  Journal of the American Society for Information Systems and Technology 54(1):3-15, 2003. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro.
  Regular Expression Searching on Compressed Text.
  Journal of Discrete Algorithms 1(5/6):423-443, 2003. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro and Mathieu Raffinot.
  Fast and Simple Character Classes and Bounded Gaps Pattern Matching, with Applications to Protein Searching.
  Journal of Computational Biology 10(6):903-923, 2003. [abstract] [bibtex] [pdf]
4. Juha Kärkkäinen, Gonzalo Navarro and Esko Ukkonen.
  Approximate String Matching on Ziv-Lempel Compressed Text.
  Journal of Discrete Algorithms 1(3/4): 313-338, 2003 [abstract] [bibtex] [pdf]
5. Josué Kuri, Ludovic Mé and Gonzalo Navarro.
  Fast Multipattern Search Algorithms for Intrusion Detection.
  Fundamenta Informaticae 56(1-2): 23-49, 2003. [abstract] [bibtex] [pdf]
6. Benjamin Bustos, Gonzalo Navarro and Edgar Chávez.
  Pivot Selection Techniques for Proximity Searching in Metric Spaces.
  Pattern Recognition Letters 24(14):2357-2366, 2003. [abstract] [bibtex] [pdf]
7. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen.
  Approximate Matching of Run-Length Compressed Strings.
  Algorithmica 35:347-369, 2003. [abstract] [bibtex] [pdf]
8. Edgar Chávez and Gonzalo Navarro.
  Probabilistic Proximity Search: Fighting the Curse of Dimensionality in Metric Spaces.
  Information Processing Letters 85:39-46, 2003. [abstract] [bibtex] [pdf]
9. Jayme Szwarcfiter, Gonzalo Navarro, Ricardo Baeza-Yates, Joísa de S. Oliveira, Walter Cunto and Nivio Ziviani.
  Optimal Binary Search Trees with Costs Depending on the Access Paths.
  Theoretical Computer Science (TCS A) 290(3):1799-1814, 2003. [abstract] [bibtex] [pdf]
International conferences
1. Gonzalo Navarro.
  Approximate Regular Expression Searching with Arbitrary Integer Weights.
  Proc. ISAAC'03, pages 230-239. LNCS 2906 [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Nora Reyes.
  Improved Deletions in Dynamic Spatial Approximation Trees.
  Proc. SCCC'03, pages 13-22. [abstract] [bibtex] [pdf]
3. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen.
  Matching Numeric Strings under Noise.
  Proc. PSC'03, pages 99-110. [abstract] [bibtex] [pdf]
4. Kjell Lemström and Gonzalo Navarro.
  Flexible and Efficient Bit-Parallel Techniques for Transposition Invariant Approximate Matching in Music Retrieval.
  Proc. SPIRE'03, pages 224-237. LNCS 2857. [abstract] [bibtex] [pdf]
5. Maxime Crochemore, Costas Iliopoulos, Gonzalo Navarro and Yoan Pinzón.
  A Bit-parallel Suffix Automaton Approach for (delta,gamma)-Matching in Music Retrieval.
  Proc. SPIRE'03, pages 211-223. LNCS 2857. [abstract] [bibtex] [pdf]
6. Joaquín Adiego, Gonzalo Navarro and Pablo de la Fuente.
  SCM: Structural Contexts Model for Improving Compression in Semistructured Text Databases.
  Proc. SPIRE'03, pages 153-167. LNCS 2857. [abstract] [bibtex] [pdf]
7. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro and María Esteller.
  (S,C)-Dense Coding: An Optimized Compression Code for Natural Language Text Databases.
  Proc. SPIRE'03, pages 122-136. LNCS 2857. [abstract] [bibtex] [pdf]
8. Mauricio Marín and Gonzalo Navarro.
  Distributed Query Processing using Suffix Arrays.
  Proc. SPIRE'03, pages 311-325. LNCS 2857. [abstract] [bibtex] [pdf]
9. Diego Arroyuelo, Francisca Muñoz, Gonzalo Navarro and Nora Reyes.
  Memory-Adaptative Dynamic Spatial Approximation Trees.
  Proc. SPIRE'03, pages 360-368 (short paper). LNCS 2857. [abstract] [bibtex] [pdf]
10. Heikki Hyyrö and Gonzalo Navarro.
  A Practical Index for Genome Searching.
  Proc. SPIRE'03, pages 341-349 (short paper). LNCS 2857. [abstract] [bibtex] [pdf]
11. Mauricio Marín and Gonzalo Navarro.
  Suffix Arrays in Parallel.
  Proc. EuroPar'03, pages 338-341 (short paper). LNCS 2790. [abstract] [bibtex] [pdf]
12. Kimmo Fredriksson and Gonzalo Navarro.
  Average-Optimal Multiple Approximate String Matching.
  Proc. CPM'03, pages 109-128. LNCS 2676. [abstract] [bibtex] [pdf]
13. Gonzalo Navarro and Rodrigo Paredes.
  Practical Construction of Metric t-Spanners.
  Proc. ALENEX'03, pages 69-81. SIAM Press. [abstract] [bibtex] [pdf]
14. Nieves Brisaboa, Eva Iglesias, Gonzalo Navarro and José Paramá.
  An Efficient Compression Code for Text Databases.
  Proc. ECIR'03, pages 468-481. LNCS 2633. [abstract] [bibtex] [pdf]
15. Joaquín Adiego, Gonzalo Navarro and Pablo de la Fuente.
  Compressing Semistructured Text Databases.
  Proc. ECIR'03, pages 482-490 (short paper). LNCS 2633. [abstract] [bibtex] [pdf]
16. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen.
  Algorithms for Transposition Invariant String Matching.
  Proc. STACS'03, pages 191-202. LNCS 2607. [abstract] [bibtex] [pdf]
National and regional conferences
1. Joaquín Adiego, Gonzalo Navarro and Pablo de la Fuente.
  Applying the Contexts Model in Semistructured Text Databases.
  Proc. IWPAAMS'03, pages 25-38. [abstract] [bibtex] [pdf]
2. Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro, Eva Lorenzo Iglesias, José Paramá and María F. Esteller.
  Codificación (s,c)-Densa: Optimizando la Compresión de Texto en Lenguaje Natural.
  Proc. JISBD'03, pages 737-746, 2003. In Spanish. [abstract] [bibtex] [pdf]
3. Eva Lorenzo Iglesias, Nieves R. Brisaboa, José R. Paramá, Antonio Fariña, Gonzalo Navarro and María F. Esteller.
  Usando Técnicas de Compresión de Textos en Bibliotecas Digitales.
  Proc. JBIDI'03, pages 39-48, 2003. In Spanish. [abstract] [bibtex] [pdf]
4. Roberto Uribe and Gonzalo Navarro.
  Una Estructura Dinámica para Búsqueda en Espacios Métricos.
  In Spanish. Proc. Encuentro Chileno de Computación, JCC'03, 2003. In CD-ROM. [abstract] [bibtex] [pdf]
5. Diego Arroyuelo, Gonzalo Navarro and Nora Reyes.
  Fully Dynamic and Memory-Adaptative Spatial Approximation Trees.
  Proc. CACIC'03, pages 1502-1513. [abstract] [bibtex] [pdf]

2002 (16)

International books
1. Gonzalo Navarro and Mathieu Raffinot.
  Flexible Pattern Matching in Strings -- Practical on-line search algorithms for texts and biological sequences.
  Cambridge University Press, 2002 [Web page] [bibtex]
International book chapters
1. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen.
  Faster than FFT: Rotation Invariant Combinatorial Template Matching.
  In S. Pandalai (editor),
  Recent Research Developments in Pattern Recognition, vol. II.
  Transworld Research Network, 2002, pages 75-112. [bibtex]
2. Ricardo Baeza-Yates, Alistair Moffat and Gonzalo Navarro.
  Searching Large Text Collections.
  In J. Abello, P. Pardalos and M. Resende (editors), Handbook of Massive Data Sets.
  Kluwer Academic Publishers, 2002, pages 195-244. [bibtex]
International journals
1. Gonzalo Navarro.
  Searching in Metric Spaces by Spatial Approximation.
  The VLDB Journal 11(1):28-46, 2002. [abstract] [bibtex] [pdf]
2. Ricardo Baeza-Yates and Gonzalo Navarro.
  XQL and Proximal Nodes.
  Journal of the American Society for Information Systems and Technology 53(6):504-514, 2002. [abstract] [bibtex] [pdf]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  New and Faster Filters for Multiple Approximate String Matching.
  Random Structures and Algorithms 20:23-49, 2002. [abstract] [bibtex] [pdf]
International conferences
1. Maxime Crochemore and Gonzalo Navarro.
  Improved Antidictionary Based Compression.
  Proc. SCCC'02. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro.
  Indexing Text using the Ziv-Lempel Trie.
  Proc. SPIRE'02, pages 325-336. LNCS 2476. [abstract] [bibtex] [pdf]
3. Benjamin Bustos and Gonzalo Navarro.
  Probabilistic Proximity Searching Algorithms Based on Compact Partitions.
  Proc. SPIRE'02, pages 284-297. LNCS 2476. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro, Rodrigo Paredes and Edgar Chávez.
  t-Spanners as a Data Structure for Metric Space Searching.
  Proc. SPIRE'02, pages 298-309. LNCS 2476. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro and Nora Reyes.
  Fully Dynamic Spatial Approximation Trees.
  Proc. SPIRE'02, pages 254-270. LNCS 2476. [abstract] [bibtex] [pdf]
6. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen.
  Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations.
  Proc. CPM'02. LNCS 2373. [abstract] [bibtex] [pdf]
7. Heikki Hyyrö and Gonzalo Navarro.
  Faster Bit-parallel Approximate String Matching.
  Proc. CPM'02. LNCS 2373. [abstract] [bibtex] [pdf]
8. Edgar Chávez and Gonzalo Navarro.
  A Metric Index for Approximate String Matching.
  Proc. LATIN'02, pages 181-195, 2002. LNCS 2286. [abstract] [bibtex] [pdf]
National and regional conferences
1. Gonzalo Navarro and Nora Reyes.
  Improved Dynamic Spatial Approximation Trees.
  Proc. CLEI'02, page 74 (abstract, full papers in CD-Rom) [abstract] [bibtex] [pdf]
2. Nora Reyes and Gonzalo Navarro.
  Eliminación en Arboles de Aproximación Espacial Dinámicos. In Spanish.
  Proc. CACIC'02, Argentina, pages 821-833. [abstract] [bibtex] [pdf]

2001 (17)

International books
1. Gonzalo Navarro, editor.
  Proceedings of the 8th International Symposium on String Processing and Information Retrieval (SPIRE 2001).
  Laguna de San Rafael, Chile, November 2001. IEEE Computer Science Press. [bibtex] [frontmatter] [contents]
International journals
1. Gonzalo Navarro, Ricardo Baeza-Yates, Erkki Sutinen and Jorma Tarhio.
  Indexing Methods for Approximate String Matching.
  IEEE Data Engineering Bulletin 24(4):19-27, 2001. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro.
  NR-grep: a Fast and Flexible Pattern Matching Tool.
  Software Practice and Experience 31:1265-1312, 2001. [abstract] [bibtex] [pdf]
3. Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates and José Luis Marroquín.
  Searching in Metric Spaces.
  ACM Computing Surveys 33(3):273-321, 2001. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  A Guided Tour to Approximate String Matching.
  ACM Computing Surveys 33(1):31-88, 2001. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro and Ricardo Baeza-Yates.
  Improving an Algorithm for Approximate Pattern Matching.
  Algorithmica 30(4):473-502, 2001. [abstract] [bibtex] [pdf]
6. Edgar Chávez, José Luis Marroquín and Gonzalo Navarro.
  Fixed Queries Array: A Fast and Economical Data Structure for Proximity Searching.
  Multimedia Tools and Applications, 14(2):113-135, 2001. [abstract] [bibtex] [pdf]
International conferences
1. Benjamin Bustos, Gonzalo Navarro and Edgar Chávez.
  Pivot Selection Techniques for Proximity Searching in Metric Spaces.
  Proc. SCCC'01, pages 33-40, 2001. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Nora Reyes.
  Dynamic Spatial Approximation Trees.
  Proc. SCCC'01, pages 213-222, 2001. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro and Mathieu Raffinot.
  Compact DFA Representation for Fast Regular Expression Search.
  Proc. WAE'01, 2001. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  Regular Expression Searching over Ziv-Lempel Compressed Text.
  Proc. CPM'01, pages 1-17, 2001. LNCS 2089. [abstract] [bibtex] [pdf]
5. Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen.
  Approximate Matching of Run-length Compressed Strings.
  Proc. CPM'01, pages 31-49, 2001. LNCS 2089. [abstract] [bibtex] [pdf]
6. Edgar Chávez and Gonzalo Navarro.
  A Probabilistic Spell for the Curse of Dimensionality.
  Proc. ALENEX'01, pages 147-160, 2001. LNCS 2153. [abstract] [bibtex] [pdf]
7. Gonzalo Navarro and Mathieu Raffinot.
  Fast and Simple Character Classes and Bounded Gaps Pattern Matching, with Application to Protein Searching.
  Proc. RECOMB'01, pages 231-240, 2001. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro, Takuya Kida, Masayuki Takeda, Ayumi Shinohara and Setsuo Arikawa.
  Faster Approximate String Matching over Compressed Text.
  Proc. DCC'01, 2001, pages 459-468. [abstract] [bibtex] [pdf]
National and regional conferences
1. Gonzalo Navarro, Ricardo Baeza-Yates and Jo�o Marcelo Arcoverde.
  Matchsimile: A Flexible Approximate Matching Tool for Personal Names Searching.
  Proc. SBBD'01, pages 228-242, 2001. [abstract] [bibtex] [pdf]
2. Edgar Chávez and Gonzalo Navarro.
  Towards Measuring the Searching Complexity of Metric Spaces.
  Proc. ENC'01, vol. II, pages 969-978, 2001. [abstract] [bibtex] [pdf]

2000 (19)

International journals
1. Nivio Ziviani, Edleno de Moura, Gonzalo Navarro and Ricardo Baeza-Yates.
  Compression: A Key for Next-Generation Text Retrieval Systems.
  IEEE Computer 33(11):37-44 (cover feature), 2000. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Mathieu Raffinot.
  Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata.
  ACM Journal of Experimental Algorithmics 5(4), 36 pages, 2000. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro and Ricardo Baeza-Yates.
  A Hybrid Indexing Method for Approximate String Matching.
  Journal of Discrete Algorithms 1(1):21-49, 2000. [abstract] [bibtex] [pdf]
4. Ricardo Baeza-Yates and Gonzalo Navarro.
  New Models and Algorithms for Multidimensional Approximate Pattern Matching.
  Journal of Discrete Algorithms 1(1):205-239, 2000. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro, Edleno de Moura, Marden Neubert, Nivio Ziviani and Ricardo Baeza-Yates.
  Adding Compression to Block Addressing Inverted Indexes.
  Information Retrieval 3(1):49-77, 2000. [abstract] [bibtex] [pdf]
6. Edleno de Moura, Gonzalo Navarro, Nivio Ziviani and Ricardo Baeza-Yates.
  Fast and Flexible Word Searching on Compressed Text.
  ACM Transactions on Information Systems 18(2):113-139, 2000. [abstract] [bibtex] [pdf] [fix]
7. Gonzalo Navarro.
  Improved Approximate Pattern Matching on Hypertext.
  Theoretical Computer Science, 237:455-463, 2000. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro, Ricardo Baeza-Yates, Eduardo Barbosa, Nivio Ziviani and Walter Cunto.
  Binary Searching with Non-uniform Costs and Its Application to Text Retrieval.
  Algorithmica, 27(2):145-169, 2000. [abstract] [bibtex] [pdf]
9. Ricardo Baeza-Yates and Gonzalo Navarro.
  Block Addressing Indices for Approximate Text Retrieval.
  Journal of the American Society for Information Science, 51(1):69-82, 2000. [abstract] [bibtex] [pdf]
International conferences
1. Nancy Hitschfeld, Gonzalo Navarro and Rodrigo Farías.
  Tesselations of Cuboids with Steiner Points.
  Proc. 9th International Meshing Roundtable, 2000, pages 275-282. [abstract] [bibtex] [pdf]
2. Josué Kuri, Gonzalo Navarro, Ludovic Mé and Laurent Heye.
  A Pattern Matching Based Filter for Audit Reduction and Fast Detection of Potential Intrusions.
  Proc. RAID'2000, pages 17-21. LNCS 1907. [abstract] [bibtex] [pdf]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  XQL and Proximal Nodes (Preliminary Version).
  Proc. XML Workshop of SIGIR'2000, [abstract] [bibtex] [pdf]
4. Edgar Chávez and Gonzalo Navarro.
  An Effective Clustering Algorithm to Index High Dimensional Metric Spaces.
  Proc. SPIRE'2000, pages 75-86, 2000. [abstract] [bibtex] [pdf]
5. Josué Kuri and Gonzalo Navarro.
  Fast Multipattern Search Algorithms for Intrusion Detection.
  Proc. SPIRE'2000, pages 169-180, 2000. [abstract] [bibtex] [pdf]
6. Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen.
  An Index for Two Dimensional String Matching Allowing Rotations.
  Proc. IFIP TCS'2000, pages 59-75, 2000. LNCS 1872. [abstract] [bibtex] [pdf]
7. Juha Kärkkäinen, Gonzalo Navarro and Esko Ukkonen.
  Approximate String Matching over Ziv-Lempel Compressed Text.
  Proc. CPM'2000, LNCS 1848. Pages 195-209, 2000. [abstract] [bibtex] [pdf]
8. Gonzalo Navarro and Jorma Tarhio.
  Boyer-Moore String Matching over Ziv-Lempel Compressed Text.
  Proc. CPM'2000, LNCS 1848. Pages 166-180, 2000. [abstract] [bibtex] [pdf]
9. Gonzalo Navarro, Erkki Sutinen, Jani Tanninen and Jorma Tarhio.
  Indexing Text with Approximate q-grams.
  Proc. CPM'2000, LNCS 1848. Pages 350-363, 2000. [abstract] [bibtex] [pdf]
National and regional conferences
1. Virna Cuquejo, Ricardo Baeza-Yates and Gonzalo Navarro.
  Algoritmos y Estructuras de Datos para Búsqueda de Objetos Similares. In Spanish.
  Proc. Encuentro Chileno de Computación, JCC'00, 2000. [abstract] [bibtex] [pdf]

1999 (14)

International book chapters
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  Query Languages.
  In Modern Information Retrieval. Addison-Wesley, 1999. [bibtex]
2. Ricardo Baeza-Yates and Gonzalo Navarro.
  Indexing and Searching.
  In Modern Information Retrieval. Addison-Wesley, 1999. [bibtex]
International journals
1. Gonzalo Navarro and Ricardo Baeza-Yates.
  Very Fast and Simple Approximate String Matching.
  Information Processing Letters 72: 65-70, 1999. [abstract] [bibtex] [pdf]
2. Ricardo Baeza-Yates, Ricard Gavaldá, Gonzalo Navarro and Rodrigo Scheihing.
  Bounding the Expected Length of Longest Common Subsequences and Forests.
  Theory of Computing Systems 32(4):435-452, 1999. [abstract] [bibtex] [pdf]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  Faster Approximate String Matching.
  Algorithmica 23(2):127-158, 1999. [abstract] [bibtex] [pdf]
International conferences
1. Gonzalo Navarro and Ricardo Baeza-Yates.
  Fast Multi-Dimensional Approximate String Matching.
  Proc. CPM'99, LNCS 1645. Pages 243-257, 1999. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Ricardo Baeza-Yates.
  A New Indexing Method for Approximate String Matching.
  Proc. CPM'99, LNCS 1645. Pages 163-185, 1999. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro and Mathieu Raffinot.
  A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text.
  Proc. CPM'99, LNCS 1645. Pages 14-36, 1999. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro and Mathieu Raffinot.
  Fast Regular Expression Search.
  Proc. WAE'99, LNCS 1668. Pages 198-212, 1999. [abstract] [bibtex] [pdf]
5. Edgar Chávez, José Luis Marroquín and Gonzalo Navarro.
  Overcoming the Curse of Dimensionality.
  Proc. CBMI'99, pages 57-64, 1999. [abstract] [bibtex] [pdf]
6. Gonzalo Navarro.
  Searching in Metric Spaces by Spatial Approximation.
  Proc. SPIRE'99. IEEE CS Press, pages 141-148. [abstract] [bibtex] [pdf]
7. Edleno de Moura, Gonzalo Navarro and Nivio Ziviani.
  Linear Time Sorting of Skewed Distributions.
  Proc. SPIRE'99. IEEE CS Press, pages 135-140. [abstract] [bibtex] [pdf]
8. Jo�o Paulo Kitajima and Gonzalo Navarro.
  A Fast Distributed Suffix Array Generation Algorithm.
  Proc. SPIRE'99. IEEE CS Press, pages 97-104. [abstract] [bibtex] [pdf]
National and regional conferences
1. Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates and José Luis Marroquín.
  A Unified Model for Similarity Searching.
  Proc. ENC'99. [abstract] [bibtex] [pdf]

1998 (13)

Theses
1. Gonzalo Navarro.
  Approximate Text Searching.
  PhD thesis, Dept. of Computer Science, Univ. of Chile, 1998. Ricardo Baeza-Yates, advisor.
  [abstract] [bibtex] [pdf (250 pages)]
  (for the English part, strip off the first few Spanish pages).
  The abstract has appeared in EATCS Bulletin 67, pages 278-282, Feb 1999.
International journals
1. Gonzalo Navarro and Ricardo Baeza-Yates.
  A Practical q-Gram Index for Text Retrieval Allowing Errors.
  CLEI Electronic Journal 1(2), 1998. [abstract] [bibtex] [pdf]
International conferences
1. Edleno de Moura, Gonzalo Navarro, Nivio Ziviani and Ricardo Baeza-Yates.
  Fast Searching on Compressed Text Allowing Errors.
  Proc. SIGIR'98, pages 298-306, 1998. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Mathieu Raffinot.
  A Bit-parallel approach to Suffix Automata: Fast Extended String Matching.
  Proc. CPM'98, LNCS 1448. Pages 14-33, 1998. [abstract] [bibtex] [pdf]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  Fast Two-Dimensional Approximate Pattern Matching.
  Proc. LATIN'98, LNCS 1380. Pages 341-351. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  Improved Approximate Pattern Matching on Hypertext.
  Proc. LATIN'98, LNCS 1380. Pages 352-357. [abstract] [bibtex] [pdf]
5. Edleno de Moura, Gonzalo Navarro, Nivio Ziviani and Ricardo Baeza-Yates.
  Direct Pattern Matching on Compressed Text.
  Proc. SPIRE'98. IEEE CS Press, pages 90-95. [abstract] [bibtex] [pdf]
6. Ricardo Baeza-Yates and Gonzalo Navarro.
  Fast Approximate String Matching in a Dictionary.
  Proc. SPIRE'98. IEEE CS Press, pages 14-22. [abstract] [bibtex] [pdf]
7. Ricardo Baeza-Yates, Gonzalo Navarro, Jesús Vegas and Pablo de la Fuente.
  A Model and a Visual Query Language for Structured Text.
  Proc. SPIRE'98. IEEE CS Press, pages 7-13. [abstract] [bibtex] [pdf]
8. Berthier Ribeiro, Jo�o Paulo Kitajima, Gonzalo Navarro, Cláudio Sant'Ana and Nivio Ziviani.
  Parallel Generation of Inverted Lists for Distributed Text Collections.
  Proc. SCCC'98, pages 149-157. [abstract] [bibtex] [pdf]
9. Autran Mac�do, Marco Cristo, Elaine Silva, Denilson Barbosa, Jo�o Paulo Kitajima, Berthier Ribeiro, Gonzalo Navarro and Nivio Ziviani.
  Experimental Analysis of a Parallel Quicksort-Based Algorithm for Suffix Array Generation.
  Proc. VECPAR'98, pages 1049-1062. [abstract] [bibtex] [pdf]
National and regional conferences
1. Ricardo Baeza-Yates, Gonzalo Navarro, Jesús Vegas and Pablo de la Fuente.
  Un Lenguaje de Consulta Intuitivo para Textos Estructurados. In Spanish.
  Proc. JI'98, pages 527-536, 1998. [abstract] [bibtex] [pdf]
2. Virna Cuquejo, Ricardo Baeza-Yates, and Gonzalo Navarro.
  Algoritmos y Estructuras de Datos para Búsqueda de Objetos Similares. In Spanish.
  Proc. CITA'98. [abstract] [bibtex] [pdf]

1997 (10)

International journals
1. Gonzalo Navarro and Ricardo Baeza-Yates.
  Proximal Nodes: A Model to Query Document Databases by Content and Structure.
  ACM Transactions on Information Systems 15(4):401-435, 1997. [abstract] [bibtex] [pdf]
International conferences
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  Block Addressing Indices for Approximate Text Retrieval.
  Proc. CIKM'97, pages 1-8. [abstract] [bibtex] [pdf]
2. Ricardo Baeza-Yates and Gonzalo Navarro.
  Multiple Approximate String Matching.
  Proc. WADS'97, LNCS 1272. Pages 174-184. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro, Jo�o Paulo Kitajima, Berthier Ribeiro and Nivio Ziviani.
  Distributed Generation of Suffix Arrays.
  Proc. CPM'97, LNCS 1264. Pages 102-115. [abstract] [bibtex] [pdf]
4. Gonzalo Navarro.
  Multiple Approximate String Matching by Counting.
  Proc. WSP'97. Pages 125-139. [abstract] [bibtex] [pdf]
5. Gonzalo Navarro.
  A Partial Deterministic Automaton for Approximate String Matching.
  Proc. WSP'97. Pages 112-124. [abstract] [bibtex] [pdf]
6. Marcio Araújo, Gonzalo Navarro and Nivio Ziviani.
  Large Text Searching Allowing Errors.
  Proc. WSP'97. Pages 2-20. [abstract] [bibtex] [pdf]
7. Edleno de Moura, Gonzalo Navarro and Nivio Ziviani.
  Indexing Compressed Text.
  Proc. WSP'97. Pages 95-111. [abstract] [bibtex] [pdf]
8. Jo�o Paulo Kitajima, Gonzalo Navarro, Berthier Ribeiro and Nivio Ziviani.
  Distributed Generation of Suffix Arrays: a Quicksort-Based Approach.
  Proc. WSP'97. Pages 53-69. [abstract] [bibtex] [pdf]
National and regional conferences
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  A Practical Index for Text Retrieval Allowing Errors.
  Proc. CLEI'97. Volume 1, pages 273-282. [abstract] [bibtex] [pdf]

1996 (7)

International journals
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  Integrating Contents and Structure in Text Retrieval.
  ACM SIGMOD Record 25(1), March 1996. Pages 67-79. [abstract] [bibtex] [pdf]
International conferences
1. Ricardo Baeza-Yates and Gonzalo Navarro.
  A Faster Algorithm for Approximate String Matching.
  Proc. CPM'96, LNCS 1075. Pages 1-23, 1996. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro.
  An Optimal Index for PAT Arrays.
  Proc. WSP'96. Pages 214-227. [abstract] [bibtex] [pdf]
3. Ricardo Baeza-Yates and Gonzalo Navarro.
  A Fast Heuristic for Approximate String Matching.
  Proc. WSP'96. Pages 47-63. [abstract] [bibtex] [pdf]
4. Ricardo Baeza-Yates, Ricard Gavaldá and Gonzalo Navarro.
  Bounding the Expected Length of Longest Common Subsequences and Forests.
  Proc. WSP'96. Pages 1-15. [abstract] [bibtex] [pdf]
National and regional conferences
1. Gonzalo Navarro.
  Un Lenguaje de Consultas sobre Estructura y Contenido en Bases de Datos de Texto. In Spanish.
  Proc. CLEI'96. Volume 2, pages 1125-1144. [abstract] [bibtex] [pdf]
  First prize in the III CLEI-UNESCO Master's Thesis Contests.
2. Gonzalo Navarro and Ricardo Baeza-Yates.
  A Class of Linear Algorithms to Process Sets of Segments.
  Proc. CLEI'96. Volume 2, pages 671-682. [abstract] [bibtex] [pdf]

1995 (5)

Theses
1. Gonzalo Navarro.
  A Language for Queries on Structure and Contents of Textual Databases.
  MSc. thesis, Dept. of Computer Science, Univ. of Chile, 1995. Ricardo Baeza-Yates, advisor.
  [abstract] [bibtex] [pdf (120 pages)]
International conferences
1. Eduardo Barbosa, Gonzalo Navarro, Ricardo Baeza-Yates, Chris Perleberg and Nivio Ziviani.
  Optimized Binary Search and Text Retrieval.
  Proc. ESA'95, LNCS 979. Pages 311-326. [abstract] [bibtex] [pdf]
2. Gonzalo Navarro and Ricardo Baeza-Yates.
  A Language for Queries on Structure and Contents of Textual Databases.
  Proc. SIGIR'95. Pages 93-101. [abstract] [bibtex] [pdf]
3. Gonzalo Navarro, Eduardo Barbosa, Chris Perleberg, Ricardo Baeza-Yates and Nivio Ziviani.
  Optimized Indirect Binary Search and Text Retrieval (Preliminary Version).
  Proc. WSP'95. Pages 53-67. [abstract] [bibtex] [pdf]
National and regional conferences
1. Gonzalo Navarro and Ricardo Baeza-Yates.
  Expressive Power of a New Model for Structured Text Databases.
  Proc. CLEI'95. Volume 2, pages 1151-1162. [abstract] [bibtex] [pdf]

1994 (1)

International conferences
1. Gonzalo Navarro and Jorge Sanz.
  MediaCore: a Multimedia Interface Composition Toolkit.
  Proc. SCCC'94. Pages 191-201. [abstract] [bibtex] [pdf]