Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 19
Encontrada(s) 1 página(s)

RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

ViQUF: De Novo Viral Quasispecies Reconstruction Using Unitig-Based Flow Networks

  • Freire, Borja
  • Ladra, Susana
  • Paramá, José R.
  • Salmela, Leena
This is the Accepted manuscript os the article; This version of the article has been accepted for publication, after peer review. The Version of Record is available online at: https://doi.org/10.1109/TCBB.2022.3190282., ViQUF is freely available at: https://github.com/borjaf696/ViQUF., [Abstract] During viral infection, intrahost mutation and recombination can lead to significant evolution, resulting in a population of viruses that harbor multiple haplotypes. The task of reconstructing these haplotypes from short-read sequencing data is called viral quasispecies assembly, and it can be categorized as a multiassembly problem. We consider the de novo version of the problem, where no reference is available. We present ViQUF, a de novo viral quasispecies assembler that addresses haplotype assembly and quantification. ViQUF obtains a first draft of the assembly graph from a de Bruijn graph. Then, solving a min-cost flow over a flow network built for each pair of adjacent vertices based on their paired-end information creates an approximate paired assembly graph with suggested frequency values as edge labels, which is the first frequency estimation. Then, original haplotypes are obtained through a greedy path reconstruction guided by a min-cost flow solution in the approximate paired assembly graph . ViQUF outputs the contigs with their frequency estimations. Results on real and simulated data show that ViQUF is at least four times faster using at most half of the memory than previous methods, while maintaining, and in some cases outperforming, the high quality of assembly and frequency estimation of overlap graph-based methodologies, which are known to be more accurate but slower than the de Bruijn graph-based approaches., This work has received funding from the EU H2020 under the Marie Sklodowska-Curie [GA 690941]. We wish to acknowledge the support received from the Centro de Investigación de Galicia “CITIC”, funded by Xunta de Galicia and the European Union (European Regional Development Fund- Galicia 2014-2020 Program), by grant ED431G 2019/01. This work was also supported by Xunta de Galicia/FEDER-UE under Grants [ED431C 2021/53; IG240.2020.1.185; IN852A 2018/14]; Ministerio de Ciencia e Innovación under Grants [TIN2016-78011-C4-1-R; FPU17/02742; PID2019-105221RB-C41; PID2020-114635RBI00]; and the Academy of Finland [grants 308030 and 323233 (LS)]. The authors also thank David Posada for his advice on viral evolution., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IG240.2020.1.185, Xunta de Galicia; IN852A 2018/14, Finlandia. Academy of Finland; 308030, Finlandia. Academy of Finland; 323233, https://github.com/borjaf696/ViQUF
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Compressed Data Structures for Binary Relations in Practice

  • Quijada Fuentes, Carlos
  • Penabad, Miguel R.
  • Ladra, Susana
  • Gutiérrez Retamal, Gilberto
[Abstract] Binary relations are commonly used in Computer Science for modeling data. In addition to classical representations using matrices or lists, some compressed data structures have recently been proposed to represent binary relations in compact space, such as the k 2 -tree and the Binary Relation Wavelet Tree (BRWT). Knowing their storage needs, supported operations and time performance is key for enabling an appropriate choice of data representation given a domain or application, its data distribution and typical operations that are computed over the data. In this work, we present an empirical comparison among several compressed representations for binary relations. We analyze their space usage and the speed of their operations using different (synthetic and real) data distributions. We include both neighborhood and set operations, also proposing algorithms for set operations for the BRWT, which were not presented before in the literature. We conclude that there is not a clear choice that outperforms the rest, but we give some recommendations of usage of each compact representation depending on the data distribution and types of operations performed over the data. We also include a scalability study of the data representations., Ministerio de Ciencia, Innovación y Universidades; TIN2016-77158-C4-3-R, Ministerio de Ciencia, Innovación y Universidades; TIN2016-78011-C4-1-R, Ministerio de Ciencia, Innovación y Universidades; RTC-2017-5908-7, Consellería de Economía e Industria; IN852A 2018/14, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia co-funded with ERDF; ED431G/01, University of Bío-Bío; 192119 2/R, University of Bío-Bío; 195119 GI/VC
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Navigating planar topologies in near-optimal space and time

  • Fuentes Sepúlveda, José
  • Navarro, Gonzalo
  • Seco, Diego
