Skip to main content

DATOS 4.0: RETOS Y SOLUCIONES-UDC

TIN2016-78011-C4-1-R

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2016
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDADE DA CORUÑA

Resultados relacionados

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

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

An index for moving objects with constant-time access to their compressed trajectories

  • Brisaboa, Nieves R.
  • Gagie, Travis
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Paramá, José R.
This is an Accepted Manuscript of an article published by Taylor & Francis in International Journal of Geographical Information Science in 2021, available at: https://doi.org/10.1080/13658816.2020.1833015, Versión final aceptada de: Nieves R. Brisaboa, Travis Gagie, Adrián Gómez-Brandón, Gonzalo Navarro & José R. Paramá (2021) An index for moving objects with constant-time access to their compressed trajectories, International Journal of Geographical Information Science, 35:7, 1392-1424, DOI: 10.1080/13658816.2020.1833015, [Abstract]: As the number of vehicles and devices equipped with GPS technology has grown explosively, an urgent need has arisen for time- and space-efficient data structures to represent their trajectories. The most commonly desired queries are the following: queries about an object’s trajectory, range queries, and nearest neighbor queries. In this paper, we consider that the objects can move freely and we present a new compressed data structure for storing their trajectories, based on a combination of logs and snapshots, with the logs storing sequences of the objects’ relative movements and the snapshots storing their absolute positions sampled at regular time intervals. We call our data structure ContaCT because it provides Constant- time access to Compressed Trajectories. Its logs are based on a compact partial-sums data structure that returns cumulative displacement in constant time, and allows us to compute in constant time any object’s position at any instant, enabling a speedup when processing several other queries. We have compared ContaCT experimentally with another compact data structure for trajectories, called GraCT, and with a classic spatio-temporal index, the MVR-tree. Our results show that ContaCT outperforms the MVR-tree by orders of magnitude in space and also outperforms the compressed representation in time performance., This work was supported by Xunta de Galicia/FEDER-UE under Grants [IN848D-2017-2350417; IN852A 2018/14; ED431C 2017/58]; Xunta de Galicia and European Union (European Regional Development Fund- Galicia 2014-2020 Program) with the support of CITIC research center under Grant [ED431G 2019/01]; Ministerio de Ciencia, Innovación y Universidades under Grants [TIN2016-78011-C4-1-R; RTC-2017-5908-7]; A.G. was supported by Ministerio de Educación y Formación Profesional (FPU) [grant number FPU16/02914]; G.N. was supported by ANID - Millennium Science Initiative Program under Grant [ICN17_002]; and Fondecyt under Grant [1-200038]. T.G. was supported by NSERC under grant [RGPIN-2020-07185]., Xunta de Galicia; IN848D-2017-2350417, Xunta de Galicia; IN852A 2018/14, 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)

Developing Web-based Geographic Information Systems with a DSL: Proposal and Case Study

  • Alvarado, Suilen H.
  • Cortiñas, Alejandro
  • Rodríguez Luaces, Miguel
  • Pedreira, Óscar
  • Saavedra Places, Ángeles
This is a pre-copyedited, author-produced version of an article accepted for publication in Journal of Web Engineering, following peer review. The version of record of the article is available online at: : https://doi.org/10.13052/jwe1540-9589.1923., [Abstract]: In this paper, we present a declarative domain-specific language (DSL) for the development of Geographic Information Systems (GIS). GIS applications manage information with a spatial component, usually in the form of points, lines, polygons, or variants of these basic data types, in domains where the spatial information plays a central role. They provide the user with different functionalities on different application domains, but they are usually developed according to a common architecture and using a common set of technologies. Hence, they share a significant number of elements that make some aspects of their development quite repetitive. Our DSL allows developers to specify the entities, geographic layers, and maps of the applications using a declarative language. Then, the specification is transformed into a working GIS application. We present the language, its implementation, and a case study on two sample projects that allowed us to evaluate the resulting software, paying special attention to the savings in the development effort., Partially funded by: Xunta de Galicia FEDER-UE CSI grants: ED431C 2017/58 (Grupo de Referencia Competitiva), and IN852A 2018/14 (ConectaPeme, project GEMA); Ministerio de Economía-AEI FEDER-UE grants: Datos 4.0 (TIN2016-78011-c4-1-R), and Flatcity (TIN2016-77158-C4-3-R); and Ministerio de Ciencia e Innovación-AEI FEDER-UE grant BIZDEVOPS (RTI2018-098309-B-C32)., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN852A 2018/14
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Towards a Compact Representation of Temporal Rasters

  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Fariña, Antonio
  • Paramá, José R.
  • Silva-Coira, Fernando
Presented at the 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018., This version of the conference paper (book chapter) 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_10, [Abstract]: Big research efforts have been devoted to efficiently manage spatio-temporal data. However, most works focused on vectorial data, and much less, on raster data. This work presents a new representation for raster data that evolve along time named Temporal . It faces the two main issues that arise when dealing with spatio-temporal data: the space consumption and the query response times. It extends a compact data structure for raster data in order to manage time and thus, it is possible to query it directly in compressed form, instead of the classical approach that requires a complete decompression before any manipulation. In addition, in the same compressed space, the new data structure includes two indexes: a spatial index and an index on the values of the cells, thus becoming a self-index for raster data., Funded in part by European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941 (project BIRDS); by Xunta de Galicia/FEDER-UE [CSI: ED431G/01 and GRC: ED431C 2017/58]; by MINECO-AEI/FEDER-UE [Datos 4.0: TIN2016-78011-C4-1-R; Velocity: TIN2016-77158-C4-3-R; and ETOME-RDFD3: TIN2015-69951-R]; and by MINECO-CDTI/FEDER-UE [INNTERCONECTA: uForest ITC-20161074]., Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58
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 Contribución de congreso (ConferenceOutput)

