Skip to main content

Resultados relacionados

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

RUA. Repositorio Institucional de la Universidad de Alicante
Publication Otros (Other)

Boosting Perturbation-Based Iterative Algorithms to Compute the Median String

  • Mirabal, Pedro
  • Abreu Salas, José Ignacio
  • Seco, Diego
  • Pedreira, Óscar
  • Chávez, Edgar
  • Abreu Salas, José Ignacio|||/items/99fd9ec6-0b97-4c02-a28e-98bc309cff48
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.
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Navigational Rule Derivation: An algorithm to determine the effect of traffic signs on road networks

  • Galaktionov, Daniil
  • Rodríguez Luaces, Miguel
  • Saavedra Places, Ángeles
[Abstract] In this paper we present an algorithm to build a road network map enriched with traffic rules such as one-way streets and forbidden turns, based on the interpretation of already detected and classified traffic signs. Such algorithm helps to automatize the elaboration of maps for commercial navigation systems. Our solution is based on simulating navigation along the road network, determining at each point of interest the visibility of the signs and their effect on the roads. We test our approach in a small urban network and discuss various ways to generalize it to support more complex environments., Ministerio de Economía y Competitividad; TIN2013-46801-C4-3-R, Ministerio de Economía y Competitividad; IDI-20141259, Ministerio de Economía y Competitividad; ITC-20151305, Ministerio de Economía y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053
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 Tesis doctoral (DoctoralThesis)

Compact data structures for large and complex datasets

  • Silva-Coira, Fernando