©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.comgeo.2022.101922, Versión aceptada, [Abstract]: We show that any embedding of a planar graph can be encoded succinctly while efficiently answering a number of topological queries near-optimally. More precisely, we build on a succinct representation that encodes an embedding of m edges within 4m bits, which is close to the information-theoretic lower bound of about 3.58m. With 4m+o(m) bits of space, we show how to answer a number of topological queries relating nodes, edges, and faces, most of them in any time in ω(1). Indeed, 3.58m+o(m) bits suffice if the graph has no self-loops and no nodes of degree one. Further, we show that with O(m) bits of space we can solve all those operations in O(1) time., Funded by ANID - Millennium Science Initiative Program - Code ICN17_002, Chile and by European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941 (project BIRDS). The authors received funding from FONDECYT grants 77190038, 1200038, and 1170497, respectively. An early partial version of this paper appeared in Proc. SPIRE 2019., Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Agencia Nacional de Investigación y Desarrollo; 77190038, Chile. Agencia Nacional de Investigación y Desarrollo; 1200038, Chile. Agencia Nacional de Investigación y Desarrollo; 1170497
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Boosting Perturbation-Based Iterative Algorithms to Compute the Median String

  • Mirabal, Pedro
  • Abreu Salas, José Ignacio
  • Seco, Diego
  • Pedreira, Óscar
  • Chávez, Edgar
[Abstract] The most competitive heuristics for calculating the median string are those that use perturbation-based iterative algorithms. Given the complexity of this problem, which under many formulations is NP-hard, the computational cost involved in the exact solution is not affordable. In this work, the heuristic algorithms that solve this problem are addressed, emphasizing its initialization and the policy to order possible editing operations. Both factors have a significant weight in the solution of this problem. Initial string selection influences the algorithm’s speed of convergence, as does the criterion chosen to select the modification to be made in each iteration of the algorithm. To obtain the initial string, we use the median of a subset of the original dataset; to obtain this subset, we employ the Half Space Proximal (HSP) test to the median of the dataset. This test provides sufficient diversity within the members of the subset while at the same time fulfilling the centrality criterion. Similarly, we provide an analysis of the stop condition of the algorithm, improving its performance without substantially damaging the quality of the solution. To analyze the results of our experiments, we computed the execution time of each proposed modification of the algorithms, the number of computed editing distances, and the quality of the solution obtained. With these experiments, we empirically validated our proposal., This work was supported in part by the Comisión Nacional de Investigación Científica y Tecnológica - Programa de Formación de Capital Humano Avanzado (CONICYT-PCHA)/Doctorado Nacional/2014-63140074 through the Ph.D. Scholarship, in part by the European Union's Horizon 2020 under the Marie Sklodowska-Curie under Grant 690941, in part by the Millennium Institute for Foundational Research on Data (IMFD), and in part by the FONDECYT-CONICYT under Grant 1170497. The work of ÓSCAR PEDREIRA was supported in part by the Xunta de Galicia/FEDER-UE refs under Grant CSI ED431G/01 and Grant GRC: ED431C 2017/58, in part by the Office of the Vice President for Research and Postgraduate Studies of the Universidad Católica de Temuco, VIPUCT Project 2020EM-PS-08, and in part by the FEQUIP 2019-INRN-03 of the Universidad Católica de Temuco, Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 2014-63140074, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 1170497, Universidad Católica de Temuco (Chile); 2020EM-PS-08, Universidad Católica de Temuco (Chile); 2019-INRN-03
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Faster compressed quadtrees

  • Bernardo, Guillermo de
  • Gagie, Travis
  • Ladra, Susana
  • Navarro, Gonzalo
  • Seco, Diego
©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.jcss.2022.09.001, Versión aceptada, An early partial version of this paper appeared in Proc. of the Data Compression Conference 2015., [Abstract]: Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O(1) bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy-path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice., Partially funded by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 690941. GdB and SL funded by MCIN/AEI/10.13039/501100011033 [grants PID2020-114635RB-I00 (EXTRACompact), PID2019-105221RB-C41 (MAGIST)], by MCIN/AEI/10.13039/501100011033, “NextGenerationEU/PRTR” [grants PDC2021-120917-C21 (SIGTRANS) , PDC2021-121239-C31 (FLATCITY-POC)], by GAIN/Xunta de Galicia [grant ED431C 2017/53 (GRC) ], and also supported by the Centro de Investigación de Galicia “CITIC”, funded by Xunta de Galicia , FEDER Galicia 2014-2020 80%, SXU 20% [grant ED431G 2019/01 (CSI) ]. TG funded by NSERC Discovery Grant RGPIN-07185-2020. GN and DS funded by ANID - Millennium Science Initiative Program - Code ICN17_002 , Chile. GN funded by FONDECYT Grant 1-200038 , Chile., Xunta de Galicia; ED431C 2017/53, Xunta de Galicia; ED431G 2019/01, Natural Sciences and Engineering Research Council of Canada; RGPIN-07185-2020, Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 1-200038
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Efficient Processing of Raster and Vector Data

  • Silva-Coira, Fernando
  • Paramá, José R.
  • Ladra, Susana
  • López, Juan R.
  • Gutiérrez, Gilberto