An Efficient Representation of Enriched Temporal Trajectories

  • Brisaboa, Nieves R.
  • Fariña, Antonio
  • Otero-González, Diego
  • Varela Rodeiro, Tirso
[Abstract] We present a novel representation of enriched trajectories of a mobile workforce management system. In this system, employees are tracked during their working day and both their routes and the tasks performed at each time instant are recorded. Our proposal tackles the representation of this information paying special attention to the space footprint without neglecting query time. We performed experiments using real and synthetic datasets where we show the compression effectiveness as well as the efficiency at query time. Our results showed that our proposal yields promising results in terms of the space needed to represent both users’ locations and activities while performing access queries to the original data within microseconds., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IG240.2020.1.185, Xunta de Galicia; IN852A 2018/14, Partially funded by the CITIC research center funded by Xunta/FEDER-UE 2014-2020 Program, grant ED431G 2019/01. MICIU (PGE/ERDF) [Datos 4.0: TIN2016-78011-C4-1-R; STEPS: RTC-2017-5908-7; BIZDEVOPS: RTI2018-098309-B-C32]. IGAPE/Xunta (FEDER-UE) 2014-2020 [IG240.2020.1.185]. Xunta/GAIN (ERDF) [GEMA: IN852A 2018/14] and by FPI Program [BES-2017-081390]., https://www.scitepress.org/ProceedingsDetails.aspx?ID=H6opWeZtwKs=&t=1
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Lossless Compression of Industrial Time Series With Direct Access

  • Gómez-Brandón, Adrián
  • Paramá, José R.
  • Villalobos, Kevin
  • Illarramendi, Arantza
  • Brisaboa, Nieves R.
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] The new opportunities generated by the data-driven economy in the manufacturing industry have causedmany companies opt for it. However, the size of time series data that need to be captured creates theproblem of having to assume high storage costs. Moreover, these costs, which are constantly growing,begin to have an impact on the profitability of companies. Thus, in this scenario, the need arises to developtechniques that allow obtaining reduced representations of the time series. In this paper, we present alossless compression method for industrial time series that allows an efficient access. That is, our aim goesbeyond pure compression, where the usual way to access the data requires a complete decompressionof the dataset before processing it. Instead, our method allows decompressing portions of the dataset,and moreover, it allows direct querying the compressed data. Thus, the proposed method combines theefficient access, typical of lossy methods, with the lossless compression., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IG240. 2020.1.185, Xunta de Galicia; IN852A 2018/14, Gobierno Vasco; IT1330-19, For the A Coruña team: This work was supported by CITIC, as Research Center accredited by Galician University System, is 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, Innovación under Grants [TIN2016-78011-C4-1-R; RTC-2017-5908-7]. For the Basque team: Ministerio de Ciencia, Innovación y Universidades under Grant [FEDER/TIN2016-78011-C4-2-R] and the Basque Government under Grant No. [IT1330-19]. Funding for open access charge: Universidade da Coruña/CISUG.
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)

Space-Efficient Representations of Raster Time Series

  • Silva-Coira, Fernando
  • Paramá, José R.
  • Bernardo, Guillermo de
  • Seco, Diego
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Raster time series, a.k.a. temporal rasters, are collections of rasters covering the same region at consecutive timestamps. These data have been used in many different applications ranging from weather forecast systems to monitoring of forest degradation or soil contamination. Many different sensors are generating this type of data, which makes such analyses possible, but also challenges the technological capacity to store and retrieve the data. In this work, we propose a space-efficient representation of raster time series that is based on Compact Data Structures (CDS). Our method uses a strategy of snapshots and logs to represent the data, in which both components are represented using CDS. We study two variants of this strategy, one with regular sampling and another one based on a heuristic that determines at which timestamps should the snapshots be created to reduce the space redundancy. We perform a comprehensive experimental evaluation using real datasets. The results show that the proposed strategy is competitive in space with alternatives based on pure data compression, while providing much more efficient query times for different types of queries., The data used in this study were acquired as part of the mission of NASA’s Earth Science Division and archived and distributed by the Goddard Earth Sciences (GES) Data and Information Services Center (DISC). Funding: CITIC, as Research Center accredited by Galician University System, is 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). This work was also supported by Xunta de Galicia/FEDER-UE under Grants [IG240.2020.1.185; IN852A 2018/14]; Ministerio de Ciencia, Innovación y Universidades under Grants [TIN2016-78011-C4-1-R; RTC-2017-5908-7; PID2019- 105221RB-C41/AEI/10.13039/501100011033]; ANID - Millennium Science Initiative Program - Code ICN17_002; Programa Iberoamericano de Ciencia y Tecnología para el Desarrollo (CYTED) [Grant No. 519RT0579], Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IG240.2020.1.185, Xunta de Galicia; IN852A 2018/14, Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002
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)

An Action Research for Improving the Sustainability Assessment Framework Instruments

  • Condori Fernández, Nelly
  • Lago, Patricia
  • Rodríguez Luaces, Miguel
  • Saavedra Places, Ángeles
