Pasar al contenido principal

Resultados relacionados

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

RUC. Repositorio da Universidade da Coruña
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación Tesis doctoral (DoctoralThesis)

Compact Structures for the Representation of Trajectory Information

  • Gutiérrez-Asorey, Pablo
[Abstract] We live in an age of information and movement. Constantly on the move, tethered to our cell phones, searching the Internet for directions to the station, what time the next bus stops, what is the best route to the mall, where we are going to eat today, and so on. We get up and go to work or school, we go home, we go out partying... As a species it would seem that we are incapable of sitting still for long, we always yearn to get somewhere. Essentially none of this is new, nor should it be considered unique to the current age. They already used maps in ancient Babylon. What they didn’t have, however, were screens, and the whole parade of technologies that in the 21st century has become practically a new limb for citizens of developed countries. Those smartphones, those GPS, the reader of our traveler card on the bus, are systems that collect information about us; about how we move. Facilities such as shopping malls or hospitals can easily capture with technological solutions the movements of users and staff, but even indirectly, when making a card payment, or, again, validating a trip on a means of public transport with a traveler card, we are creating a record of our position and intention to move at a given instant of time. We are not talking about discrete amounts of information, either. With so much technology flooding us, it is to be expected that the positioning information of people and objects over a relatively large period of time (or even not that large, depending on the context) will reach massive sizes. Of course, any technological advance brings with it ripe opportunities for research on how to refine the new technologies and apply them to solve problems that matter to people and society at large. Thus, this thesis focuses on researching solutions for the representation of maps and the movements of people and objects on those maps over time. Our work focuses on facilitating the spatially and time-efficient representation of maps and trajectories using compact data structures capable of storing information in a compressed format while allowing its exploitation without the need for decompression. Our first contribution is a strategy for representing maps at different scales or zoom levels in a compact manner. Most systems that work with maps, such as Google Maps, store different versions of the same map at different levels of detail suitable for different zoom levels. This generates redundant information that needs to be stored. This is because, for example, although a coastline may look much more simplified at a low zoom, using far fewer geographic points than at a high zoom, the visible points will still exist at all successive zoom levels as well, only added to new points that provide more detail to the shape. Our proposal can represent different zoom levels without repeating any geographic points between them, thus greatly improving storage size when compared to typical solutions. Our second contribution is an indoor positioning system, capable of capturing user trajectories in a semantically annotated, motion-limited space (e.g., a shopping mall or medical facility where the layout of the space informs the possibilities of movement and it is possible to tag rooms and corridor segments with unique identifiers), and compressing them into a compact data structure with access times to the movements of any user in a given time period well below a millisecond. Finally, the last contribution of this thesis is the work done as part of an ambitious research project aimed at the analysis and exploitation of traveler movements in public transport networks. Using traveler card records, we offer solutions for storing and exploiting trips from an origin to a destination stop of users of the transport network., [Resumen] Vivimos en la era de la información y el movimiento. Constantemente en movimiento, enganchados a nuestros teléfonos móviles, buscando en Internet cómo llegar a la estación, a qué hora pasa el bus, cuál es la mejor ruta hasta el centro comercial, dónde vamos a comer hoy, etc. Nos levantamos y vamos al trabajo o a la escuela, volvemos a casa, salimos de fiesta. . . Como especie parecería que somos incapaces de permanecer quietos mucho tiempo, siempre anhelamos llegar a alguna parte. En esencia nada de esto es nuevo, ni deberían considerarse circunstancias exclusivas de la era actual. Ya se usaban mapas en la antigua Babilonia. No obstante, lo que no tenían eran pantallas, y todo el desfile de tecnologías que en el siglo 21 se han convertido en prácticamente una nueva extremidad para los ciudadanos de los países desarrollados. Los teléfonos inteligentes, los GPS, el lector de nuestra tarjeta de viajero en el autobús; son todos sistemas que recaban información sobre nosotros, sobre cómo nos movemos. Instalaciones como centros comerciales u hospitales pueden utilizar soluciones tecnológicas para conocer los movimientos de usuarios y personal con facilidad, pero, incluso de forma indirecta, al hacer un pago con tarjeta de crédito, o, de nuevo, al validar un viaje en un medio de transporte público con una tarjeta de viajero, estamos creando un registro, tanto de nuestra posición como de una intención de desplazamiento, en un instante de tiempo determinado. Por descontado, no estamos hablando de cantidades de información precisamente pequeñas. Con tanta tecnología inundando nuestras vidas, es de esperar que la información de posicionamiento de personas y objetos a lo largo de un periodo de tiempo relativamente grande (o no tan grande, esto depende del contexto) alcance tamaños masivos. Por supuesto, cualquier avance tecnológico trae consigo oportunidades de investigación en como afinar las nuevas tecnologías y aplicarlas para resolver problemas que importan a las personas y a la sociedad en general. Así pues, esta tesis se centra en investigar soluciones para la representación de mapas y los movimientos de personas y objetos en esos mapas. El trabajo realizado se centra en facilitar la representación eficiente, tanto desde el punto de vista espacial como del tiempo de acceso a los datos, de mapas y trayectorias, utilizando estructuras de datos compactas que almacenan la información en formato comprimido a la vez que permiten su explotación sin necesidad de un proceso previo de descompresión. Nuestra primera contribución es una estrategia para la representación de mapas a diferentes niveles de escala o zoom de forma compacta. La mayoría de sistemas que trabajan con mapas, como Google Maps y similares, guardan diferentes versiones de un mismo mapa a diferentes niveles de detalle adecuados para los distintos niveles de zoom. Esto genera una gran cantidad de información redundante que es necesario almacenar. Esto es debido a que, por ejemplo, aunque la línea de una costa se vea mucho más simplificada a un zoom bajo, utilizando muchos menos puntos geográficos que en un zoom alto, los puntos que sí se ven van a existir en todos los niveles sucesivos de zoom también, solo que sumados a nuevos puntos que confieren más detalle a la forma. Nuestra propuesta es capaz de representar diferentes niveles de zoom sin repetir ningún punto geográfico entre ellos, mejorando por tanto en términos de espacio de almacenamiento respecto a las soluciones típicas. Nuestra segunda contribución es un sistema de posicionamiento en interiores capaz de capturar las trayectorias de usuarios en un espacio con movimiento limitado y anotado semánticamente (por ejemplo, un centro comercial o instalación médica donde la distribución del espacio informa obviamente de las posibilidades de movimiento y es posible etiquetar salas y segmentos de pasillo con identificadores únicos), y comprimirlas en una estructura de datos compacta con tiempos de acceso a los movimientos de cualquier usuario en un periodo de tiempo determinado muy por debajo del milisegundo. Finalmente, la última contribución de esta tesis es el trabajo realizado como parte de un ambicioso proyecto de investigación destinado al análisis y explotación de los movimientos de viajeros en redes de transporte público. Utilizando registros de tarjetas de viajero, ofrecemos soluciones para almacenar y explotar los viajes de una parada de origen a otra de destino de usuarios de la red de transporte., [Resumo] Vivimos nunha era de información e movemento. Constantemente en movemento, atados aos nosos móbiles, buscando en Internet como chegar á estación, a que hora pasa o autobús, cal é a mellor ruta para ir ao centro comercial, onde imos comer hoxe, etc. Levantámonos e imos ao traballo ou ao colexio, chegamos á casa, saímos de festa... Como especie parece que somos incapaces de quedarnos moito tempo parados, sempre queremos chegar a algún sitio. En esencia nada disto é novo, nin debe ser visto como exclusivo da época actual. Xa usaban mapas na antiga Babilonia. Porén, o que non tiñan eran pantallas, e todo o desfile de tecnoloxías que no século XXI se converteron practicamente nunha nova extremidade para os cidadáns dos países desenvolvidos. Os móbiles intelixentes, os GPS, o lector da nosa tarxeta de viaxeiro no autobús, son sistemas que recollen información sobre nós; sobre como nos movemos. Instalacións como centros comerciais ou hospitais poden coñecer con solucións tecnolóxicas os movementos de usuarios e persoal con facilidade, pero, incluso indirectamente, realizando o pago con tarxeta, ou, de novo, validando unha viaxe nun medio de transporte público con nosa tarxeta de viaxeiro, estamos creando un rexistro da nosa posición e intención de movernos nun momento dado. Ademais, non estamos a falar de cantidades de información precisamente pequenas. Con tanta tecnoloxía que nos inunda, é de esperar que a información de posicionamento de persoas e obxectos durante un período de tempo relativamente grande (ou non tan grande, dependendo do contexto) alcance tamaños masivos. Por suposto, calquera avance tecnolóxico trae consigo oportunidades de investigación sobre como mellorar as novas tecnoloxías e aplicalas para resolver problemas que importan ás persoas e a sociedade en xeral. Así, esta tese céntrase en investigar solucións para a representación de mapas e os movementos de persoas e obxectos neses mapas ao longo do tempo. O traballo realizado céntrase en facilitar a representación eficiente, tanto dende o punto de vista espacial como no tempo de acceso aos datos, de mapas e traxectorias, utilizando estruturas de datos compactas que almacenan a información nun formato comprimido ao tempo que permiten a súa explotación sen necesidade de un proceso de descompresión previo. A nosa primeira contribución é unha estratexia para representar mapas a diferentes escalas ou niveis de zoom dun xeito compacto. A maioría dos sistemas que traballan con mapas, como Google Maps e similares, gardan diferentes versións do mesmo mapa en diferentes niveis de detalle pensados para diferentes niveis de zoom. Isto xera unha gran cantidade de información redundante que é necesario almacenar. Isto ocorre porque, por exemplo, aínda que unha liña de costa parece moito máis simplificada cun zoom baixo, utilizando moitos menos puntos xeográficos que cun zoom alto, os puntos visibles existirán en todos os niveis de zoom sucesivos. Ao aumentar o zoom, só se engadirán aos novos puntos que dan máis detalle á forma. A nosa proposta é capaz de representar diferentes niveis de zoom sen repetir ningún punto xeográfico entre eles, mellorando moito o almacenamento en comparación coas solucións típicas. A nosa segunda contribución é un sistema de posicionamento en interiores, capaz de captar as traxectorias dos usuarios nun espazo de movemento limitado e anotado semanticamente (por exemplo, un centro comercial ou centro médico onde a distribución do espazo informa obviamente das posibilidades de movemento e os cuartos e os segmentos do corredor pódense etiquetar con identificadores únicos) e comprimirse nunha estrutura de datos compacta con tempos de acceso aos movementos de calquera usuario nun período de tempo determinado moi por debaixo do milisegundo. Finalmente, a última contribución desta tese é o traballo realizado no marco dun ambicioso proxecto de investigación enfocado á análise e explotación dos movementos de viaxeiros nas redes de transporte público. Mediante os rexistros da tarxeta de viaxeiro, ofrecemos solucións para almacenar e explotar viaxes dunha parada de orixe a outra de destino dos usuarios da rede de transporte., Ministerio de Ciencia, Innovación e Universidades; BIZDEVOPS-GLOBAL; RTI2018-098309-B-C32, Ministerio de Economía y Competitividad; TIN2016-78011-c4-1-R, Xunta de Galicia; COV20/00604, Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; IN852A 2018/14, Xunta de Galicia; IG240.2020.1.185, Los trabajos llevados a cabo como parte de esta tesis han sido parcialmente financiados por el centro de investigación CITIC, financiado por la Xunta de Galicia a través del acuerdo de colaboración entre el Ministerio de Educación, Formación Profesional y Universidades, y las universidades gallegas para el refuerzo de los centros de investigación de la Red de Centros de Investigación del Sistema Universitario de Galicia (CIGUS); por el GRC: ED431C 2021/53, parcialmente financiado por GAIN/Xunta de Galicia, y por los siguientes proyectos de investigación y subvenciones: • MAGIST: PID2019-105221RB-C41, financiado por MCIN / AEI / 10.13039 / 501100011033. • EXTRACompact: PID2020-114635RB-I00, financiado por MCIN / AEI / 10.13039 / 501100011033. • SIGTRANS: PDC2021-120917-C21, financiado por MCIN / AEI / 10.13039 / 501100011033 and “NextGenerationEU”/PRTR». • PLAGEMIS: TED2021-129245B-C21, financiado por MCIN / AEI / 10.13039 / 501100011033 and “NextGenerationEU”/PRTR. • OASSIS: PID2021-122554OB-C33, financiado por MCIN / AEI / 10.13039 / 501100011033 and EU/ERDF A way of making Europe. • EarthDL: PID2022-141027NB-C21, financiado por MCIN / AEI / 10.13039 / 501100011033 and EU/ERDF A way of making Europe. • FLATCITY-POC: PDC2021-121239-C31, financiado por MCIN / AEI / 10.13039 / 501100011033 and “NextGenerationEU” / PRTR • STEPS: RTC-2017-5908-7, financiado por Ministerio de Ciencia, Innovación y Universidades, AEI, co-funded 80% by Fondos FEDER, Programa Retos Colaboración, 2017. • BIZDEVOPS: RTI2018-098309-B-C32, financiado por Ministerio de Ciencia, Innovación e Universidades. Convocatoria del 2018 para projectos I+D+i "Retos investigación". • Datos 4.0: TIN2016-78011-C4-1-R, financiado por Ministerio de Economía e Competitividade, Programa Retos da Sociedade, convocatoria de 2016. • CEDCOVID: COV20/00604, financiado por Axencia Galega de Innovación, Proxecto Programas Autonómicos. • Convocatoria Conecta COVID: IN852D 2021/3, financiado por UE, FEDER, GAIN, Convocatoria Conecta COVID. • GRC: ED431C 2017/58, financiado por GAIN / Xunta de Galicia. • GEMA: IN852A 2018/14, financiado por Xunta de Galicia / FEDER-UE, and ConectaPeme. • LEMSI: financiado por IG240.2020.1.185, Xunta de Galicia / Igape. El trabajo realizado en varias publicaciones como parte del desarrollo de esa tesis también estuvo financiado por el programa de becas FPI [BES-2017-081390], la beca Fondecyt #11221029 de la Universidad Austral de Chile, y por la beca predoctoral de la Xunta de Galicia ED481A-2021/183.
RUC. Repositorio da Universidade da Coruña
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación Contribución de congreso (ConferenceOutput)

Data Extraction in Insurance Photo-Inspections Using Computer Vision

  • Gende, M.
  • Ortega Hortas, Marcos
  • Penedo, Manuel
[Abstract] Recent advances in computer vision and artificial intelligence allow for a better processing of complex information in many fields of human activity. One such field is vehicle expertise and inspection. This paper presents the development of systems for the automatic reading of French and Spanish license plates, as well as odometer value reading in dashboard photographs. These were trained and validated with real examples of more than 4000 vehicles, while addressing typical problems with irregular data acquisition. The systems proposed have found use in a real environment and are employed as assistance in vehicle appraisal., This research was co-funded by Ministerio de Ciencia, Innovación y Universidades and the European Union (European Regional Development Fund—ERDF) as part of the RTC-2017-5908-7 research project. We wish to acknowledge the support received from the Centro de Investigación de Galicia CITIC, funded by Consellería de Educación, Universidade e Formación Profesional from Xunta de Galicia and European Union. (European Regional Development Fund - FEDER Galicia 2014-2020 Program) by grant ED431G 2019/01, Xunta de Galicia; ED431G 2019/01