[Abstract] In this work, we propose a framework to store and manage spatial data, which includes new efficient algorithms to perform operations accepting as input a raster dataset and a vector dataset. More concretely, we present algorithms for solving a spatial join between a raster and a vector dataset imposing a restriction on the values of the cells of the raster; and an algorithm for retrieving K objects of a vector dataset that overlap cells of a raster dataset, such that the K objects are those overlapping the highest (or lowest) cell values among all objects. The raster data is stored using a compact data structure, which can directly manipulate compressed data without the need for prior decompression. This leads to better running times and lower memory consumption. In our experimental evaluation comparing our solution to other baselines, we obtain the best space/time trade-offs., This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 690941; from the Ministerio de Ciencia, Innovación y Universidades (PGE and ERDF) grant numbers TIN2016-78011-C4-1-R; TIN2016-77158 C4-3-R; RTC-2017-5908-7; from Xunta de Galicia (co-founded with ERDF) grant numbers ED431C 2017/58; ED431G/01; IN852A 2018/14; and University of Bío-Bío grant numbers 192119 2/R; 195119 GI/VC, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Xunta de Galicia; IN852A 2018/14, Universidad del Bío-Bío (Chile); 192119 2/R, Universidad del Bío-Bío (Chile); 195119 GI/VC
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Inference of Viral Quasispecies With a Paired de Bruijn Graph

  • Freire, Borja
  • Ladra, Susana
  • Paramá, José R.
  • Salmela, Leena
This is a pre-copyedited, author-produced version of an article accepted for publication in Bioinformatics, published by Oxford University Press, following peer review. The version of record of the article is available online at: https://doi.org/10.1093/bioinformatics/btaa782., viaDBG is implemented in C++ and it is publicly available at https://bitbucket.org/bfreirec1/viadbg. All datasets used in this article are publicly available at https://bitbucket.org/bfreirec1/data-viadbg/., Supplementary data are available at Bioinformatics online., [Abstract] Motivation: RNA viruses exhibit a high mutation rate and thus they exist in infected cells as a population of closely related strains called viral quasispecies. The viral quasispecies assembly problem asks to characterize the quasispecies present in a sample from high-throughput sequencing data. We study the de novo version of the problem, where reference sequences of the quasispecies are not available. Current methods for assembling viral quasispecies are either based on overlap graphs or on de Bruijn graphs. Overlap graph-based methods tend to be accurate but slow, whereas de Bruijn graph-based methods are fast but less accurate. Results: We present viaDBG, which is a fast and accurate de Bruijn graph-based tool for de novo assembly of viral quasispecies. We first iteratively correct sequencing errors in the reads, which allows us to use large k-mers in the de Bruijn graph. To incorporate the paired-end information in the graph, we also adapt the paired de Bruijn graph for viral quasispecies assembly. These features enable the use of long-range information in contig construction without compromising the speed of de Bruijn graph-based approaches. Our experimental results show that viaDBG is both accurate and fast, whereas previous methods are either fast or accurate but not both. In particular, viaDBG has comparable or better accuracy than SAVAGE, while being at least nine times faster. Furthermore, the speed of viaDBG is comparable to PEHaplo but viaDBG is able to retrieve also low abundance quasispecies, which are often missed by PEHaplo. Availability and implementation: viaDBG is implemented in C++ and it is publicly available at https://bitbucket.org/bfreirec1/viadbg. All datasets used in this article are publicly available at https://bitbucket.org/bfreirec1/data-viadbg/. Supplementary information: Supplementary data are available at Bioinformatics online., This work was supported by EU H2020 MSCA RISE BIRDS: 690941; MCIU [TIN2016-78011-C4-1-R; TIN2016-77158-C4-3-R; FPU17/02742; RTC-2017-5908-7]; Xunta de Galicia [ED431C 2017/58; ED431G/01; IN848D-2017-2350417; IN852A 2018/14]; and from Academy of Finland [308030 and 314170]., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Xunta de Galicia; IN848D-2017-2350417, Xunta de Galicia; IN852A 2018/14, Finlandia. Academy of Finland; 308030, Finlandia. Academy of Finland; 314170, https://bitbucket.org/bfreirec1/viadbg, https://bitbucket.org/bfreirec1/data-viadbg/
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Parallel construction of wavelet trees on multicore architectures

  • Fuentes Sepúlveda, José
  • Elejalde, Erick
  • Ferres, Leo
  • Seco, Diego