[Abstract] In the last years, software engineering researchers have defined sustainability as a quality requirement of software, but not enough effort has been devoted to develop new methods/techniques to support the analysis and assessment of software sustainability. In this study, we present the Sustainability Assessment Framework (SAF) that consists of two instruments: the software sustainability–quality model, and the architectural decision map. Then, we use participatory and technical action research in close collaboration with the software industry to validate the SAF regarding its applicability in specific cases. The unit of analysis of our study is a family of software products (Geographic Information System- and Mobile-based Workforce Management Systems) that aim to address sustainability goals (e.g., efficient collection of dead animals to mitigate social and environmental sustainability risks). The results show that the sustainability–quality model integrated with the architectural decision maps can be used to identify sustainability–quality requirements as design concerns because most of its quality attributes (QAs) have been either addressed in the software project or acknowledged as relevant (i.e., creating awareness on the relevance of the multidimensional sustainability nature of certain QAs). Moreover, the action–research method has been helpful to enrich the sustainability–quality model, by identifying missing QAs (e.g., regulation compliance, data privacy). Finally, the architectural decision maps have been found as useful to guide software architects/designers in their decision-making process., This work has received partial support by Xunta de Galicia/FEDER-UE CSI (ED431G/01, ED431C 2017/58); Xunta de Galicia/FEDER-UE, ConectaPeme, GEMA (IN852A 2018/14); MINECO-AEI/FEDER-UE with the projects: Datos 4.0 (TIN2016-78011-C4-1-R), BIZDEVOPS (RTI2018-098309-B-C32), FLATCITY (TIN2016-77158-C4-3-R.); and FONDECYT with the Kusisqa project (014-2019-FONDECYTBM-INC.INV), Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN852A 2018/14, Gobierno de Chile; 014-2019-FONDECYTBM-INC.INV
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)

Improved structures to solve aggregated queries for trips over public transportation networks

  • Brisaboa, Nieves R.
  • Fariña, Antonio
  • Galaktionov, Daniil
  • Varela Rodeiro, Tirso
  • Rodríguez, M. Andrea
This is the Accepted Manuscript. 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.1016/j.ins.2021.10.079., [Abstract]: We address the problem of storing and analyzing large datasets of passenger trips over public transportation networks that are of interest to network administrators trying to balance transportation offers (e.g., frequency of vehicles) according to the historical demand. We exploit the fact that all passenger trips made within the same vehicle share the same trajectories to reduce their redundancy and provide a representation, based on well-known compact data structures, that not only reduces the space requirements of the original passenger’s trajectories but also efficiently supports querying. Our solution uses two complementary representations: T-Matrices which excels at querying the aggregated network load, and TTCTR which represents all passenger trips and aims at counting the trips following a given pattern (i.e., how many passengers started/ended a trip at a given location or moved from a given location to another). In addition, we propose XCTR, a variant of TTCTR, which efficiently answers a wider range of queries at the cost of a moderate performance loss for some queries and some space overhead. Overall, our representation can handle a dataset of ten million trips within approximately 65% of its original size while supporting a wide range of queries in the order of microseconds., This work was supported by the CITIC research center funded by Xunta/FEDER-UE 2014-2020 Program grant ED431G 2019/01. The Spanish group is partially funded by MCIU-AEI/ FEDER-UE [Datos 4.0: TIN2016-78011-C4-1-R, BIZDEVOPS: RTI2018-098309-B-C32, STEPS: RTC-2017-5908-7]; by MICINN (PGE/ERDF) [EXTRACompact: PID2020-114635RB-I00; SIGTRANS-UDC: PDC2021-120917-C21]; by Xunta de Galicia/FEDERUE [CSI: ED431G 2019/01; GRC: ED431C 2021/53; LEMSI: IG240.2020.1.185]; by Xunta de Galicia/GAIN [Innovapeme: IN848D-2017-2350417]; by Xunta de Galicia Conecta-Peme 2018 [Gema: IN852A 2018/14]; and by FPI Program [BES-2017-081390] (T.V.R.). M. A. Rodríguez is partially funded by Millennium Institute for Foundational Research on Data, Millennium Science Initiative Program - Code ICN17 002., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IG240.2020.1.185, Xunta de Galicia; IN848D-2017-2350417, Xunta de Galicia; IN852A 2018/14, Chile. Instituto Milenio Fundamentos de los Datos, IMFD; ICN17 002
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 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 Tesis doctoral (DoctoralThesis)

Development of efficient De Bruijn graph-based algorithms for genome assembly

  • Freire, Borja
