Browsing by Author "Gagie, Travis"

Now showing items 1-3 of 3

    • 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 ...
    • 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, ...