Browsing by Author "Gagie, Travis"

Now showing items 1-5 of 5

    • Colored range queries and document retrieval 
      Gagie, Travis; Kärkkäinen, Juha; Navarro, Gonzalo; Puglisi, Simon J. (2013)
      Colored range queries are a well-studied topic in computational geometry and database research that, in the past decade, have found exciting applications in information retrieval. In this paper, we give improved time and ...
    • Data structures and algorithms for analyzing DNA sequences in compressed space 
      Díaz Domínguez, Diego Alejandro (Universidad de Chile, 2021)
      Los avances en las tecnologías de secuenciación del ADN han generado que hoy en día tengamos una gran cantidad de colecciones genómicas disponibles para analizar. El reto con estas colecciones es almacenar y procesar los ...
    • Efficient Fully-Compressed Sequence Representations 
      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, ...
    • Entropy-bounded representation of point grids 
      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, ...
    • Synergistic (Analysis of) algorithms and data structures 
      Ochoa Méndez, Carlos Ernesto (Universidad de Chile, 2019)
      Los refinamientos actuales del análisis del peor caso sobre instancias con tamaño de entrada fijo consideran el orden de la entrada (por ejemplo, las subsecuencias ordenadas en una secuencia de números y las cadenas ...