[Abstract] In this thesis, we study the problem of processing large and complex collections of data, presenting new data structures and algorithms that allow us to efficiently store and analyze them. We focus on three main domains: processing of multidimensional data, representation of spatial information, and analysis of scientific data. The common nexus is the use of compact data structures, which combine in a unique data structure a compressed representation of the data and the structures to access such data. The target is to be able to manage data directly in compressed form, and in this way, to keep data always compressed, even in main memory. With this, we obtain two benefits: we can manage larger datasets in main memory and we take advantage of a better usage of the memory hierarchy. In the first part, we propose a compact data structure for multidimensional databases where the domains of each dimension are hierarchical. It allows efficient queries of aggregate information at different levels of each dimension. A typical application environment for our solution would be an OLAP system. Second, we focus on the representation of spatial information, specifically on raster data, which are commonly used in geographic information systems (GIS) to represent spatial attributes (such as the altitude of a terrain, the average temperature, etc.). The new method enables several typical spatial queries with better response times than the state of the art, at the same time that saves space in both main memory and disk. Besides, we also present a framework to run a spatial join between raster and vector datasets, that uses the compact data structure previously presented in this part of the thesis. Finally, we present a solution for the computation of empirical moments from a set of trajectories of a continuous time stochastic process observed in a given period of time. The empirical autocovariance function is an example of such operations. In this thesis, we propose a method that compresses sequences of floating numbers representing Brownian motion trajectories, although it can be used in other similar areas. In addition, we also introduce a new algorithm for the calculation of the autocovariance that uses a single trajectory at a time, instead of loading the whole dataset, reducing the memory consumption during the calculation process., [Resumo] Nesta tese estudamos o problema de procesar grandes coleccións de datos, presentando novas estruturas de datos compactas e algoritmos que nos permiten almacenalas e analizalas de forma eficiente. Centrámonos en tres dominios principais: procesamento de datos multidimensionais, representación de información espacial e análise de datos científicos. O nexo común é o uso de estruturas de datos compactas, que combinan nunha única estrutura de datos unha representación comprimida dos datos e as estruturas para acceder a tales datos. O obxectivo é poder manipular os datos directamente en forma comprimida, e desta maneira, manter os datos sempre comprimidos, incluso na memoria principal. Con esto obtemos dous beneficios: podemos xestionar conxuntos de datos máis grandes na memoria principal e aproveitar un mellor uso da xerarquía da memoria. Na primera parte propoñemos unha estructura de datos compacta para bases de datos multidimensionais onde os dominios de cada dimensión están xerarquizados. Permítenos consultar eficientemente a información agregada (sumar valor máximo, etc) a diferentes niveis de cada dimensión. Un entorno de aplicación típico para a nosa solución sería un sistema OLAP. En segundo lugar, centrámonos na representación de información espacial, especificamente en datos ráster, que se utilizan comunmente en sistemas de información xeográfica (SIX) para representar atributos espaciais (como a altitude dun terreo, a temperatura media, etc.). O novo método permite realizar eficientemente varias consultas espaciais típicas con tempos de resposta mellores que o estado da arte, ao mesmo tempo que reduce o espazo utilizado tanto na memoria principal como no disco. Ademais, tamén presentamos un marco de traballo para realizar un join espacial entre conxuntos de datos vectoriais e ráster, que usa a estructura de datos compacta previamente presentada nesta parte da tese. Por último, presentamos unha solución para o cálculo de momentos empíricos a partir dun conxunto de traxectorias dun proceso estocástico de tempo continuo observadas nun período de tempo dado. A función de autocovarianza empírica é un exemplo de tales operacións. Nesta tese propoñemos un método que comprime secuencias de números flotantes que representan traxectorias de movemento Browniano, aínda que pode ser empregado noutras áreas similares. Ademais, tamén introducimos un novo algoritmo para o cálculo da autocovarianza que emprega unha única traxectoria á vez, en lugar de cargar todo o conxunto de datos, reducindo o consumo de memoria durante o proceso de cálculo., [Resumen] En esta tesis estudiamos el problema de procesar grandes colecciones de datos, presentando nuevas estructuras de datos compactas y algoritmos que nos permiten almacenarlas y analizarlas de forma eficiente. Nos centramos principalmente en tres dominios: procesamiento de datos multidimensionales, representación de información espacial y análisis de datos científicos. El nexo común es el uso de estructuras de datos compactas, que combinan en una única estructura de datos una representación comprimida de los datos y las estructuras para acceder a dichos datos. El objetivo es poder manipular los datos directamente en forma comprimida, y de esta manera, mantener los datos siempre comprimidos, incluso en la memoria principal. Con esto obtenemos dos beneficios: podemos gestionar conjuntos de datos más grandes en la memoria principal y aprovechar un mejor uso de la jerarquía de la memoria. En la primera parte proponemos una estructura de datos compacta para bases de datos multidimensionales donde los dominios de cada dimensión están jerarquizados. Nos permite consultar eficientemente la información agregada (suma, valor máximo, etc.) a diferentes niveles de cada dimensión. Un entorno de aplicación típico para nuestra solución sería un sistema OLAP. En segundo lugar, nos centramos en la representación de la información espacial, específicamente en datos ráster, que se utilizan comúnmente en sistemas de información geográfica (SIG) para representar atributos espaciales (como la altitud de un terreno, la temperatura media, etc.). El nuevo método permite realizar eficientemente varias consultas espaciales típicas con tiempos de respuesta mejores que el estado del arte, al mismo tiempo que reduce el espacio utilizado tanto en la memoria principal como en el disco. Además, también presentamos un marco de trabajo para realizar un join espacial entre conjuntos de datos vectoriales y ráster, que usa la estructura de datos compacta previamente presentada en esta parte de la tesis. Por último, presentamos una solución para el cálculo de momentos empíricos a partir de un conjunto de trayectorias de un proceso estocástico de tiempo continuo observadas en un período de tiempo dado. La función de autocovariancia empírica es un ejemplo de tales operaciones. En esta tesis proponemos un método que comprime secuencias de números flotantes que representan trayectorias de movimiento Browniano, aunque puede ser utilizado en otras áreas similares. En esta parte, también introducimos un nuevo algoritmo para el cálculo de la autocovariancia que utiliza una única trayectoria a la vez, en lugar de cargar todo el conjunto de datos, reduciendo el consumo de memoria durante el proceso de cálculo, Xunta de Galicia; ED431G/01, Ministerio de Economía y Competitividad ;TIN2016-78011-C4-1-R, Ministerio de Economía y Competitividad; TIN2016-77158-C4-3-R, Ministerio de Economía y Competitividad; TIN2013-46801-C4-3-R, Centro para el desarrollo Tecnológico e Industrial; IDI-20141259, Centro para el desarrollo Tecnológico e Industrial; ITC-20151247, Xunta de Galicia; GRC2013/053
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 Contribución de congreso (ConferenceOutput)

