Now showing items 1-13 of 13

    • 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 ...
    • Compressed Dynamic Range Majority Data Structures 

      Gagie, Travis; He, Meng; Navarro, Gonzalo (Institute of Electrical and Electronics Engineers Inc., 2017)
      In the range α-majority query problem, we preprocess a given sequence S[1.n] for a fixed threshold α ϵ (0, 1], such that given a query range [i.j], the symbols that occur more than α (j-i+1) times in S[i.j] can be reported ...
    • 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 compression and indexing of trajectories 

      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 ...
    • 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, ...
    • Exploiting computation-friendly graph compression methods for adjacency-matrix multiplication 

      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 ...
    • Fast and compact planar embeddings 

      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 ...
    • Guest editorial: special issue on compact data structures 

      Gagie, Travis; Navarro, Gonzalo (Springer, 2018)
    • On the approximation ratio of Lempel-Ziv parsing 

      Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola (Springer Verlag, 2018)
      Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is b, the least number of phrases of a general ...
    • Path queries on functions 

      Gagie, Travis; He, Meng; Navarro, Gonzalo (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      Let f: [1.n] → [1.n] be a function, and i: [1.n] → [1.σ] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For ...
    • 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 ...
    • Two-dimensional block trees 

      Brisaboa, Nieves; Gagie, Travis; Gomez-Brandon, Adrian; Navarro, Gonzalo (Institute of Electrical and Electronics Engineers Inc., 2018)
      The Block Tree (BT) is a novel compact data structure designed to compress sequence collections. It obtains compression ratios close to Lempel-Ziv and supports efficient direct access to any substring. The BT divides the ...