[Abstract] During the last two decades, thanks to the development of new sequencing techniques, the study of the genome has become very popular in order to discover the genetic variation present in both humans and other organisms. The predominant mode of genome analysis is through the assembly of reads in one or multiple chains for as long as possible. The most traditional way of assembly is the one that involves reads from a single genome. In this field, in the last decade, third-generation readings have emerged with new challenges for which there are no efficient solutions. The first contribution that has been made in this thesis is Compact-Flye, a tool for the efficient assembly of third-generation reads on the Flye algorithm. This tool is based on the ingenious use of compact data structures to improve typical assembly steps such as counting and indexing k-mers. Apart from the assembly of a genome, there are techniques that seek to assemble all the genomes contained in a given sample. This assembly is known as multiple sequence assembly or haplotype reconstruction, a subject also treated in this thesis. Our first approach to solving this has been viaDBG, which is the first solution based on de Bruijn graphs that offers results comparable to current techniques in viral genome assembly while maintaining the efficiency of these graphs. Our second contribution is ViQUF, which is a natural improvement on its predecessor. ViQUF completely changes the algorithm of viaDBG but continues to be based on the same structures, although with some variations that allow it not only to improve results in terms of time and quality, but also to provide additionalinformation such as an estimate of the relative presence of each species in the sample., [Resumen] Durante las últimas dos décadas, gracias al desarrollo de nuevas técnias secuenciación, el estudio del genoma ha ganado mucha popularidad de cara a conocer la variación genética presente tanto seres humanos como otros organismos. El modo predominante de análisis del genoma es a través del ensamblaje de lecturas en una o múltiples cadenas lo más largas posibles. La manera más tradicional de ensamblaje es el que implica lecturas provenientes de un solo genoma. En este campo, en la última década han surgido las lecturas de tercera generación con nuevos retos para los que no existen soluciones eficientes. La primera aportación que se ha realizado en esta tesis es Compact-Flye una herramienta para el ensamblaje eficiente de lecturas de tercera generación sobre el algoritmo Flye. Esta herramienta está basada en el uso igenioso de estructuras compactas de datos para mejorar etapas típicas del ensamblaje como el conteo e indexación de k-mers. Al margen del ensamblaje de un genoma existen técnicas que buscan ensamblar todos los genomas contenidos en una muestra determinada. Este ensamblaje es conocido como ensamblaje múltiple de secuencias o reconstrucción de haplotipos, tema también tratado en esta tesis. Nuestra primera aproximación para la resolución de este ha sido viaDBG, que es la primera solución basada en grafos de de Bruijn que ofrece resultados comparables a las técnicas vigentes en ensamblaje de genomas víricos, mientras que mantiene la eficiencia de estos grafos. Nuestra segunda aportación es ViQUF, que es una mejora natural de su predecesor. ViQUF cambia totalmente la algoritmia de viaDBG, pero sigue cimentándose en las mismas estructuras aunque con alguna variación que le permite no solo mejorar resultados en tiempo y calidad. Sino que además le permite aportar más información como estimaciones relativa de cada especie en la muestra., [Resumo] Durante as dúas últimas décadas, grazas ao desenvolvemento de novas técnicas de secuenciación, o estudo do xenoma fíxose moi popular para descubrir a variación xenética presente tanto nos humanos como noutros organismos. O modo predominante de análise do xenoma é a través da ensamblaxe de lecturas nunha ou varias cadeas o maior tempo posible. A forma máis tradicional de ensamblar é a que implica lecturas dun só xenoma. Neste campo, na última década xurdiron lecturas de terceira xeración con novos retos para os que non existen solucións eficientes. A primeira contribución que se fixo nesta tese é Compact-Flye, unha ferramenta para a montaxe eficiente de lecturas de terceira xeración sobre o algoritmo Flye. Esta ferramenta baséase no uso intelixente de estruturas de datos compactas para mellorar os pasos típicos de montaxe, como contar e indexar k-mers. Ademais da montaxe dun xenoma, existen técnicas que buscan ensamblar todos os xenomas contidos nunha determinada mostra. Este conxunto coñécese como conxunto de secuencias múltiples ou reconstrución de haplotipos, tema tamén tratado nesta tesis. O noso primeiro enfoque para resolver isto foi viaDBG, que é a primeira solución baseada en gráficos de Bruijn que ofrece resultados comparables ás técnicas actuais de ensamblaxe de xenoma viral, mantendo a eficiencia destes gráficos. A nosa segunda incorporación é ViQUF, que é unha mellora natural con respecto ao seu predecesor. ViQUF cambia completamente o algoritmo de viaDBG pero segue baseándose nas mesmas estruturas, aínda que con algunha variación que lle permite non só mellorar os resultados en tempo e calidade. Pero tamén permite achegar máis información como estimacións relativas de cada especie da mostra., 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, Quiero agradecer al Centro de Investigación de Galicia “CITIC”, financiado por la Xunta de Galicia y la Unión Europea (European Regional Development Fund- Galicia 2014-2020 Program), con la beca ED431G 2019/01. También agradecer a la Xunta de Galicia/FEDER-UE que ha financiado esta tesis a través de las becas [ED431C 2021/53; IG240.2020.1.185; IN852A 2018/14]; al Ministerio de Ciencia e Innovación con las becas [TIN2016- 78011-C4-1-R; FPU17/02742; PID2019-105221RB-C41; PID2020-114635RB-I00]; y a la academia de Finlandia [grants 308030 and 323233 (LS)].
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)

The largest empty circle with location constraints in spatial databases

  • Gutiérrez Retamal, Gilberto
  • López, Juan R.
  • Paramá, José R.
  • Penabad, Miguel R.