A New Method to Index and Store Spatio-Temporal Data

  • Bernardo, Guillermo de
  • Casares, Ramón
  • Gómez-Brandón, Adrián
  • Paramá, José R.
[Abstract] We propose a data structure that stores, in a compressed way, object trajectories, which at the same time, allow to efficiently response queries without the need to decompress the data. We use a data structure, called K2-tree, to store the full position of all objects at regular time intervals. For storing the positions of objects between two time instants represented with K2-trees, we only encode the relative movements. In order to save space, those relative moments are encoded with only one integer, instead of two (x,y)-coordinates. Moreover, the resulting integers are further compressed with a technique that allows us to manipulate those movements directly in compressed form. In this paper, we show an experimental evaluation of this structure, which shows important savings in space and good response times., Ministerio de Economía y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía y Competitividad; IDI-20141259, Ministerio de Economía y Competitividad; ITC-20151305, Ministerio de Economía y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053
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 Contribución de congreso (ConferenceOutput)

Dv2v: A Dynamic Variable-to-Variable Compressor

  • Brisaboa, Nieves R.
  • Fariña, Antonio
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Varela Rodeiro, Tirso
The congress was held in Snowbird, Utah, USA. March 26-29, 2019, [Abstract]: We present D-v2v, a new dynamic (one-pass) variable-to-variable compressor. Variable-to-variable compression aims at using a modeler that gathers variable-length input symbols and a variable-length statistical coder that assigns shorter codewords to the more frequent symbols. In D-v2v, we process the input text word-wise to gather variable-length symbols that can be either terminals (new words) or non-terminals, subsequences of words seen before in the input text. Those input symbols are set in a vocabulary that is kept sorted by frequency. Therefore, those symbols can be easily encoded with dense codes. Our D-v2v permits real-time transmission of data, i.e. compression/transmission can begin as soon as data become available. Our experiments show thatD-v2vis able to overcome the compression ratios of the v2vDC, the state-of-the-art semi-static variable-to-variable compressor, and to almost reach p7zip values. It also draws a competitive performance at both compression and decompression., Funded in part by European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941 (project BIRDS). G.N. is funded by the Millennium Institute for Foundational Research on Data (IMFD), Chile. The Spanish group is funded by Xunta de Galicia/FEDER-UE [CSI: ED431G/01 and GRC: ED431C 2017/58]; by MINECO-AEI/FEDER-UE [ETOME-RDFD3: TIN2015-69951-R, Datos 4.0: TIN2016-78011-C4- 1-R]; by MINECO-CDTI/FEDER-UE [INNTERCONECTA: uForest ITC-20161074]; by FPI Program [BES-2017-081390] (T.V.R.); and by FPU Program [FPU16/02914] (A.G.B.).
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Semantrix: A Compressed Semantic Matrix

  • Brisaboa, Nieves R.
  • Fariña, Antonio
  • Navarro, Gonzalo
  • Varela Rodeiro, Tirso
