Pasar al contenido principal

Resultados relacionados

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

RUC. Repositorio da Universidade da Coruña
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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