[Abstract]: Given a set S of points in the two-dimensional space, which are stored in a spatial database, this paper presents an efficient algorithm to find, in the area delimited by those points, the empty circle with the largest area that contains only a query point q. Our algorithm adapts previous work in the field of computational geometry to be used in spatial databases, which requires to manage large amounts of data. To achieve this objective, the basic idea is to discard a large part of the points of S, in such a way that the problem can be solved providing only the remaining points to a classical computational geometry algorithm that, by processing a smaller collection of points, saves main memory resources and computation time. The correctness of our algorithm is formally proven. In addition, we empirically show its efficiency and scalability by running a set of experiments using both synthetic and real data., For the first author, this work was supported by the research projects DIUBB [140515 3/R; 142719 3/R]s and MECESUP [UBB0704]. For the rest of authors by Ministerio de Economía y Competitividad (PGE and FEDER) under grants [TIN2016-78011-C4-1-R, TIN2013-46238- C4-3-R] and Centro para el desarrollo Tecnol´ogico e Industrial under grants [IDI-20141259, ITC-20151305, ITC-20151247]. The authors also want to thank Boaz Ben Moshe for sharing his Java Delaunay code and for kindly answering our questions., University of Bío-Bío; 140515 3/R, University of Bío-Bío; 142719 3/R, Chile. Ministerio de Educación; UBB0704
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Herramienta para la visualización de la movilidad durante la pandemia

  • Cortiñas, Alejandro
  • Rodríguez Luaces, Miguel
  • Pedreira, Óscar
Publicado en Actas de las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021). Las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021) se han celebrado en Málaga del 22 al 24 de septiembre de 2021, como parte de las Jornadas SISTEDES, parte a su vez del VI Congreso Español de Informática (CEDI 20/21)., [Resumen]: En este artículo presentamos una herramienta prototipo desarrollada entre los meses de mayo a julio del 2020, durante la situación de pandemia por el COVID-19, para mostrar la información de movilidad proporcionada por el gobierno. La herramienta pretende ser una prueba de concepto de aplicación ligera de análisis de datos espaciales, y fruto de este desarrollo surgieron varias ideas que se están llevando a cabo en la actualidad, y una nueva línea de investigación relacionada con la generación ágil de aplicaciones de mapas con indicadores gráficos mediante un lenguaje específico de dominio. Describimos aquí la motivación, el diseño de la herramienta, y el producto desarrollado., Este trabajo ha sido parcialmente financiado por el CITIC (programa Xunta/FEDER-UE 2014-2020 [ED431G 2019/01]), MICIU (PGE/ERDF) [Ma- GIST: PID2019-105221RB-C41; Datos 4.0: TIN2016-78011-C4-1-R]; MICINN (PGE/ERDF) [EXTRA-Compact: PID2020-114635RB-I00], y por el programa FPI [BES-2017-081390]., Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Set operations over compressed binary relations

  • Quijada Fuentes, Carlos
  • Penabad, Miguel R.
  • Ladra, Susana
  • Gutiérrez Retamal, Gilberto
[Abstract]: Binary relations are commonly used to represent relationships between real-world objects. Classical representations for binary relations can be very space-consuming when the set of elements is large. In these cases, compressed representations, such as the -tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover, -trees can successfully represent both sparse and dense binary relations, using different variants of the technique. In this paper, we propose and evaluate algorithms to efficiently perform set operations over binary relations represented using -trees. More specifically, we present algorithms for computing the union, intersection, difference, symmetric difference, and complement of binary relations. Thus, this work extends the functionality of the different variants of the -tree representation for binary relations. Our algorithms are computed directly over the compressed representation, without requiring previous decompression, and generate the result in compressed form. The experimental evaluation shows that they are efficient in terms of space and time, compared with different baselines where the binary relations are represented in plain form or require a previous decompression to perform the set operation., Gilberto Gutiérrez was supported by the research group ALgoritmos y BAses de Datos (ALBA) 160119 GI/EF and the research project 171319 4/R, both funded by Universidad del Bío-Bío (Chile). Susana Ladra was supported by Ministerio de Economía y Competitividad, Spain (PGE and FEDER) [grant number TIN2016-77158-C4-3-R], Centro para el desarrollo Tecnológico e Industrial, Spain (co-founded with FEDER) [ITC-20161074]; Xunta de Galicia, Spain (co-founded with FEDER) [grant number ED431C 2017/58]; and support from Xunta de Galicia (Centro singular de investigación de Galicia accreditation 2016–2019), Spain and the European Union (European Regional Development Fund — ERDF), Spain. Miguel R. Penabad was supported by Ministerio de Economía y Competitividad, Spain (PGE and FEDER) [grant number TIN2016-78011-C4-1-R], Xunta de Galicia, Spain (co-founded with FEDER) [grant number ED431C 2017/58]; and support from Xunta de Galicia (Centro singular de investigación de Galicia accreditation 2016–2019) and the European Union (European Regional Development Fund — ERDF). Carlos Quijada-Fuentes was supported by CONICYT-PCHA/MagisterNacional/2015-22150776, Chile and by the research group ALgoritmos y BAses de Datos (ALBA) 160119 GI/EF funded by Universidad del Bío-Bío (Chile)., Xunta de Galicia; ED431C 2017/58, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 2015-22150776, University of Bío-Bío; 160119 GI/EF, University of Bío-Bío; 171319 4/R
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Utilización de estructuras compactas para la generalización cartográfica de información geográfica vectorial

  • Brisaboa, Nieves R.
  • Cortiñas, Alejandro
  • Gutiérrez-Asorey, Pablo
  • Rodríguez Luaces, Miguel
  • Varela Rodeiro, Tirso