The congress was held in Snowbird, Utah, USA. March 24-27, 2020, [Abstract]: We present a compact data structure to represent both the duration and length of homogeneous segments of trajectories from moving objects in a way that, as a data warehouse, it allows us to efficiently answer cumulative queries. The division of trajectories into relevant segments has been studied in the literature under the topic of Trajectory Segmentation. In this paper, we design a data structure to compactly represent them and the algorithms to answer the more relevant queries. We experimentally evaluate our proposal in the real context of an enterprise with mobile workers (truck drivers) where we aim at analyzing the time they spend in different activities. To test our proposal under higher stress conditions we generated a huge amount of synthetic realistic trajectories and evaluated our system with those data to have a good idea about its space needs and its efficiency when answering different types of queries., Funded in part by European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941 (project BIRDS). G.N. is funded by the Millennium Institute for Foundational Research on Data (IMFD), Chile. The Spanish group is funded by Xunta de Galicia/FEDER-UE [CSI: ED431G/01 and GRC: ED431C 2017/58]; by Xunta de Galicia/GAIN [IN848D-2017-2350417]; by Xunta de Galicia Conecta-Peme 2018 [Gema: IN852A 2018/14]; by MCIU-AEI/ FEDER-UE [ETOME-RDFD3: TIN2015-69951-R, Datos 4.0: TIN2016- 78011-C4-1-R, BIZDEVOPS: RTI2018-098309-B-C32]; and by FPI Program [BES-2017-081390] (T.V.R.)., Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN848D-2017-2350417, Xunta de Galicia; IN852A 2018/14
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 Contribución de congreso (ConferenceOutput)

Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes

  • Fariña, Antonio
  • Gagie, Travis
  • Manzini, Giovanni
  • Navarro, Gonzalo
  • Ordóñez, Alberto
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_5, [Abstract] For many kinds of prefix-free codes there are efficient and compact alternatives 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 characters. In this paper we first show how, given a probability distribution over an alphabet of σσ characters, we can store a nearly optimal alphabetic prefix-free code in o(σ)o(σ) bits such that we can encode and decode any character in constant time. We then consider a kind of code introduced recently to reduce the space usage of wavelet matrices (Claude, Navarro, and Ordóñez, Information Systems, 2015). They showed how to build an optimal prefix-free code such that the codewords’ lengths are non-decreasing when they are arranged such that their reverses are in lexicographic order. We show how to store such a code in O(σlogL+2ϵL)O(σlog⁡L+2ϵL) bits, where L is the maximum codeword length and ϵϵ is any positive constant, such that we can encode and decode any character in constant time under reasonable assumptions. Otherwise, we can always encode and decode a codeword of ℓℓ bits in time O(ℓ)O(ℓ) using O(σlogL)O(σlog⁡L) bits of space., Ministerio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-P, Ministerio de Economía, Industria y Competitividad; TIN2015-69951-R, Ministerio de Economía, Industria y Competitividad; ITC-20151305, Ministerio de Economía, Industria y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053, Chile. Núcleo Milenio Información y Coordinación en Redes; ICM/FIC.P10-024F, COST. IC1302, Academy of Finland; 268324, Academy of Finland; 250345
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 Contribución de congreso (ConferenceOutput)

3DGraCT: A Grammar-Based Compressed Representation of 3D Trajectories

  • Brisaboa, Nieves R.
  • Gómez-Brandón, Adrián
  • Martínez-Prieto, Miguel A.
  • Paramá, José R.
This version of the manuscript has been accepted for publication, after peer review and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-030-00479-8_9, [Abstract]: Much research has been published about trajectory management on the ground or at the sea, but compression or indexing of flight trajectories have usually been less explored. However, air traffic management is a challenge because airspace is becoming more and more congested, and large flight data collections must be preserved and exploited for varied purposes. This paper proposes 3DGraCT, a new method for representing these flight trajectories. It extends the GraCT compact data structure to cope with a third dimension (altitude), while retaining its space/time complexities. 3DGraCT improves space requirements of traditional spatio-temporal data structures by two orders of magnitude, being competitive for the considered types of queries, even leading the comparison for a particular one., This work was funded in part by EU H2020 MSCA RISE BIRDS: 690941; MINECO-AEI/FEDER-UE: TIN2016-78011-C4-1-R; MINECO-CDTI/FEDER-UE CIEN IDI-20141259; MINECO-CDTI/FEDER-UE CIEN IDI-20150616; MINECO-CDTI/FEDER-UE INNTERCONECTA ITC-20161074; Xunta de Galicia/FEDER-UE ED431C 2017/58 and ED431G/01., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01
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 Contribución de congreso (ConferenceOutput)

Compact Representations of Event Sequences

  • Brisaboa, Nieves R.
  • Bernardo, Guillermo de
  • Navarro, Gonzalo
  • Seco, Diego
  • Varela Rodeiro, Tirso