The final publication is available at Springer via http://dx.doi.org/10.1007/s10115-016-1000-6, [Abstract] The wavelet tree has become a very useful data structure to efficiently represent and query large volumes of data in many different domains, from bioinformatics to geographic information systems. One problem with wavelet trees is their construction time. In this paper, we introduce two algorithms that reduce the time complexity of a wavelet tree’s construction by taking advantage of nowadays ubiquitous multicore machines. Our first algorithm constructs all the levels of the wavelet in parallel with O(n) time and O(nlgσ+σlgn)O(nlg⁡σ+σlg⁡n) bits of working space, where n is the size of the input sequence and σσ is the size of the alphabet. Our second algorithm constructs the wavelet tree in a domain decomposition fashion, using our first algorithm in each segment, reaching O(lgn)O(lg⁡n) time and O(nlgσ+pσlgn/lgσ)O(nlg⁡σ+pσlg⁡n/lg⁡σ) bits of extra space, where p is the number of available cores. Both algorithms are practical and report good speedup for large real datasets., Chile.Comisión Nacional de Investigación Científica y Tecnológica; 21120974, Chile.Comisión Nacional de Investigación Científica y Tecnológica; 63130228
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Memory-Efficient Assembly Using Flye

  • Freire, Borja
  • Ladra, Susana
  • Paramá, José R.
This is the Accepted manuscript os the article; This version of the article has been accepted for publication, after peer review. The Version of Record is available online at: https://doi.org/10.1109/TCBB.2021.3108843 ., [Abstract]: In the past decade, next-generation sequencing (NGS) enabled the generation of genomic data in a cost-effective, high-throughput manner. The most recent third-generation sequencing technologies produce longer reads; however, their error rates are much higher, which complicates the assembly process. This generates time- and space- demanding long-read assemblers. Moreover, the advances in these technologies have allowed portable and real-time DNA sequencing, enabling in-field analysis. In these scenarios, it becomes crucial to have more efficient solutions that can be executed in computers or mobile devices with minimum hardware requirements. We re-implemented an existing assembler devoted for long reads, more concretely Flye, using compressed data structures. We then compare our version with the original software using real datasets, and evaluate their performance in terms of memory requirements, execution speed, and energy consumption. The assembly results are not affected, as the core of the algorithm is maintained, but the usage of advanced compact data structures leads to improvements in memory consumption that range from 22% to 47% less space, and in the processing time, which range from being on a par up to decreases of 25%. These improvements also cause reductions in energy consumption of around 3–8%, with some datasets obtaining decreases up to 26%., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IG240.2020.1.185, Xunta de Galicia; IN852A 2018/14, This research has received funding from: the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie [grant agreement No 690941]; CITIC Research Center, funded by “Consellería de Cultura, Educaci ón e Universidade from Xunta de Galicia”, supported in an 80% through ERDF Funds, ERDF Operational Programme Galicia 2014-2020, and the remaining 20% by “Secretaría Xeral de Universidades” (Grant ED431G 2019/01); Xunta de Galicia/FEDER-UE under Grants [IG240.2020.1.185; IN852A 2018/14] and Ministerio de Ciencia e Innovación under Grants [TIN2016-78011-C4-1-R; PID2019-105221RB-C41; PID2020-114635RB- I00; FPU17/02742].
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Grammar compressed sequences with rank/select support

  • Ordóñez, Alberto
  • Navarro, Gonzalo
  • Brisaboa, Nieves R.
