143 citations · 504 across the 80 of their papers we have counts for
10 papers · 2 filters
Text Indexing and Searching in Sublinear Time
J. Ian Munro, Gonzalo Navarro, Yakov Nekrich
We introduce the first index that can be built in time for a text of length , and can also be queried in time for a pattern of length . On an alphabet of size $…
A Grammar Compression Algorithm based on Induced Suffix Sorting
Daniel Saad Nogueira Nunes, Felipe A. Louza, Simon Gog +2
We introduce GCIS, a grammar compression algorithm based on the induced suffix sorting algorithm SAIS, introduced by Nong et al. in 2009. Our solution builds on the factorization p…
Efficient Compression and Indexing of Trajectories
Nieves R. Brisaboa, Travis Gagie, Adrián Gómez-Brandón +2
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 ob…
Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
J. Ian Munro, Gonzalo Navarro, Yakov Nekrich
We introduce a compressed suffix array representation that, on a text of length over an alphabet of size , can be built in deterministic time, within …
Exploiting Computation-Friendly Graph Compression Methods
Alexandre P. Francisco, Travis Gagie, Susana Ladra +1
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,…
Compressed Representation of Dynamic Binary Relations with Applications
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo +1
We introduce a dynamic data structure for the compact representation of binary relations . The data structure is a dynamic variant of the k-tr…
A succinct data structure for self-indexing ternary relations
Sandra Alvarez-Garcia, Guillermo de Bernardo, Nieves R. Brisaboa +1
The representation of binary relations has been intensively studied and many different theoretical and practical representations have been proposed to answer the usual queries in m…
Document Listing on Repetitive Collections with Guaranteed Performance
Gonzalo Navarro
We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of si…
Optimal-Time Text Indexing in BWT-runs Bounded Space
Travis Gagie, Gonzalo Navarro, Nicola Prezza
Indexing highly repetitive texts --- such as genomic databases, software repositories and versioned text collections --- has become an important problem since the turn of the mille…
Parallel Construction of Compact Planar Embeddings
Leo Ferres, José Fuentes-Sepúlveda, Travis Gagie +2
The sheer sizes of modern datasets are forcing data-structure designers to consider seriously both parallel construction and compactness. To achieve those goals we need to design a…