The congress was held in Snowbird, Utah, USA. 27-30 March 2018, [Abstract]: We introduce a new technique for the efficient management of large sequences of multi-dimensional data, which takes advantage of regularities that arise in real-world datasets and supports different types of aggregation queries. More importantly, our representation is flexible in the sense that the relevant dimensions and queries may be used to guide the construction process, easily providing a space-time tradeoff depending on the relevant queries in the domain. We provide two alternative representations for sequences of multidimensional data and describe the techniques to efficiently store the datasets and to perform aggregation queries over the compressed representation. We perform experimental evaluation on realistic datasets, showing the space efficiency and query capabilities of our proposal., Funded in part by European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941. NB, GdB and TR supported by: CDTI, MINECO grant ITC-20151247; MINECO grants TIN2016-78011-C4-1-R, TIN2016-77158-C4-3-R and TIN2013-46238-C4-3-R; and Xunta de Galicia grant ED431C 2017/58 GRC. DS supported by: MINECO (PGE and FEDER) grants TIN2016-77158-C4-3-R and TIN2013-46801-C4-3-R, and Fondecyt-Conicyt grant number 1170497. GN supported by Basal Funds FB0001, Conicyt, Chile., Xunta de Galicia; ED431C 2017/58 GRC, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 1170497
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 Contribución de congreso (ConferenceOutput)

Design of Mutation Operators for Testing Geographic Information Systems

  • Alvarado, Suilen H.
[Abstract] In this article, we propose the definition of specific mutation operators for testing Geographic Information Systems. We describe the process for applying the operators and generating mutants, and present a case study where these mutation operators are applied to two real-world applications., Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Ministerio de Economía y Competitividad; TIN2016-78011-c4-1-R, Ministerio de Ciencia, Innovación e Universidades; BIZDEVOPS-GLOBAL; RTI2018-098309-B-C32
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 Tesis doctoral (DoctoralThesis)

Compressed data structures for trajectory representation

  • Galaktionov, Daniil
