Browsing by Author "0b299f8a96ef4215819d9ba77fe8f9d1"
Now showing items 115 of 15

Brisaboa, Nieves R.; Gagie, Travis; Gómez Brandon, Adrián; Navarro, Gonzalo; Parama, José R. (Taylor & Francis, 2020)As the number of vehicles and devices equipped with GPS technology has grown explosively, an urgent need has arisen for time and spaceefficient data structures to represent their trajectories. The most commonly desired ...

Gagie, Travis; He, Meng; Navarro, Gonzalo (Springer, 2020)In the range alphamajority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ...

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 α (ji+1) times in S[i.j] can be reported ...

Gagie, Travis; Hartikainen, Aleski; Karhu, Kalle; Kärkkäinen, Juha; Navarro, Gonzalo; Puglisi, Simon J.; Sirén, Jouni (Springer, 201706)Most of the fastestgrowing 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 ...

Brisaboa, Nieves R.; Gagie, Travis; GómezBrandó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 partialsumsbased structure that retrieves in constant time the position of the object at any instant, with a hierarchical ...

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 realvalued 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 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 selfloops and multiedges, and can store any specified embedding. ...

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 multiedges and can store any specified embedding. Its main ...

Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola (Assoc Computing Machinery, USA, 2020)Indexing highly repetitive textssuch as genomic databases, software repositories and versioned text collectionshas become an important problem since the turn of the millennium. A relevant compressibility measure for ...

Gagie, Travis; Navarro, Gonzalo (Springer, 2018)

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 dictionarybased compression. A plausible lower bound is b, the least number of phrases of a general ...

Gagie, Travis; He, Meng; Navarro, Gonzalo (Schloss Dagstuhl LeibnizZentrum 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 ...

Farruggia, Andrea; Gagie, Travis; Navarro, Gonzalo; Puglisi, Simon J.; Siren, Jouni (The British Computer Society, 201805)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 ...

Gagie, Travis; He, Meng; Navarro, Gonzalo (Elsevier, 2020)We present the first solution to finding taumajorities on tree paths. Given a tree of nnodes, each with a label from [1..sigma], and a fixed threshold 0 < tau 1, such a query gives two nodes u nd v nd asks for all the ...

Brisaboa, Nieves; Gagie, Travis; GomezBrandon, 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 LempelZiv and supports efficient direct access to any substring. The BT divides the ...