An early partial version of this paper appeared in Proc. SPIRE 2014: G. Navarro, A. Ordóñez Grammar compressed sequences with rank/select support, Proc. 21st International Symposium on String Processing and Information Retrieval, LNCS, SPIRE, vol. 8799 (2014), pp. 31–44, The final publication is available at Springer via http://dx.doi.org/10.1016/j.jda.2016.10.001, [Abstract] Sequence representations supporting not only direct access to their symbols, but also rank/select operations, are a fundamental building block in many compressed data structures. Several recent applications need to represent highly repetitive sequences, and classical statistical compression proves ineffective. We introduce, instead, grammar-based representations for repetitive sequences, which use up to 6% of the space needed by statistically compressed representations, and support direct access and rank/select operations within tens of microseconds. We demonstrate the impact of our structures in text indexing applications., Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 140796, Ministerio de Economía, Industria y Competitividad; 00645663/ITC-20133062, Ministerio de Economía, Industria y Competitividad; TIN2009-14560-C03-02, Ministerio de Economía, Industria y Competitividad; TIN2010-21246-C02-01, Ministerio de Economía, Industria y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-P, Ministerio de Economía, Industria y Competitividad; AP2010-6038, Xunta de Galicia; GRC2013/053
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

A practical succinct dynamic graph representation

  • Coimbra, Miguel E.
  • Hrotkó, Joana
  • Francisco, Alexandre P.
  • Russo, Luís M.S.
  • Bernardo, Guillermo de
  • Ladra, Susana
  • Navarro, Gonzalo
©2022 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.ic.2021.104862, [Abstract]: We address the problem of representing dynamic graphs using k2-trees. The k2-tree data structure is one of the succinct data structures proposed for representing static graphs, and binary relations in general. It relies on compact representations of bit vectors. Hence, by relying on compact representations of dynamic bit vectors, we can also represent dynamic graphs. However, this approach suffers of a well known bottleneck in compressed dynamic indexing. In this paper we present a k2-tree based implementation which follows instead the ideas by Munro et al. (PODS 2015) to circumvent this bottleneck. We present two dynamic graph k2-tree implementations, one as a standalone implementation and another as a C++ library. The library includes efficient edge and neighbourhood iterators, as well as some illustrative algorithms. Our experimental results show that these implementations are competitive in practice., This work was supported by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie [grant agreement No. 690941 ], namely while the first, third and fourth authors were visiting either the University of Chile or Enxenio SL. This work was partially funded by Fundação para a Ciência e a Tecnologia (FCT) [grants PTDC/CCI-BIO/29676/2017, PTDC/CPO-CPO/28495/2017, CMUP-ERI/TIC/0046/2014, UIDB/50021/2020 ], by MCIN-AEI/10.13039/501100011033 (PGE and ERDF) [grants RTC-2017-5908-7, PID2019-105221RB-C41, PID2020-114635RB-I00 ], by MCIN-AEI “NextGenerationEU”/PRTR [grants PDC2021-120917-C21, PDC2021-121239-C31 ], by Xunta de Galicia /GAIN (co-funded by ERDF) [grant ED431C 2021/53 ], and by ANID - Millennium Science Initiative Program - Code ICN17_002 . We also wish to acknowledge the support received from the Centro de Investigación de Galicia “CITIC”, funded by Xunta de Galicia , FEDER Galicia 2014-2020 80%, SXU 20% [grant ED431G 2019/01 ]., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431G 2019/01, Portugal. Fundação para a Ciência e a Tecnologia; PTDC/CCI-BIO/29676/2017, Portugal. Fundação para a Ciência e a Tecnologia; PTDC/CPO-CPO/28495/2017, Portugal. Fundação para a Ciência e a Tecnologia; CMUP-ERI/TIC/0046/2014, Portugal. Fundação para a Ciência e a Tecnologia; UIDB/50021/2020, Chile. Agencia Nacional de Investigacion y Desarrollo; ICN17_002
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Universal indexes for highly repetitive document collections

  • Claude, Francisco
  • Fariña, Antonio
  • Martínez-Prieto, Miguel A.
  • Navarro, Gonzalo
The final publication is available via http://dx.doi.org/10.1016/j.is.2016.04.002, [Abstract] Indexing highly repetitive collections has become a relevant problem with the emergence of large repositories of versioned documents, among other applications. These collections may reach huge sizes, but are formed mostly of documents that are near-copies of others. Traditional techniques for indexing these collections fail to properly exploit their regularities in order to reduce space. We introduce new techniques for compressing inverted indexes that exploit this near-copy regularity. They are based on run-length, Lempel–Ziv, or grammar compression of the differential inverted lists, instead of the usual practice of gap-encoding them. We show that, in this highly repetitive setting, our compression methods significantly reduce the space obtained with classical techniques, at the price of moderate slowdowns. Moreover, our best methods are universal, that is, they do not need to know the versioning structure of the collection, nor that a clear versioning structure even exists. We also introduce compressed self-indexes in the comparison. These are designed for general strings (not only natural language texts) and represent the text collection plus the index structure (not an inverted index) in integrated form. We show that these techniques can compress much further, using a small fraction of the space required by our new inverted indexes. Yet, they are orders of magnitude slower., Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1-140796, Ministerio de Economía y competitividad; TIN2013-47090-C3-3-P, Ministerio de Economía y competitividad; TIN2015-69951-R, Ministerio de Economía y competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía y Competitividad; IC1302, Xunta de Galicia; GRC2013/053
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