[Abstract] The proliferation of GPS devices in smartphones, vehicles and sport wearables in one hand, and geolocation mechanisms (such as smart cards in public transportation) in the other hand, have produced an unprecedented capacity of obtaining and storing trajectories that people generate by the movements that originate from their daily schedules. However, no standard data models exist to represent these trajectories, and besides neither traditional databases nor new NoSQL databases are adequate for the representation and exploitation of the complex data of spatio-temporal nature which these trajectories consist of. This general outlook is even more complex once we consider that whenever we are storing information related to a context of public transportation passengers, customers inside a mall, or simply vehicles moving in a city we must deal with a true Big Data scenario in which guaranteeing an efficient response can be very challenging. Consequently, in this thesis we address the design of compact data structures for the representation of the followed trajectories, both in the context of vehicles and/or people moving in urban or periurban spaces, as in the context of itineraries of commuters in public transportation. Additionally to designing these compact data structures that allow us to represent the Big Data scenario usually seen in this application domain, we have designed the algorithms that allow the efficient exploitation of said information. These algorithms, in addition to solving classic spatio-temporal queries, such as obtaining the position of a moving object at a time instant, reconstructing the trajectory of an object, or even spatio-temporal window queries (which objects are inside a spatial range either within a time window or at a time instant), are also able to solve more specialized queries for the analysis of trajectories that travelers make. For instance, we have designed algorithms to query the number of travelers that start (or finish) their trip in a certain place within a determined time interval, or the number of travelers that switch from one line from the public transportation network to another using a particular stop, or even the number of travelers that had started their trip in a certain place (which can be either a stop or a whole neighborhood) to finish it in another place. Both the designed structures as the querying algorithms, which are available at https://github.com/dgalaktionov/compact-trip-representation, have been experimentally evaluated. With these structures we are able to represent, in a compact space of 100 MiB, a collection of approximately a million and a half of taxi trajectories, or alternatively ten million trajectories consisting of itineraries over public transportation networks, given that they are more compact. In both cases, we can solve most of the considered exploitation queries in the order of microseconds, with algorithms that scale logarithmically with respect to the increase in the number of stored trajectories. Finally, considering the practical quality of this work, it was required for the performed research to be of a clearly applied nature, which led us to developing a web application with Geograhic Information Systems technology, which integrates with our compressed structures and algorithms instead of relying on common spatial databases. This application, which provides a simple and intuitive user interface that represents the map of a transportation network, enabled an end user to run the aforementioned algorithms over a large collection of historic trajectories. Likewise, this interface presents the query results in a graphical and intuitive way., [Resumen] La proliferación de por un lado de dispositivos GPS en smartphones, vehículos o pulseras de deporte, y por otro, de otros mecanismos de geolocalización (como las tarjetas de pago de trasporte público), han generado una capacidad inédita de obtener y almacenar las trayectorias que generan las personas al moverse durante sus quehaceres diarios. Sin embargo, no existen modelos de datos estándar para representar dichas trayectorias, además de que ni las bases de datos tradicionales, ni para las nuevas bases de datos NoSQL se adecúan bien a la representación y explotación de esos datos complejos de naturaleza espacio-temporal que son las trayectorias. Para hacer más complejo aún el panorama, se constata además que cuando se quieren almacenar trayectorias de viajeros de transporte público, o de clientes en centros comerciales, o simplemente de personas o vehículos moviéndose por la ciudad hay que enfrentarse a un verdadero escenario Big Data en el que la eficiencia en la respuesta a las consultas se hace muy difícil. Por todo ello, en esta tesis se aborda el diseño de estructuras de datos compactas para la representación de las trayectorias seguidas, por un lado, por vehículos y/o personas que se mueven por las calles de un entorno urbano o periurbano acotado, y por otro los itinerarios de viajeros de transporte público. Además de diseñar esas estructuras de datos compactas, que permiten representar ese escenario Big Data habitual en estos dominios de aplicación, se han diseñado los algoritmos que permiten la explotación eficiente de dichos datos. Dichos algoritmos, además de resolver las consultas espacio-temporales clásicas, tanto las de posición de un objeto en un tiempo, o trayectoria de un objeto durante un intervalo temporal, como las consultas de rango espacio-temporal (qué objetos están en una ventana del espacio en un instante o intervalo temporal) resuelven también consultas más especializadas para el análisis de trayectorias de viajeros. Por ejemplo, hemos diseñado algoritmos para consultar el número de viajeros que inician (o terminan) su viaje en cierto lugar dentro de un cierto intervalo temporal, o el número de viajeros que conmutan de una línea a otra de la red de transporte público en una cierta parada, o incluso el número de viajeros que inicia su viaje en cierto lugar (parada o barrio) y lo termina en otra parada o barrio determinados. Tanto las estructuras de datos diseñadas como todos los algoritmos de consulta, que están disponibles en https://github.com/dgalaktionov/compact-trip-representation, han sido evaluados experimentalmente. Con estas estructuras es posible representar en un espacio de 100 MiB una colección de aproximadamente un millón y medio de trayectorias de taxis, o alternativamente diez millones de trayectorias consistentes de itinerarios sobre redes de transporte público, al ser éstas últimas más compactas. En ambos casos, podemos resolver la mayor parte de las consultas de explotación planteadas en el orden de microsegundos, con algoritmos que escalan de forma logarítmica con respecto al incremento en el número de trayectorias almacenadas. Por último y dado el carácter de tesis industrial de este trabajo, era necesario que la investigación realizada tuviese un carácter claramente aplicado, por ello se implementó una aplicación web con tecnología de Sistemas de Información Geográfica que en vez de trabajar sobre una base de datos espacial convencional utiliza la estructura comprimida y los algoritmos para su explotación diseñados en la tesis. Esa aplicación facilita, mediante una sencilla e intuitiva interfaz de usuario que representa el mapa de la red de transporte, el lanzamiento de los algoritmos diseñados sobre un amplio conjunto de trayectorias de viajeros. Del mismo modo esa interfaz presenta los resultados de las consultas de modo gráfico e intuitivo., [Resumo] A proliferación de por un lado os dispositivos GPS en smartphones, vehículos ou brazaletes deportivos e por outro lado os mecanismos de xeolocalización (como as tarxetas de pago do transporte público), xeraron unha capacidade sen precedentes para obter e almacenar as traxectorias que a xente xera ao moverse durante as súas tarefas diarias. Non obstante, non hai modelos de datos estándar para representar tales traxectorias, ademais de que nin as bases de datos tradicionais nin para as novas bases de datos NoSQL son adecuadas para a representación e explotación de datos tan complexos de natureza espazo-temporal que son as traxectorias. Para facer o panorama aínda máis complexo, tamén se comproba que cando se quere almacenar traxectorias de viaxeiros de transporte público, ou clientes en centros comerciais, ou simplemente de persoas ou vehículos que se desprazan pola cidade, se ten que afrontar un verdadeiro escenario de Big Data no que a eficiencia na resposta ás consultas faise moi difícil. Por iso, esta tese trata do deseño de estruturas compactas de datos para a representación dos camiños seguidos, por un lado, por vehículos e/ou persoas que se desprazan polas rúas dun contorno urbano ou periurbano delimitado, e por outros itinerarios de viaxeiros en transporte público. Ademais de deseñar estas estruturas compactas de datos, que permiten representar ese escenario Big Data habitual neste dominios de aplicación, deseñáronse algoritmos que permitan a explotación eficiente dos devanditos datos. Estes algoritmos, ademais de resolver as clásicas consultas espazo-temporais, tanto a posición dun obxecto á vez, como a traxectoria dun obxecto durante un intervalo de tempo, así como as consultas de rango espazo-temporal (qué obxectos están nun rango do espazo nun intre ou nun intervalo temporal) tamén resolver consultas máis especializadas para a análise de traxectorias de viaxeiros. Por exemplo, deseñamos algoritmos para comprobar o número de viaxeiros que inician (ou terminan) a súa viaxe nun determinado lugar nun determinado intervalo de tempo, ou o número de viaxeiros que cambian dunha liña a outra da rede de transporte público nun certa parada, ou incluso o número de viaxeiros que comezan a súa viaxe nun determinado lugar (parada ou barrio) e rematan noutra parada ou barrio específico. Tanto as estruturas de datos deseñadas como todos os algoritmos de consulta, dispoñibles en https://github.com/dgalaktionov/ compact-trip-representation, foron evaluados experimentalmente. Con estas estruturas é posible representar nun espazo de 100 MiB unha colección de aproximadamente un millón e medio de traxectos de taxi ou, alternativamente, dez millóns de traxectos consistentes en itinerarios en redes de transporte público, sendo estes últimos máis compactos. Nos dous casos, podemos resolver a maioría das consultas de explotación plantexadas na orde de microsegundos, con algoritmos que escalan logarítmicamente con respecto ao aumento do número de traxectorias almacenadas. Finalmente, dado o carácter de tese industrial deste traballo, foi necesario que a investigación realizada tivese un carácter claramente aplicado, polo que se implementou unha aplicación web con tecnoloxía de Sistemas de Información Xeográfica que no canto de traballar nunha base de datos espacial convencional usa a estrutura comprimida e algoritmos de explotación deseñados na tese. Esta aplicación facilita, mediante unha interface de usuario sinxela e intuitiva que representa o mapa da rede de transporte, o lanzamento dos algoritmos deseñados nun amplo conxunto de rutas de pasaxeiros. Do mesmo xeito que a interface presenta os resultados das consultas dun xeito gráfico e intuitivo., Xunta de Galicia; IN848D 2017 2350417, Xunta de Galicia; IN852A 2018/14, Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Ministerio de Economía y Competitividad; TIN2016-78011-C4-1-R, Ministerio de Economía y Competitividad; TIN2015-69951-R, Ministerio de Ciencia e Innovación; RTI-2018-098309-B-C32
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 Contribución de congreso (ConferenceOutput)

Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication

  • Francisco, Alexandre P.
  • Gagie, Travis
  • Ladra, Susana
  • Navarro, Gonzalo
