Now showing items 21-40 of 104

    • Brisaboa, NievesR; Cerdeira Pena, Ana; Bernardo, Guillermo de; Navarro, Gonzalo (Elsevier, 2017)
      We introduce a dynamic data structure for the compact representation of binary relations R subset of A x B. The data structure is a dynamic variant of the k(2)-tree, a static compact representation that takes advantage of ...
    • Hernández, Cecilia; Navarro, Gonzalo (Springer-Verlag, 2013)
      Compressed representations have become effective to store and access largeWeb and social graphs, in order to support various graph querying and mining tasks. The existing representations exploit various typical patterns ...
    • González González, Rodrigo; Navarro, Gonzalo (2014-01-08)
      We introduce a practical disk-based compressed text index that, when the text is compressible, takes much less space than the suffix array. It provides very good I/O times for searching, which in particular improve when ...
    • González González, Rodrigo; Navarro, Gonzalo (JCMCC, 2009)
      We introduce a practical disk-based compressed text index that, when the text is compressible, takes little more than the plain text size (and replaces it). It provides very good I/O times for searching, which in particular ...
    • González González, Rodrigo; Navarro, Gonzalo (Springer Berlin Heidelberg, 2007)
      Compressed text (self-)indexes have matured up to a point where they can replace a text by a data structure that requires less space and, in addition to giving access to arbitrary text passages, support indexed text ...
    • Álvarez García, Sandra; Brisaboa, Nieves; Fernández, Javier D.; Martínez Prieto, Miguel A.; Navarro, Gonzalo (Springer, 2015)
      The Web of Data has been gaining momentum in recent years. This leads to increasingly publish more and more semi-structured datasets following, in many cases, the RDF (Resource Description Framework) data model based on ...
    • Arenas, Marcelo; Baeza Yates, Ricardo; Gutiérrez Gallardo, Claudio; Hurtado Larraín, Carlos; Marín, Mauricio; Navarro, Gonzalo; Piquer Gardner, José; Rodríguez Tastets, M. Andrea; Ruiz del Solar, Javier; Velasco, Javier (Centro de Investigación de la Web, Departamento de Ciencias de la Computación, Universidad de Chile, 2008)
    • Brisaboa, Nieves R.; Ladra, Susana; Navarro, Gonzalo (2013)
      We present a new variable-length encoding scheme for sequences of integers, Directly Addressable Codes (DACs), which enables direct access to any element of the encoded sequence without the need of any sampling method. ...
    • Castro Gorostiza, José Miguel (Universidad de Chile, 2007)
      El objetivo general del presente trabajo de título es diseñar e implementar una solución de distribución de información de gestión, abordando el problema de modelamiento de sistemas de gestión para apoyar los procesos ...
    • Navarro, Gonzalo (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1, σ] is composed of ...
    • Mäkinen, Veli; Navarro, Gonzalo (SPRINGER-VERLAG BERLIN, 2006)
      Given a sequence of n bits with binary zero-order entropy H-o, we present a dynamic data structure that requires nH(o) + o(n) bits of space, which is able of performing rank and select, as well as inserting and deleting ...
    • Chávez, Edgar; Figueroa, Karina; Navarro, Gonzalo (IEEE COMPUTER SOC, 2008-09)
      We introduce a new probabilistic proximity search algorithm for range and K-nearest neighbor (K-NN) searching in both coordinate and metric spaces. Although there exist solutions for these problems, they boil down to a ...
    • Brisaboa, Nieves R.; Gagie, Travis; Gómez-Brandón, Adrián; Navarro, Gonzalo; Paramá, José R. (Springer, 2017)
      We present a new compressed representation of free trajectories of moving objects. It combines a partial-sums-based structure that retrieves in constant time the position of the object at any instant, with a hierarchical ...
    • Barbay, Jérémy; Claude, Francisco; Gagie, Travis; Navarro, Gonzalo; Nekrich, Yakov (Springer, 2012)
      We present a data structure that stores a sequence s[1..n] over alphabet [1..σ ] in nH0(s) + o(n)(H0(s)+1) bits, where H0(s) is the zero-order entropy of s. This structure supports the queries access, rank and select, ...
    • Farzan, Arash; Gagie, Travis; Navarro, Gonzalo (Elsevier, 2014)
      We give the first fully compressed representation of a set of m points on an n×n grid, taking H+o(H) bits of space, where View the MathML source is the entropy of the set. This representation supports range counting, ...
    • Francisco, Alexandre; Gagie, Travis; Ladra, Susana; Navarro, Gonzalo (Institute of Electrical and Electronics Engineers Inc., 2018)
      Computing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper ...
    • Ferres, Leo; Fuentes, José; Gagie, Travis; He, Meng; Navarro, Gonzalo (Springer, 2017)
      There are many representations of planar graphs but few are as elegant as Turán’s (1984): it is simple and practical, uses only four bits per edge, can handle multi-edges and can store any specified embedding. Its main ...
    • Ferres, Leo; Fuentes Sepúlveda, José; Gagie, Travis; He, Meng; Navarro, Gonzalo (Elsevier, 2020)
      There are many representations of planar graphs, but few are as elegant as Turan's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multiedges, and can store any specified embedding. ...
    • Claude, Francisco; Navarro, Gonzalo (2010-09)
      Compressed graph representations, in particular for Web graphs, have become an attractive research topic because of their applications in the manipulation of huge graphs in main memory. The state of the art is well represented ...
    • Munro, J. Ian; Navarro, Gonzalo; Nekrich, Yakov (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      We introduce a compressed suffix array representation that, on a textTof lengthnover analphabet of sizeσ, can be built inO(n)deterministic time, withinO(nlogσ)bits of workingspace, and counts the number of occurrences of ...