A succinct data structure for self-indexing ternary relations

  • Álvarez García, Sandra
  • Bernardo, Guillermo de
  • Brisaboa, Nieves R.
  • Navarro, Gonzalo
The final publication is available via http://dx.doi.org/10.1016/j.jda.2016.10.002, [Abstract] 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 multiple domains. However, ternary relations have not received as much attention, even though many real-world applications require the processing of ternary relations. In this paper we present a new compressed and self-indexed data structure that we call Interleaved K2-tree (IK2-tree), designed to compactly represent and efficiently query general ternary relations. The IK2-tree is an evolution of an existing data structure, the K2-tree [6], initially designed to represent Web graphs and later applied to other domains. The IK2-tree is able to extend the K2-tree to represent a ternary relation, based on the idea of decomposing it into a collection of binary relations but providing indexing capabilities in all the three dimensions. We present different ways to use IK2-tree to model different types of ternary relations using as reference two typical domains: RDF and Temporal Graphs. We also experimentally evaluate our representations comparing them in space usage and performance with other solutions of the state of the art., Ministerio de Economía y Competitividad; TIN2013-46238-C4-3-R, Xunta de Galicia; GRC2013/053, Chile. Núcleo Milenio Información y Coordinación en Redes; ICM/FIC RC130003, Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1-140796
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Energy Consumption in Compact Integer Vectors: A Study Case

  • Fuentes Sepúlveda, José
  • Ladra, Susana
[Abstract] In the field of algorithms and data structures analysis and design, most of the researchers focus only on the space/time trade-off, and little attention has been paid to energy consumption. Moreover, most of the efforts in the field of Green Computing have been devoted to hardware-related issues, being green software in its infancy. Optimizing the usage of computing resources, minimizing power consumption or increasing battery life are some of the goals of this field of research. As an attempt to address the most recent sustainability challenges, we must incorporate the energy consumption as a first-class constraint when designing new compact data structures. Thus, as a preliminary work to reach that goal, we first need to understand the factors that impact on the energy consumption and their relation with compression. In this work, we study the energy consumption required by several integer vector representations. We execute typical operations over datasets of different nature. We can see that, as commonly believed, energy consumption is highly related to the time required by the process, but not always. We analyze other parameters, such as number of instructions, number of CPU cycles, memory loads, among others., Ministerio de Ciencia, Innovación y Universidades; TIN2016-77158-C4-3-R, Ministerio de Ciencia, Innovación y Universidades; RTC-2017-5908-7, Xunta de Galicia (co-founded with ERDF); ED431C 2017/58, Xunta de Galicia; ED431G/01, Comisión Nacional de Investigación Científica y Tecnológica; 3170534.
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Compact structure for sparse undirected graphs based on a clique graph partition

  • Glaria, Felipe
  • Hernández, Cecilia
  • Ladra, Susana
  • Navarro, Gonzalo
  • Salinas, Lilian
©2021 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https://doi.org/10.1016/j.ins.2020.09.010, [Abstract]: Compressing real-world graphs has many benefits such as improving or enabling the visualization in small memory devices, graph query processing, community search, and mining algorithms. This work proposes a novel compact representation for real sparse and clustered undirected graphs. The approach lists all the maximal cliques by using a fast algorithm and defines a clique graph based on its maximal cliques. Further, the method defines a fast and effective heuristic for finding a clique graph partition that avoids the construction of the clique graph. Finally, this partition is used to define a compact representation of the input graph. The experimental evaluation shows that this approach is competitive with the state-of-the-art methods in terms of compression efficiency and access times for neighbor queries, and that it recovers all the maximal cliques faster than using the original graph. Moreover, the approach makes it possible to query maximal cliques, which is useful for community detection., This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie [grant agreement No 690941]; from the Ministerio de Economía y Competitividad (PGE and ERDF) [Grant Nos. TIN2016-77158-C4-3-R]; from Xunta de Galicia (co-founded with ERDF) [Grant Nos. ED431C 2017/58; ED431G 2019/01]; from the Center for Biotechnology and Bioengineering (CeBiB), Chile; and from the Millennium Institute for Foundational Research on Data (IMFD), Chile., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