[Abstract] 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 we show that some well-known Web and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. In particular, we show that the format of Boldi and Vigna allows computing the product in time proportional to the compressed graph size. Our experimental results show speedups of at least 2 on graphs that were compressed at least 5 times with respect to the original. We show that other successful graph compression formats enjoy this property as well., Fundação para a Ciência e a Tecnologia (Portugal); UID/CEC/50021/2013, Academy of Finland; 268324, Fondo Nacional de Desarrollo Científico y Tecnológico (Chile); 1171058, Ministerio de Economía y Competitividad; TIN2016-77158-C4-3-R, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Agencia Nacional de Investigación y Desarrollo (Chile); ICM/FIC RC130003
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
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Efficient Representation of Multidimensional Data over Hierarchical Domains

  • Brisaboa, Nieves R.
  • Cerdeira-Pena, Ana
  • López-López, Narciso
  • Navarro, Gonzalo
  • Penabad, Miguel R.
  • Silva-Coira, Fernando
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_19, [Abstract] We consider the problem of representing multidimensional data where the domain of each dimension is organized hierarchically, and the queries require summary information at a different node in the hierarchy of each dimension. This is the typical case of OLAP databases. A basic approach is to represent each hierarchy as a one-dimensional line and recast the queries as multidimensional range queries. This approach can be implemented compactly by generalizing to more dimensions the k2k2 -treap, a compact representation of two-dimensional points that allows for efficient summarization queries along generic ranges. Instead, we propose a more flexible generalization, which instead of a generic quadtree-like partition of the space, follows the domain hierarchies across each dimension to organize the partitioning. The resulting structure is much more efficient than a generic multidimensional structure, since queries are resolved by aggregating much fewer nodes of the tree., Ministerio de Economía, Industria y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía, Industria y Competitividad; IDI-20141259, Ministerio de Economía, Industria y Competitividad; ITC-20151305, Ministerio de Economía y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053, Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1-140796, COST. IC1302
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Compact Trip Representation over Networks

  • Brisaboa, Nieves R.
  • Fariña, Antonio
  • Galaktionov, Daniil
  • Rodríguez, M. Andrea
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_23, [Abstract] We present a new Compact Trip Representation ( CTRCTR ) that allows us to manage users’ trips (moving objects) over networks. These could be public transportation networks (buses, subway, trains, and so on) where nodes are stations or stops, or road networks where nodes are intersections. CTRCTR represents the sequences of nodes and time instants in users’ trips. The spatial component is handled with a data structure based on the well-known Compressed Suffix Array ( CSACSA ), which provides both a compact representation and interesting indexing capabilities. We also represent the temporal component of the trips, that is, the time instants when users visit nodes in their trips. We create a sequence with these time instants, which are then self-indexed with a balanced Wavelet Matrix ( WMWM ). This gives us the ability to solve range-interval queries efficiently. We show how CTRCTR can solve relevant spatial and spatio-temporal queries over large sets of trajectories. Finally, we also provide experimental results to show the space requirements and query efficiency of CTRCTR ., Ministerio de Economía y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía y Competitividad; TIN2013-47090-C3-3-P, Ministerio de Economía y Competitividad; IDI-20141259, Ministerio de Economía y Competitividad; ITC-20151305, Ministerio de Economía y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053, Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1140428, Chile. Instituto de Sistemas Complejos de Ingeniería ; FBO 16
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

