Now showing items 1-6 of 6

    • 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 ...
    • Document retrieval on repetitive string collections 

      Gagie, Travis; Hartikainen, Aleski; Karhu, Kalle; Kärkkäinen, Juha; Navarro, Gonzalo; Puglisi, Simon J.; Sirén, Jouni (Springer, 2017-06)
      Most of the fastest-growing string collections today are repetitive, that is, most of the constituent documents are similar to many others. As these collections keep growing, a key approach to handling them is to exploit ...
    • 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, ...
    • Guest editorial: special issue on compact data structures 

      Gagie, Travis; Navarro, Gonzalo (Springer, 2018)
    • Relative Suffix Trees 

      Farruggia, Andrea; Gagie, Travis; Navarro, Gonzalo; Puglisi, Simon J.; Siren, Jouni (The British Computer Society, 2018-05)
      Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times larger than the input sequence. Much effort ...