Publications

Here is a list of my publications, together with abstracts, bibtex entries and pdfs. The copyrights belong to the publishers, so I ask you to use these pdfs for your personal use only. For these same reasons, no pdfs are given for books and book chapters once they appear. 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.

There is also available code (most is free).

2010 (0+5)

• International conferences
  1. Jérémy Barbay, Francisco Claude, and Gonzalo Navarro.
     Compact Rich-Functional Binary Relation Representations.
     To appear in Proc. LATIN'10. LNCS. [abstract] [bibtex] [pdf]

  2. Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, and Kunihiko Sadakane.
     Succinct Trees in Practice.
     To appear in Proc. ALENEX'10. [abstract] [bibtex] [pdf]

  3. Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.
     Fast and Compact Prefix Codes.
     To appear in Proc. SOFSEM'10. LNCS. [abstract] [bibtex] [pdf]

  4. 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.
     To appear in Proc. ICDE'10. [abstract] [bibtex] [pdf]

  5. Kunihiko Sadakane and Gonzalo Navarro.
     Fully-Functional Succinct Trees.
     To appear in Proc. SODA'10. [abstract] [bibtex] [pdf]

2009 (26+4)

• 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. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki.
     Storage and Retrieval of Highly Repetitive Sequence Collections.
     To appear in Journal of Computational Biology. [abstract] [bibtex] [pdf]

  2. Nieves Brisaboa, Antonio Fariña, Gonzalo Navarro, and José Paramá.
     Dynamic Lightweight Text Compression.
     To appear in ACM Transactions on Information Systems. [abstract] [bibtex] [pdf]

  3. Gonzalo Navarro and Rodrigo Paredes.
     On Sorting, Heaps, and Minimum Spanning Trees.
     To appear in Algorithmica. [abstract] [bibtex] [pdf]

  4. Rodrigo González and Gonzalo Navarro.
     A Compressed Text Index on Secondary Memory.
     To appear in Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC). [abstract] [bibtex] [pdf]

  5. Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro.
     Faster Entropy-Bounded Compressed Suffix Trees.
     Theoretical Computer Science (TCS) 410(51):5354-5364, 2009. [abstract] [bibtex] [pdf]

  6. 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]

  7. Rodrigo González and Gonzalo Navarro.
     Rank/Select on Dynamic Compressed Sequences and Applications.
     Theoretical Computer Science (TCS) 410(43):4414-4422, 2009. [abstract] [bibtex] [pdf]

  8. Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes.
     Speeding up Spatial Approximation Search in Metric Spaces.
     ACM Journal of Experimental Algorithmics (JEA) 14:article 3.6, 2009. 21 pages. [abstract] [bibtex] [pdf]

  9. Amihood Amir and Gonzalo Navarro.
     Parameterized Matching on Non-linear Structures.
     Information Processing Letters (IPL) 109(15):864-867, 2009. [abstract] [bibtex] [pdf]

  10. Paolo Ferragina, Rodrigo González, Gonzalo Navarro, and Rossano Venturini.
      Compressed Text Indexes: From Theory to Practice.
      ACM Journal of Experimental Algorithmics (JEA) 13:article 12, 2009. 30 pages. [abstract] [bibtex] [pdf]

  11. Benjamin Bustos and Gonzalo Navarro.
      Improving the Space Cost of k-NN Search in Metric Spaces by Using Distance Estimators.
      Multimedia Tools and Applications (MTAP) 41(2):215-233, 2009. [abstract] [bibtex] [pdf]

  12. Gonzalo Navarro.
      Implementing the LZ-index: Theory versus Practice.
      ACM Journal of Experimental Algorithmics (JEA) 13:article 2, 49 pages, 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. Invited paper. [abstract] [bibtex] [pdf] [errata]

  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 (SPE) 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 (TALG) 4(3):article 32, 2008. 38 pages. [abstract] [bibtex] [pdf]

  3. Edgar Chávez, Karina Figueroa, and Gonzalo Navarro.
     Effective Proximity Retrieval by Ordering Permutations.
     IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 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 (JEA) 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] [errata]

  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]

  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 (TALG) 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] [errata]

  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 (JASIST) 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 (IPM) 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]

  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]

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 (IJFCS) 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 (IJFCS) 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 (IJFCS) 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 (TCS) 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]

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 (JEA) 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 (TCS) 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 (SPE) 35(12):1107-1130, 2005. [abstract] [bibtex] [pdf]

  4. Gonzalo Navarro and Nieves Brisaboa.
     New Bounds on D-ary Optimal Codes.
     Information Processing Letters (IPL) 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 (NJC) 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 (JDA) 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 (JDA) 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 (JDA) 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] [errata]

• National 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 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 (JEA) 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 (JDA) 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 (TCS) 321(2-3):283-290, 2004. [abstract] [bibtex] [pdf] [errata]

  7. Benjamin Bustos and Gonzalo Navarro.
     Probabilistic Proximity Search Algorithms Based on Compact Partitions.
     Journal of Discrete Algorithms (JDA) 2(1):115-134, 2004. [abstract] [bibtex] [pdf]

  8. Gonzalo Navarro.
     Indexing Text using the Ziv-Lempel Trie.
     Journal of Discrete Algorithms (JDA) 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 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 (JASIST) 54(1):3-15, 2003. [abstract] [bibtex] [pdf]

  2. Gonzalo Navarro.
     Regular Expression Searching on Compressed Text.
     Journal of Discrete Algorithms (JDA) 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 (JDA) 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 (IPL) 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 (JASIST) 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 (RSA) 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. Invited paper. [abstract] [bibtex] [pdf]

  2. Gonzalo Navarro.
     NR-grep: a Fast and Flexible Pattern Matching Tool.
     Software Practice and Experience (SPE) 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 (MTAP), 14(2):113-135, 2001. Kluwer. [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), November 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 (JEA) 5, article 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 (JDA) 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 (JDA) 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 (TOIS) 18(2):113-139, 2000. [abstract] [bibtex] [pdf]

  7. Gonzalo Navarro.
     Improved Approximate Pattern Matching on Hypertext.
     Theoretical Computer Science (TCS), 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 (JASIS), 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 R. Baeza-Yates and B. Ribeiro,
     Modern Information Retrieval.
     Addison-Wesley, 1999. [bibtex]

  2. Ricardo Baeza-Yates and Gonzalo Navarro.
     Indexing and Searching.
     In R. Baeza-Yates and B. Ribeiro,
     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 (IPL) 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 (TOIS) 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. Invited paper. [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]