GraCT: A Grammar Based Compressed Representation of Trajectories

  • Brisaboa, Nieves R.
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Paramá, José R.
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-46049-9_21, [Abstract] We present a compressed data structure to store free trajectories of moving objects (ships over the sea, for example) allowing spatio-temporal queries. Our method, GraCT, uses a k2k2 -tree to store the absolute positions of all objects at regular time intervals (snapshots), whereas the positions between snapshots are represented as logs of relative movements compressed with Re-Pair. Our experimental evaluation shows important savings in space and time with respect to a fair baseline., Ministerio de Economía y Competitividad; TIN2013-46238-C4-3-R, Ministerio de Economía y Competitividad; IDI-20141259, Ministerio de Economía y Competitividad; ITC-20151305, Ministerio de Economía y Competitividad; ITC-20151247, Xunta de Galicia; GRC2013/053, Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1-140796
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Improved Compressed String Dictionaries, CIKM '19 Proceedings of the 28th ACM International Conference on Information and Knowledge Management

  • Brisaboa, Nieves R.
  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Navarro, Gonzalo
[Abstract] We introduce a new family of compressed data structures to efficiently store and query large string dictionaries in main memory. Our main technique is a combination of hierarchical Front-coding with ideas from longest-common-prefix computation in suffix arrays. Our data structures yield relevant space-time tradeoffs in real-world dictionaries. We focus on two domains where string dictionaries are extensively used and efficient compression is required: URL collections, a key element in Web graphs and applications such as Web mining; and collections of URIs and literals, the basic components of RDF datasets. Our experiments show that our data structures achieve better compression than the state-of-the-art alternatives while providing very competitive query times., Chile.Fondo Nacional de Desarrollo Científico y Tecnológico; 1-170048, Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Ministerio de Economía y Empresa; TIN2016-77158-C4-3-R, Ministerio de Economía y Empresa; TIN2016-78011-C4-1-R, Ministerio de Ciencia, Innovación y Universidades; RTC-2017-5908-7.