GraCT: A Grammar-based Compressed Index for Trajectory Data

  • Brisaboa, Nieves R.
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Paramá, José R.
©2019 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Information Sciences. The Version of Record is available online at https://doi.org/10.1016/j.ins.2019.01.035, Versión final aceptada de: N. R. Brisaboa, A. Gómez-Brandón, G. Navarro, and J. R. Paramá, "GraCT: A Grammar-based Compressed Index for Trajectory Data", Information Sciences, Vol. 483, pp. 106-135, May 2019, doi: 10.1016/j.ins.2019.01.035, [Abstract]: We introduce a compressed data structure for the storage of free trajectories of moving objects that efficiently supports various spatio-temporal queries. Our structure, dubbed GraCT, stores the absolute positions of all the objects at regular time intervals (snapshots) using a k2-tree, which is a space- and time-efficient region quadtree. Positions between snapshots are represented as logs of relative movements and compressed using a grammar-based compressor. The non-terminals of this grammar are enhanced with MBR information to enable fast queries. The GraCT structure of a dataset occupies less than the raw data compressed with a powerful traditional compressor. Further, instead of requiring full decompression to access the data like a traditional compressor, GraCT supports direct access to object trajectories or to their position at specific time instants, as well as spatial range and nearest-neighbor queries on time instants and/or time intervals. Compared to traditional methods for storing and indexing spatio-temporal data, GraCT requires two orders of magnitude less space, and is competitive in query times. In particular, thanks to its compressed representation, the GraCT structure may reside in main memory in situations where any classical uncompressed index must resort to disk, thereby being one or two orders of magnitude faster., This work has been funded by the European Union Horizon 2020 Marie Skłodowska-Curie Action Fund [grant agreement EU H2020 MSCA RISE BIRDS: 690941]; Ministerio de Economía y Competitividad (PGE and FEDER) [grant number TIN2016-78011-C4-1-R], Centro para el desarrollo Tecnológico e Industrial Programaco-founded with FEDER) [grant number CIEN 2014 IDI-20141259; INNTERCONECTA ITC-20161074], Ministerio de Educación y Formación Profesional (FPU) [grant number FPU16/02914]; Xunta de Galicia (co-founded with FEDER) [grant numbers ED431C 2017/58; ED431G/01; the Chilean National Science and Technology Development Fund (Fondecyt Grant 1-170048); and the Millennium Institute for Foundational Research on Data (IMFD), Chile., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 1-170048
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Aggregated 2D range queries on clustered points

  • Bernardo, Guillermo de
  • Konow, Bernardo
  • Navarro, Gonzalo
  • Brisaboa, Nieves R.
  • Seco, Diego
[Abstract] Efficient processing of aggregated range queries on two-dimensional grids is a common requirement in information retrieval and data mining systems, for example in Geographic Information Systems and OLAP cubes. We introduce a technique to represent grids supporting aggregated range queries that requires little space when the data points in the grid are clustered, which is common in practice. We show how this general technique can be used to support two important types of aggregated queries, which are ranked range queries and counting range queries. Our experimental evaluation shows that this technique can speed up aggregated queries up to more than an order of magnitude, with a small space overhead., Chile. Núcleo Milenio Información y Coordinación en Redes; ICM/FIC. P10-024F, Ministerio de Economía y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía y Competitividad; TIN2013-46801-C4-3-R, Xunta de Galicia; GRC2013/053
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Automatic group-wise whole-brain short association fiber bundle labeling based on clustering and cortical surface information

  • Vázquez, Andrea
  • López-López, Narciso
  • Houenou, Josselin
  • Poupon, Cyril
  • Mangin, Jean-François
  • Ladra, Susana
  • Guevara, Pamela