Publicado en Actas de las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021). Las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021) se han celebrado en Málaga del 22 al 24 de septiembre de 2021, como parte de las Jornadas SISTEDES, parte a su vez del VI Congreso Español de Informática (CEDI 20/21)., [Resumen]: A pesar de la madurez tecnológica de los Sistemas de Información Geográfica, todavía existen retos de investigación relevantes en el campo relacionados con las problemáticas del almacenamiento y representación eficientes de la información. En este trabajo presentamos un proyecto de investigación en curso centrado en el desarrollo de nuevas estructuras de datos para almacenar información geográfica para contextos en los que se espera que se genere una cantidad de datos inmensa., Este trabajo ha sido parcialmente financiado por el CITIC (programa Xunta/FEDER-UE 2014-2020 [ED431G 2019/01]), MICIU (PGE/ERDF) [Ma- GIST: PID2019-105221RB-C41; Datos 4.0: TIN2016-78011-C4-1-R]; MICINN (PGE/ERDF) [EXTRA-Compact: PID2020-114635RB-I00], y por el programa FPI [BES-2017-081390], Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Optimization in Sanger sequencing

  • Carpente, Luisa
  • Cerdeira-Pena, Ana
  • Lorenzo Freire, Silvia
  • Saavedra Places, Ángeles
© 2019. 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 Carpente, L., Cerdeira-Pena, A., Lorenzo-Freire, S., Places, Á.S., 2019. Optimization in Sanger sequencing. Computers & Operations Research 109, 250–262 has been accepted for publication in Computers & Operations Research. The Version of Record is available online at https://doi.org/10.1016/j.cor.2019.05.011, [Abstract]: The main objective of this paper is to solve the optimization problem that is associated with the classification of DNA samples in PCR plates for Sanger sequencing. To achieve this goal, we design an integer linear programming model. Given that the real instances involve the classification of thousands of samples and the linear model can only be solved for small instances, the paper includes a heuristic to cope with bigger problems. The heuristic algorithm is based on the simulated annealing technique. This algorithm obtains satisfactory solutions to the problem in a short amount of time. It has been tested with real data and yields improved results compared to some commercial software typically used in (clinical) laboratories. Moreover, the algorithm has already been implemented in the laboratory and is being successfully used., This work has been supported by MINECO: MTM2014-53395-C3-1-P, MINECO: MTM2017-87197-C3-1-P, Xunta de Galicia/FEDER-UE ERDF: ED431C-2016-015, Xunta de Galicia/FEDER-UE ERDF: ED431G/01, FEDER-UE ESF, Xunta de Galicia Conecta Peme-2014: IN852A-2014/9, Xunta de Galicia/FEDER-UE CSI: ED431G/01, Xunta de Galicia/FEDER-UE GRC: ED431C 2017/58, MINECO-CDTI/FEDER-UE CIEN LPS-BIGGER: IDI-20141259, MINECO-CDTI/FEDER-UE INNTERCONECTA uForest: ITC-20161074, MINECO-AEI/FEDER-UE eDSalud: RTC-2016-5143-1, MINECO-AEI/FEDER-UE Datos 4.0: TIN2016-78011-C4-1-R and MINECO-AEI/FEDER-UE ETOME-RDFD3: TIN2015-69951-R., Xunta de Galicia; ED431C-2016-015, Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN852A-2014/9
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

A Compact Representation of Indoor Trajectories

  • Fariña, Antonio
  • Gutiérrez-Asorey, Pablo
  • Ladra, Susana
  • Penabad, Miguel R.
  • Varela Rodeiro, Tirso
[Abstract]: We present a system that combines indoor positioning with a compression algorithm for trajectories in the context of a nursing home. Our aim is to gather and effectively represent the location of the residents and caregivers along time, while allowing for efficient access to those data. We briefly show the system architecture that enables the automatic tracking of user’s movements and consequently the gathering of their locations. Then, we present indRep, our compact representation to handle positioning data using grammar-based compression, and provide two basic operations that enable pseudo-random access to the data. Finally, we include experiments that show that indRep is competitive with well-know general-purpose compressors in terms of compression effectiveness and also provides fast access to the compressed data. We expect both features would enable exploitation functionalities even in computers with rather low computational resources., Partially funded by the CITIC research center funded by Xunta/FEDER-UE 2014-2020 Program, grant ED431G 2019/01. MICIU(PGE/ERDF) [MaGIST: PID2019-105221RB-C41; Datos 4.0: TIN2016-78011-C4-1- R; STEPS: RTC-2017-5908-7; BIZDEVOPS: RTI2018-098309-B-C32]. MICINN(PGE/ERDF) [EXTRA-Compact: PID2020-114635RB-I00]. Xunta/GAIN(ERDF) [CEDCOVID: COV20/00604; GRC: ED431C 2021/53] and by FPI Program [BES-2017-081390]., Xunta de Galicia: ED431G 2019/01, Xunta de Galicia: ED431C 2021/53
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Revisiting Compact RDF Stores Based on k2-Trees

  • Brisaboa, Nieves R.
  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Fariña, Antonio
Presented at the 2020 Data Compression Conference (DCC), Snowbird, UT, USA, 24-27 March 2020, © 2020 IEEE. This version of the paper has been accepted for publication. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The final published paper is available online at: https: https://doi.org/10.1109/DCC47342.2020.00020, [Abstract]: We present a new compact representation to efficiently store and query large RDF datasets in main memory. Our proposal, called BMatrix, is based on the k 2 -tree, a data structure devised to represent binary matrices in a compressed way, and aims at improving the results of previous state-of-the-art alternatives, especially in datasets with a relatively large number of predicates. We introduce our technique, together with some improvements on the basic k 2 -tree that can be applied to our solution in order to boost compression. Experimental results in the flagship RDF dataset DBPedia show that our proposal achieves better compression than existing alternatives, while yielding competitive query times, particularly in the most frequent triple patterns and in queries with unbound predicate, in which we outperform existing solutions, Funded by: MICINN-AEI/FEDER-UE RTI2018-098309-B-C32, Xunta de Galicia/GAIN IN848D-2017-2350417; MICINN-AEI/FEDER-UE RTC-2017-5908-7; Xunta de Galicia/FEDER-UE ED431C 2017/58, ED431G/01, IN852A 2018/14; MINECO-AEI/FEDER-UE TIN2016-78011-C4-1- R, TIN2016-77158-C4-3-R, TIN2015-69951-R; EU H2020 MSCA RISE BIRDS: 690941, Xunta de Galicia; IN848D-2017-2350417, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Xunta de Galicia; IN852A 2018/14
RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