[Abstract] Background Diffusion MRI is the preferred non-invasive in vivo modality for the study of brain white matter connections. Tractography datasets contain 3D streamlines that can be analyzed to study the main brain white matter tracts. Fiber clustering methods have been used to automatically group similar fibers into clusters. However, due to inter-subject variability and artifacts, the resulting clusters are difficult to process for finding common connections across subjects, specially for superficial white matter. Methods We present an automatic method for labeling of short association bundles on a group of subjects. The method is based on an intra-subject fiber clustering that generates compact fiber clusters. Posteriorly, the clusters are labeled based on the cortical connectivity of the fibers, taking as reference the Desikan–Killiany atlas, and named according to their relative position along one axis. Finally, two different strategies were applied and compared for the labeling of inter-subject bundles: a matching with the Hungarian algorithm, and a well-known fiber clustering algorithm, called QuickBundles. Results Individual labeling was executed over four subjects, with an execution time of 3.6 min. An inspection of individual labeling based on a distance measure showed good correspondence among the four tested subjects. Two inter-subject labeling were successfully implemented and applied to 20 subjects and compared using a set of distance thresholds, ranging from a conservative value of 10 mm to a moderate value of 21 mm. Hungarian algorithm led to a high correspondence, but low reproducibility for all the thresholds, with 96 s of execution time. QuickBundles led to better correspondence, reproducibility and short execution time of 9 s. Hence, the whole processing for the inter-subject labeling over 20 subjects takes 1.17 h. Conclusion We implemented a method for the automatic labeling of short bundles in individuals, based on an intra-subject clustering and the connectivity of the clusters with the cortex. The labels provide useful information for the visualization and analysis of individual connections, which is very difficult without any additional information. Furthermore, we provide two fast inter-subject bundle labeling methods. The obtained clusters could be used for performing manual or automatic connectivity analysis in individuals or across subjects., Anillo de Investigación en Ciencia y Tecnología (Chile); 2016-21160342, Fondo Nacional de Desarrollo Científico y Tecnológico; 1190701, Anillo de Investigación en Ciencia y Tecnología (Chile); ACT172121, Anillo de Investigación en Ciencia y Tecnología (Chile); FB0008
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Efficient and compact representations of some non-canonical prefix-free codes

  • Fariña, Antonio
  • Gagie, Travis
  • Grabowski, Marcin
  • Manzini, Giovanni
  • Navarro, Gonzalo
  • Ordóñez, Alberto
©2022 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/. This version of the article has been accepted for publication in Theoretical Computer Science. The Version of Record is available online at https://doi.org/10.1016/j.tcs.2022.01.010 Versión final de: https://doi.org/10.1007/978-3-319-46049-9_5, [Abstract]: For many kinds of prefix-free codes there are efficient and compact alterna-tives to the traditional tree-based representation. Since these put the codes into canonical form, however, they can only be used when we can choose the order in which codewords are assigned to symbols. In this paper we first show how, given a probability distribution over an alphabet of σ symbols, we can store an optimal alphabetic prefix-free code in O(σ lg L) bits such that we can encode and decode any codeword of length  inO (min(, lg L)) time, where L is the maximum codeword length. With O 2L further bits, for any constant  > 0, we can encode and decode O(lg ) time. We then show how to store a nearly optimal alphabetic prefix-free code in o(σ) bits such that we can encode and decode in constant time. We also consider a kind of optimal prefix-free code introduced recently where the codewords’ lengths are non-decreasing if arranged in lexicographic order of their reverses. We reduce their storage space to O(σ lg L) while maintaining encoding and de-coding times in O(). We also show how, with O 2L further bits, we can encode and decode in constant time. All of our results hold in the word-RAM model., This research was carried out in part at University of A Coruña, Spain, while the second author was visiting from the University of Helsinki and the sixth author was a PhD student there. It started at a StringMasters workshop at the Research Center on Information and Communication Technologies (CITIC) of the University of A Coruña. The workshop was funded in part by European Union's Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 690941 (project BIRDS). The authors thank Nieves Brisaboa and Susana Ladra. The first author was supported by the CITIC research center funded by Xunta de Galicia/FEDER-UE 2014-2020 Program, grant CSI:ED431G 2019/01; by MICIU/FEDER-UE, grant BIZDEVOPSGLOBAL: RTI2018-098309-B-C32; and by Xunta de Galicia/FEDER-UE, ConectaPeme grant GEMA: IN852A 2018/14. The second author was supported by Academy of Finland grants 268324 and 250345 (CoECGR), Fondecyt Grant 1-171058, and NSERC grant RGPIN-07185-2020. The fourth author was supported by PRIN grant 2017WR7SHH, and by the INdAM-GNCS Project 2020 MFAIS- IoT. The fifth author was supported by Fondecyt Grant 1-200038, Basal Funds FB0001, and ANID - Millennium Science Initiative Program - Code ICN17 002, Chile., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IN852A 2018/14, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-171058, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-200038, Canada. Natural Science and Engineering Research Council (NSERC); RGPIN-07185-2020, Italia. Ministero dell'Istruzione, dell'Università e della Ricerca; 2017WR7SHH, Suomen Akatemia; 268324, Suomen Akatemia; 250345, http://hdl.handle.net/2183/18174