Re-ingeniería y Modernización de la Biblioteca Virtual Galega

  • Ramos-Vidal, Delfina
  • Cortiñas, Alejandro
  • Rodríguez Luaces, Miguel
  • Pedreira, Óscar
  • Saavedra Places, Ángeles
Publicado en Actas de las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021). Las XXV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2021) se han celebrado en Málaga del 22 al 24 de septiembre de 2021, como parte de las Jornadas SISTEDES, parte a su vez del VI Congreso Español de Informática (CEDI 20/21)., [Resumen]: La Biblioteca Virtual Galega (BVG) es una biblioteca digital de referencia en literatura gallega de todos los tiempos, para el público general y especialmente para centros de educación de enseñanza obligatoria de la comunidad. Esta plataforma almacena y da acceso a información bibliográfica de autores clásicos y actuales, as+AO0 como información multimedia correspondiente a ediciones digitales de sus obras. En este artículo se presenta el proyecto de re-ingeniería y modernización de esta biblioteca digital (desarrollada en 2002) utilizando una línea de producto software para la generación de bibliotecas digitales desarrollada por investigadores del Laboratorio de Bases de Datos (LBD)., Parcialmente financiado por: MICIU / FEDER-UE: MAGIST (PID2019-105221RB- C41), EXTRACompact (PID2020-114635RB-I00), Red Aracne-Nodus (RED2018- 102755-T), y BIZDEVOPSGLOBAL (RTI-2018-098309-B-C32); Xunta de Galicia / FEDER-UE, ConectaPeme, GEMA (IN852A 2018/14), GRC (ED431C 2017/58); MINECO-AEI / FEDER-UE Datos 4.0 (TIN2016-78011-C4-1-R) y Velocity (TIN2016-77158-C4-3-R); centro de investigación CITIC financiado por la Xunta y la UE a través del Fondo Europeo de Desarrollo Regional - Programa Galicia 2014-2020 (ED431G 2019/01)., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IN852A 2018/14
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 Contribución de congreso (ConferenceOutput)

Tool for SPARQL Querying over Compact RDF Representations

  • Ramos-Vidal, Delfina
  • Bernardo, Guillermo de
Presented at the 4th XoveTIC Conference, A Coruña, Spain, 7–8 October 2021., [Abstract] We present an architecture for the efficient storing and querying of large RDF datasets. Our approach seeks to store RDF datasets in very little space while offering complete SPARQL functionality. To achieve this, our proposal was built over HDT, an RDF serialization framework, and its interaction with the Jena query engine. We propose a set of modifications to this framework in order to incorporate a range of space-efficient compact data structures for data storage and access, while using high-level capabilities to answer more complicated SPARQL queries. As a result, our approach provides a standard mechanism for using low-level data structures in complicated query situations requiring SPARQL searches, which are typically not supported by current solutions., This research was funded by Xunta de Galicia/FEDER grant ED431G 2019/01, Xunta de Galicia/FEDER-UE grant IN852A 2018/14; Ministerio de Ciencia, Innovación y Universidades grants [TIN2016-78011-C4-1-R; PID2019-105221RB-C41]; Consellería de Cultura, Educación e Universidade/Consellería de Economía, Empresa e Innovación/GAIN/Xunta de Galicia grant ED431C 2021/53; and by MICINN (PGE/ERDF) grant PID2020-114635RB-I00., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; IN852A 2018/14, Xunta de Galicia; ED431C 2021/53
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Scalable processing and autocovariance computation of big functional data

  • Brisaboa, Nieves R.
  • Cao, Ricardo
  • Paramá, José R.
  • Silva-Coira, Fernando
This is the peer reviewed version of the following article: Brisaboa NR, Cao R, Paramá JR, Silva-Coira F. Scalable processing and autocovariance computation of big functional data. Softw Pract Exper. 2018; 48: 123–140 which has been published in final form at https://doi.org/10.1002/spe.2524 . This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited., [Abstract]: This paper presents 2 main contributions. The first is a compact representation of huge sets of functional data or trajectories of continuous-time stochastic processes, which allows keeping the data always compressed even during the processing in main memory. It is oriented to facilitate the efficient computation of the sample autocovariance function without a previous decompression of the data set, by using only partial local decoding. The second contribution is a new memory-efficient algorithm to compute the sample autocovariance function. The combination of the compact representation and the new memory-efficient algorithm obtained in our experiments the following benefits. The compressed data occupy in the disk 75% of the space needed by the original data. The computation of the autocovariance function used up to 13 times less main memory, and run 65% faster than the classical method implemented, for example, in the R package., This work was supported by the Ministerio de Economía y Competitividad (PGE and FEDER) under grants [TIN2016-78011-C4-1-R; MTM2014-52876-R; TIN2013-46238-C4-3-R], Centro para el desarrollo Tecnológico e Industrial MINECO [IDI-20141259; ITC-20151247; ITC-20151305; ITC-20161074]; Xunta de Galicia (cofounded with FEDER) under Grupos de Referencia Competitiva grant ED431C-2016-015; Xunta de Galicia-Consellería de Cultura, Educación e Ordenación Universitaria (cofounded with FEDER) under Redes grants R2014/041, ED341D R2016/045; Xunta de Galicia-Consellería de Cultura, Educación e Ordenación Universitaria (cofounded with FEDER) under Centro Singular de Investigación de Galicia grant ED431G/01., Xunta de Galicia; D431C-2016-015, Xunta de Galicia; R2014/041, Xunta de Galicia; ED341D R2016/045, Xunta de Galicia; ED431G/01
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Extending general compact querieable representations to GIS applications

  • Brisaboa, Nieves R.
  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Navarro, Gonzalo
  • Pedreira, Óscar
© 2020. 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 “Brisaboa, N.R., Cerdeira-Pena, A., de Bernardo, G., Navarro, G., Pedreira, Ó., 2020. Extending general compact querieable representations to GIS applications. Information Sciences 506, 196–216” has been accepted for publication in Information Sciences. The Version of Record is available online at https://doi.org/10.1016/j.ins.2019.08.007, [Abstract]: The raster model is commonly used for the representation of images in many domains, and is especially useful in Geographic Information Systems (GIS) to store information about continuous variables of the space (elevation, temperature, etc.). Current representations of raster data are usually designed for external memory or, when stored in main memory, lack efficient query capabilities. In this paper we propose compact representations to efficiently store and query raster datasets in main memory. We present different representations for binary raster data, general raster data and time-evolving raster data. We experimentally compare our proposals with traditional storage mechanisms such as linear quadtrees or compressed GeoTIFF files. Results show that our structures are up to 10 times smaller than classical linear quadtrees, and even comparable in space to non-querieable representations of raster data, while efficiently answering a number of typical queries., Partially funded by: IMFD; Xunta de Galicia/FEDER-UE grants CSI:ED431G/01 and GRC:ED431C 2017/58; Xunta de Galicia/FEDER-UE, ConectaPeme grant GEMA: IN852A 2018/14; Xunta de Galicia/GAIN grant Innovapeme: IN848D-2017-2350417; by MINECO-AEI/FEDER-UE grants Flatcity: TIN2016-77158-C4-3-R, Datos 4.0: TIN2016-78011-C4-1-R and ETOME-RDFD3: TIN2015-69951-R; MICINN-AEI/FEDER-UE grants Steps: RTC-2017-5908-7 and BIZDEVOPS: RTI2018- 098309-B-C32; and EU H2020 MSCA RISE BIRDS: 690941. An early partial version of this article appeared in Proc SPIRE’13. Some parts of this work also appeared in G. de Bernardo’s PhD thesis., Xunta de Galicia; ED431G/01, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN852A-2018/14, Xunta de Galicia; IN848D-2017-2350417
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Multilevel Modeling of Geographic Information Systems Based on International Standards

  • Alvarado, Suilen H.
  • Cortiñas, Alejandro
  • Rodríguez Luaces, Miguel
  • Pedreira, Óscar
  • Saavedra Places, Ángeles
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Even though different applications based on Geographic Information Systems (GIS) provide different features and functions, they all share a set of common concepts (e.g., spatial data types, operations, services), a common architecture, and a common set of technologies. Furthermore, common structures appear repeatedly in different GIS, although they have to be specialized in specific application domains. Multilevel modeling is an approach to model-driven engineering (MDE) in which the number of metamodel levels is not fixed. This approach aims at solving the limitations of a two-level metamodeling approach, which forces the designer to include all the metamodel elements at the same level. In this paper, we address the application of multilevel modeling to the domain of GIS, and we evaluate its potential benefits. Although we do not present a complete set of models, we present four representative scenarios supported by example models. One of them is based on the standards defined by ISO TC/211 and the Open Geospatial Consortium. The other three are based on the EU INSPIRE Directive (territory administration, spatial networks, and facility management). These scenarios show that multilevel modeling can provide more benefits to GIS modeling than a two-level metamodeling approach., Xunta de Galicia; IN852A 2018/14, Xunta de Galicia; ED431G 2019/01, This work has been partially funded by grants: MICIU/FEDER-UE, MAGIST: PID2019-105221RB-C41; MICIU/FEDER-UEBIZDEVOPSGLOBAL: RTI-2018-098309-B-C32, Xunta de Galicia/FEDER-UE, ConectaPeme, GEMA: IN852A 2018/14; MINECOAEI/FEDER-UE Datos 4.0: TIN2016-78011-C4-1-R; MINECOAEI/FEDER-UE Velocity: TIN2016-77158-C4-3-R; CITIC research center funded by XUNTA and EU through the European Regional Development Fund- Galicia 2014-2020 Program, grant ED431G 2019/01. Funding for open access charge: Universidade da Coruña/CISUG.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Building the legal knowledge graph for smart compliance services in multilingual Europe

  • Montiel-Ponsoda, E.
  • Rodríguez-Doncel, V.
  • Gracia, J.
This position paper describes the vision, objectives and methodology of the LYNX project. The aim of Lynx is to create services to better manage compliance, based on a legal knowledge graph which integrates and links heterogeneous compliance data sources including legislation, case law and standards.