Pasar al contenido principal

Resultados relacionados

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

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

A novel architecture for the detection, exploitation and historical archival of indoor semantic trajectories: A case study on nursing homes

  • Varela Rodeiro, Tirso
  • Gutiérrez-Asorey, Pablo
  • Brisaboa, Nieves R.
  • Penabad, Miguel R.
  • Cortiñas, Alejandro
This author accepted manuscript is deposited under a Creative Commons Attribution Noncommercial 4.0 International (CC BY-NC) licence. This means that anyone may distribute, adapt, and build upon the work for non-commercial purposes, subject to full attribution. If you wish to use this manuscript for commercial purposes, please contact permissions@emerald.com., [Abstract]: We introduce an automatic system, based on indoor positioning techniques, aimed at improving the quality of service of a nursing home. It tracks the location of both residents and caregivers and automatically detects the activities taking place. The system presents a hybrid approach for storing large amounts of data, using both a traditional relational database and an ad-hoc compact data structure, enabling compact storage of the information without compromising fast random access. Our proposal is complemented by a graphical user interface that can dynamically display collected trajectories within the facilities. Having access to all this information, our system will be able to evaluate the quality of health care offered to their residents, as well as assess the efficiency of the nursing home as a business., CITIC, as a center accredited for excellence within the Galician University System and a member of the CIGUS Network, receives subsidies from the Department of Education, Science, Universities, and Vocational Training of the Xunta de Galicia. Additionally, it is cofinanced by the EU through the FEDER Galicia 2021-27 operational program (Ref. ED431G 2023/01); and by FEDER Galicia 2014-2020 80%, SXU 20% [CSI: ED431G 2019/01]; MCIN/AEI/10.13039/501100011033 ([EXTRA-Compact: PID2020-114635RB-I00]; “NextGenerationEU” /PRTR [SIGTRANS: PDC2021-120917-C21], [PLAGEMIS: TED2021-129245B-C21], [FLATCITY: PDC2021-121239-C31]; EU/ERDF A way of making Europe [OASSIS-UDC: PID2021-122554OB-C3], [EarthDL: PID2022-141027NB-C21]); by GAIN/Xunta de Galicia [GRC: ED431C 2021/53]; by UE FEDER [0079 ATEMPO 6 E],[0064 GRESINT 1 E]., Xunta de Galicia; ED431G 2023/01, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/53
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Two-Dimensional Block Trees

  • Brisaboa, Nieves R.
  • Gagie, Travis
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
[Absctract]: The Block Tree is a data structure for representing repetitive sequences in compressed space, which reaches space comparable with that of Lempel–Ziv compression while retaining fast direct access to any position in the sequence. In this paper, we generalize Block Trees to two dimensions, in order to exploit repetitive patterns in the representation of images, matrices and other kinds of bidimensional data. We demonstrate the practicality of the two-dimensional Block Trees (2D-BTs) in representing the adjacency matrices of Web graphs, and raster images in GIS applications. For this purpose, we integrate our 2D-BT with the k2-tree—an efficient structure that exploits clustering and sparseness to compress adjacency matrices—so that it also exploits repetitive patterns. Our experiments show that this structure uses 60–80% of the space of the original k2-tree, while being 30% faster to three times slower when accessing cells., This work was supported by Centro de Investigación en TIC, as Research Center accredited by Galician University System, is funded by Xunta de Galicia, FEDER Galicia 2014-2020 80%, SXU 20% [grant number ED431G 2019/01 to N.R.B and A.G]; GAIN/Xunta de Galicia [grant number ED431C 2021/53 (GRC) to N.R.B and A.G]; Xunta de Galicia/FEDER-UE [grant numbers IN852D 2021/3 to N.R.B and A.G]; Ministerio de Ciencia e Innovación [grant numbers PID2020-114635RB-I00 and PDC2021-120917-C21 to N.R.B and A.G]; Fondo Nacional de Desarrollo Científico y Tecnológico [grant number 1-200038 to G.N., grant number 1171058 to T.G.]; Agencia Nacional de Investigación y Desarrollo (ANID) – Basal Funds, Chile [grant number FB0001 to T.G, A.G, and G.N]; and The Natural Sciences and Engineering Research Council Discovery Grant [grant number RGPIN-07185-2020 to T.G.]., Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IN852D 2021/3, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-200038, Chile. Agencia Nacional de Investigación y Desarrollo (ANID). Chile; FB0001, Canada. Natural Science and Engineering Research Council (NSERC); RGPIN-07185-2020
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Space/time-efficient RDF stores based on circular suffix sorting

  • Brisaboa, Nieves R.
  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Fariña, Antonio
  • Navarro, Gonzalo
This version of the article 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/s11227-022-04890-w, [Abstract]: The resource description framework (RDF) has gained popularity as a format for the standardized publication and exchange of information in the Web of Data. In this paper, we introduce RDFCSA, a compressed representation of RDF datasets that in addition supports efficient querying. RDFCSA regards the triples of the RDF store as short circular strings and applies suffix sorting on those strings, so that triple-pattern queries reduce to prefix searching on the string set. The RDF store is then represented compactly using a compressed suffix array (CSA), a proved technology in text indexing that efficiently supports prefix searches. Our experiments show that RDFCSA is competitive with state-of-the-art alternatives. It compresses the raw data to 60% of its size, close to the most compact alternatives. While most alternatives perform better in some kinds of triple-patterns than in others, RDFCSA features fast and consistent query times, a few microseconds per result in all cases. This enables efficiently supporting join queries by using either merge- or chaining-join strategies over the triple patterns coupled with some specific optimizations such as variable filling. Our experiments on binary joins show that RDFCSA is faster than the alternatives in most cases., Funding for the Spanish group: projects funded by MCIN/ AEI/10.13039/501100011033: PDC2021-121239-C31 (FLATCITY-POC)-“NextGenerationEU”/PRTR; PDC2021-120917-C21 (SIGTRANS)-“NextGenerationEU”/PRTR; PID2020-114635RB-I00 (EXTRACompact); PID2019-105221RB-C41 (MAGIST); PID2021-122554OB-C33 (OASSIS-UDC); and TED2021-129245B-C21 (PLAGEMIS-UDC); grant ED431C 2021/53 (GRC) funded by GAIN/Xunta de Galicia; and grant ED431G 2019/01 (CSI) funded by Xunta de Galicia, FEDER Galicia 2014-2020 80%, SXU 20%; Gonzalo Navarro is partially funded by Fondecyt 1-200038, and by ANID - Millennium Science Initiative Program - Code ICN17 002., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431G 2019/01, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-200038., Chile. Agencia National de Investigación y Desarrollo; ICN17_002
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Optimizing RPQs over a compact graph representation

  • Arroyuelo, Diego
  • Gómez-Brandón, Adrián
  • Hogan, Aidan
  • Navarro, Gonzalo
  • Rojas-Ledesma, Javiel
©2023 This version of the article 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/s00778-023-00811-2, [Absctract]: We propose techniques to evaluate regular path queries (RPQs) over labeled graphs (e.g., RDF). We apply a bit-parallel simulation of a Glushkov automaton representing the query over a ring: a compact wavelet-tree-based index of the graph. To the best of our knowledge, our approach is the first to evaluate RPQs over a compact representation of such graphs, where we show the key advantages of using Glushkov automata in this setting. Our scheme obtains optimal time, in terms of alternation complexity, for traversing the product graph. We further introduce various optimizations, such as the ability to process several automaton states and graph nodes/labels simultaneously, and to estimate relevant selectivities. Experiments show that our approach uses 3–5X less space, and is over 5 X faster, on average, than the next best state-of-the-art system for evaluating RPQs., This work was supported by ANID—Millennium Science Initiative Program—Code ICN17_002; Fondecyt Grant 1-230755; Fondecyt Grants 1221926 and 1-200038; Xunta de Galicia, FEDER Galicia 2014-2020 80%, SXU 20% Grant ED431G 2019/01; GAIN/Xunta de Galicia Grant ED431C 2021/53 (GRC); Xunta de Galicia/FEDER-UE Grant IN852D 2021/3; Ministerio de Ciencia e Innovación Grants PID2020-114635RB-I00 and PDC2021-120917-C21., Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-230755, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1221926, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-221926, Xunta de Galicia; ED431G 2019/01, Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IN852D 2021/3
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Faster compressed quadtrees

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

LITHEUM. A web-based lighting and thermal urban model for city energy assessment

  • Rodríguez-Álvarez, Jorge
  • Rodríguez Luaces, Miguel
  • Varela Rodeiro, Tirso
  • Alvaredo López, Natalia
  • Lamas Sardiña, Víctor Juan
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: This study presents Litheum (LIghting and THErmal Urban Model), an online urban building energy modelling (UBEM) tool that integrates morphological sensitivity analysis with interactive scenario development. By leveraging Geographic Information Systems and open-source technologies, the model addresses the accessibility challenges of previous UBEM tools, offering an intuitive web-based application suitable for diverse users, from homeowners to planners and policymakers, without requiring prior energy modelling expertise. Litheum applies a novel algorithm to calculate solar obstruction, optimizing computational requirements while capturing the spatial and temporal dynamics of urban contexts, an area where data-driven models often fall short. The energy calculation methods follow the EN ISO 52016–1 standard, balancing precision, flexibility, and reproducibility for large-scale applications. Unlike detailed dynamic building simulation tools, Litheum is optimized for urban energy planning and policy development. Pilot studies in three Spanish cities—Pontevedra, A Coruña, and Madrid—demonstrated the model's adaptability across varying urban scales. Feedback informed enhancements, including a solar control mode functionality for warmer climates. The online platform's design enables seamless interaction and rapid deployment in diverse urban settings. Future efforts will focus on expanding the platform's deployment in additional cities, integrating artificial intelligence to infer key building characteristics, such as glazing ratios, to improve robustness and processing efficiency. Litheum exemplifies the potential of open-source UBEM tools to facilitate energy assessment, fostering widespread adoption and better informed planning decisions., The research reported in this article was funded by MCIN/ AEI/10.13039/501100011033/ and by “European Union NextGenerationEU/PRTR, with the Grant TED2021–130779A-I00 The CITIC Database Lab authors acknowledge the support by the CITIC, as a center accredited for excellence within the Galician University System and a member of the CIGUS Network, receives subsidies from the Department of Education, Science, Universities, and Vocational Training of the Xunta de Galicia. Additionally, it is co-financed by the EU through the FEDER Galicia 2021–27 operational program (Ref. ED431G 2023/01); and by MCIN/ AEI/10.13039/501100011033 ([EXTRA-Compact: PID2020–114635RB-I00]; “NextGenerationEU”/PRTR [SIGTRANS: PDC2021–120917-C21], [PLAGEMIS: TED2021–129245B-C21]; EU/ERDF A way of making Europe [EarthDL: PID2022–141027NB-C21] partially funded by MCIN/AEI/10.13039/501100011033 and EU/ERDF A way of making Europe); by GAIN/Xunta de Galicia [GRC: ED431C 2021/53]; by UE FEDER [0079_ATEMPO_6_E], [0064_GRESINT_1_E] and by INE [CIDMEFEO]. Jorge Rodríguez-Álvarez acknowledges the support of the Ministry for Digital Transformation and Civil Service and Next-GenerationEU/RRF under Grant TSI-100925–2023–1 to support the development of the model with AI techniques; and MCIN/ AEI/10.13039/501100011033/and by ERDF A way of making Europe for the assistance in the continuation of the project for the adaptation of the model to rural areas with the Grant PID2021‐123961OA‐I00. Funding for open access charge: Universidade da Coruña/CISUG.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space

  • Arroyuelo, Diego
  • Gómez-Brandón, Adrián
  • Hogan, Aidan
  • Navarro, Gonzalo
  • Reutter, Juan
  • Rojas-Ledesma, Javiel
  • Soto, Adrián
© ACM 2024. This is the author's version of the work (accepted manuscript or postprint). It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Database Systems, https://doi.org/10.1145/3644824, [Absctract]: We present an indexing scheme for triple-based graphs that supports join queries in worst-case optimal (wco) time within compact space. This scheme, called a ring, regards each triple as a cyclic string of length 3. Each rotation of the triples is lexicographically sorted and the values of the last attribute are stored as a column, so we obtain the order of the next column by stably re-sorting the triples by its attribute. We show that, by representing the columns with a compact data structure called a wavelet tree, this ordering enables forward and backward navigation between columns without needing pointers. These wavelet trees further support wco join algorithms and cardinality estimations for query planning. While traditional data structures such as B-Trees, tries, and so on, require 6 index orders to support all possible wco joins over triples, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space, thus supporting wco joins in almost no space beyond storing the graph itself. Experiments querying a large graph (Wikidata) in memory show that the ring offers nearly the best overall query times while using only a small fraction of the space required by several state-of-the-art approaches. We then turn our attention to some theoretical results for indexing tables of arity d higher than 3 in such a way that supports wco joins. While a single ring of length d no longer suffices to cover all d! orders, we need much fewer rings to index them all: O(2d) rings with a small constant. For example, we need 5 rings instead of 120 orders for d=5. We show that our rings become a particular case of what we dub order graphs, whose nodes are attribute orders and where stably sorting by some attribute leads us from an order to another, thereby inducing an edge labeled by the attribute. The index is then the set of columns associated with the edges, and a set of rings is just one possible graph shape. We show that other shapes, like for example a single ring instead of several ones of length d, can lead us to even smaller indexes, and that other more general shapes are also possible. For example, we handle d=5 attributes within space equivalent to 4 rings., We thank Amine Mhedhbi for help with Graphflow and Daniela Campos for help with CompactLTJ. This work was supported by ANID – Millennium Science Initiative Program – Code ICN17_002. Gómez-Brandón was supported in part by MCIN/AEI/10.13039/5011000-11033: grants PID2020- 114635RB-I00; by MCIN/AEI/10.13039/501100011033 and EU/ERDF "A way of making Europe": PID2022-141027NB-C21; by MCIN/AEI/10.13039/501100011033 and “Next-GenerationEU”/ PRTR: grants TED2021-129245B-C21, PDC2021-120917-C21 and by GAIN/ Xunta de Galicia: GRC: grants ED431C 2021/53, and CIGUS 2023-2026. Hogan was supported by FONDECYT Grant No. 1221926. Navarro was supported by FONDECYT Grant No. 1230755. Reutter was supported by FONDECYT Grant No. 1221799., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; CIGUS 2023-2026, Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1221926, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1230755, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1221799
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Map algebra on raster datasets represented by compact data structures

  • Silva-Coira, Fernando
  • Paramá, José R.
  • Ladra, Susana
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract]: The increase in the size of data repositories has forced the design of new computing paradigms to be able to process large volumes of data in a reasonable amount of time. One of them is in-memory computing, which advocates storing all the data in main memory to avoid the disk I/O bottleneck. Compression is one of the key technologies for this approach. For raster data, a compact data structure, called (Formula presented.) -raster, have been recently been proposed. It compresses raster maps while still supporting fast retrieval of a given datum or a portion of the data directly from the compressed data. (Formula presented.) -raster's original work introduced several queries in which it was superior to competitors. However, to be used as the basis of an in-memory system for raster data, it is mandatory to demonstrate its efficiency when performing more complex operations such as the map algebra operators. In this work, we present the algorithms to run a set of these operators directly on (Formula presented.) -raster without a decompression procedure., This work was supported by the National Natural Science Foundation of China (Grant Nos. 31171944, 31640068), Anhui Provincial Natural Science Foundation (Grant No. 2019B319), Earmarked Fund for Anhui Science and Technology Major Project (202003b06020016). Information CITIC, Ministerio de Ciencia e Innovación, Grant/Award Numbers: PID2020-114635RB-I00; PDC2021-120917-C21; PDC2021-121239-C31; PID2019-105221RB-C41; TED2021-129245-C21; Xunta de Galicia, Grant/Award Numbers: ED431C 2021/53; IN852D 2021/3 (CO3)This work was partially supported by CITIC, CITIC is funded by the Xunta de Galicia through the collaboration agreement between the Department of Culture, Education, Vocational Training and Universities and the Galician universities for the reinforcement of the research centers of the Galician University System (CIGUS). IN852D 2021/3(CO3): partially funded by UE, (ERDF), GAIN, convocatoria Conecta COVID. GRC: ED431C 2021/53: partially funded by GAIN/Xunta de Galicia. TED2021-129245B-C21; PDC2021-121239-C31; PDC2021-120917-C21: partially funded by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR. PID2020-114635RB-I00; PID2019-105221RB-C41: partially funded by MCIN/AEI/10.13039/501100011033. Funding for open access charge: Universidadeda Coruña/CISUG., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IN852D 2021/3 (CO3), National Natural Science Foundation of China; 31171944, National Natural Science Foundation of China; 31640068, Anhui Provincial Natural Science Foundation; 2019B319
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)

Onto how compression yields energy-efficient text search

  • Fariña, Antonio
  • Poy, Olivia
  • Brisaboa, Nieves R.
  • Calero, Coral
  • Moraga, Mª Ángeles
  • Pedreira, Óscar
[Abstract]: In the last two decades, word-based text compression has shown to be the key to efficiently handling large collections of text not only due to yielding important storage savings but, more importantly, because it allowed boosting the performance of some traditional text retrieval systems. The reason is that when the appropriate compression techniques are chosen, compressed text search becomes much faster than searches on plain text, and retrieval/decompression could start at any part of the compressed data, hence allowing to keep the text collection compressed all the time. Word-based text compressors have been typically compared in terms of their compression effectiveness, encoding/decoding speed, and performance when searching for words. In this paper, we show that compression also has benefits in terms of energy efficiency when performing word-based searches. Particularly, our experiments considering searches performed over uncompressed text and text compressed with the most well-suited compressors for text databases showed energy savings of around 30–70%. These savings are obtained thanks to improvements in search time but also, rather unexpectedly, because compressed text searches typically require less power from the processor. We have also analyzed how small modifications to the Horspool search algorithm can lead to time savings and can reduce even further the power needs of the processor (up to 5–10%), and, consequently, the overall energy consumption., This work was partially funded by MCIN/AEI/10.13039/501100011033 and EU/ ERDF: grant PID2021-122554OB-C33 (OASSIS); by MCIN/AEI/ 10.13039/501100011033 and European Union NextGenerationEU/PRTR: grant TED2021-129245B-C21 (PLAGEMIS). Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. The group from Castilla - La Mancha is funded in part by CECD (JCCM) and FEDER funds: grant SBPLY/21/180501/000115 (EMMA). The group from A Coruña is also funded in part by MCIN/ AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR: grants PDC2021-121239-C31 (FLATCITY-POC), PDC2021-120917-C21 (SIGTRANS), and PID2020-114635RB-I00 (EXTRA-Compact); by GAIN/Xunta de Galicia: grant GRC: ED431C 2021/53; by UE, (ERDF), GAIN, Convocatoria Conecta COVID: grant IN852D 2021/3 (CO3)., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; IN852D 2021/3, Junta Castilla-La Mancha; SBPLY/21/180501/000115
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)

Classic Distance Join Queries Using Compact Data Structures

  • Bernardo, Guillermo de
  • Penabad, Miguel R.
  • Corral, Antonio
  • Brisaboa, Nieves R.
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG, [Abstract] Distance-based Join Queries (DJQs) have multiple applications in spatial databases, Geographic Information Systems, and other areas. The 𝐾 Closest Pairs Query (𝐾CPQ) and the 𝜀 Distance Join Query (𝜀DJQ) are well-known DJQs that have been widely studied and can be solved using plane-sweep techniques, which are efficient but must keep the whole datasets in main memory. In this work, we propose DJQ algorithms that work with data represented using a 𝑘2-tree, a compact data structure for binary grids. Our algorithms solve 𝐾CPQ and 𝜀DJQ queries, as well as several window-constrained variants, taking advantage of the indexing capabilities of 𝑘2-trees to efficiently answer queries without the need to decompress the data. Our experimental evaluation with large datasets shows that 𝑘2-tree algorithms are up to 5 times faster than plane-sweep algorithms in 𝐾CPQ, and 5–30 times faster in 𝜀DJQ. In variants that are window-constrained, our algorithms are competitive in most scenarios and faster for large windows. Additionally, our algorithms are not very affected by the distribution of the data and yield much more predictable query times, showing up to 30 times smaller variance in query times than plane sweep, depending on the location of the query window., Guillermo de Bernardo, Miguel R. Penabad and Nieves R. Brisaboa are partially funded by MCIN/AEI/10.13039/501100011033 and EU/ERDF A way of making Europe [PID2021-122554OB-C33 (OASSIS)]; by MCIN/AEI/10.13039/501100011033 [PID2020-114635RB-I00 (EXTRACompact), PID2019-105221RB-C41 (MAGIST)]; by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR [TED2021-129245B-C21 (PLAGEMIS), PDC2021-121239-C31 (FLATCITY-POC), PDC2021-120917-C21 (SIGTRANS)]; and by GAIN/Xunta de Galicia [ED431C 2021/53]. CITIC is funded by the Xunta de Galicia through the collaboration agreement between the Department of Culture, Education, Vocational Training and Universities and the Galician universities for the reinforcement of the research centers of the Galician University System (CIGUS) [ED431G 2019/01 (CSI)]. The work by Antonio Corral was partially funded by the EU ERDF and the Andalusian Government (Spain) under the project UrbanITA (ref. PY20_00809) and grant PID2021-124124OB-I00 funded by the Spanish Government MCIN/AEI/10.13039/501100011033 and the “ERDF A way of making Europe”. Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Compressed and queryable self-indexes for RDF archives

  • Cerdeira-Pena, Ana
  • Bernardo, Guillermo de
  • Fariña, Antonio
  • Fernández, Javier D.
  • Martínez-Prieto, Miguel A.
This version of the article has been accepted for publication, after peer review and is subject to Knowledge and Information Systems , 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/s10115-023-01967-7, [Abstract]: RDF compression and querying are consolidated topics in the Web of Data, with a plethora of solutions to efficiently store and query static datasets. However, as RDF data changes along time, it becomes necessary to keep different versions of RDF datasets, in what is called an RDF archive. For large RDF datasets, naive techniques to store these versions lead to significant scalability problems. In this paper, we present v-RDF-SI, one of the first RDF archiving solutions that aim at joining both compression and fast querying. In v-RDF-SI, we extend existing RDF representations based on compact data structures to provide efficient support of version-based queries in compressed space. We present two implementations of v-RDF-SI, named v-RDFCSA and v-HDT, based, respectively, on RDFCSA (an RDF self-index) and HDT (a W3C-supported compressed RDF representation). We experimentally evaluate v-RDF-SI over a public benchmark named BEAR, showing that v-RDF-SI drastically reduces space requirements, being up to 40 times smaller than the baselines provided by BEAR, and 4 times smaller than alternatives based on compact data structures, while yielding significantly faster query times in most cases. On average, the fastest variants of v-RDF-SI outperform the alternatives by almost an order of magnitude., The first three co-authors are members of the CITIC, which, as Research Center accredited by the Galician University System, is funded by Consellería de Cultura, Educación e Universidades 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]. The Spanish group is also funded by Xunta de Galicia/FEDER-UE [ED431C 2021/53]; by MICINN [Magist: PID2019-105221RB-C41; FLATCity-POC: PDC2021-121239-C31; SIGTRANS: PDC2021-120917-C21; EXTRA-Compact: PID2020-114635RB-I00; PID2019-105221RB-C41]; by MCIU-AEI/FEDER-UE [BIZDEVOPS: RTI2018-098309-B-C32]; and by Xunta de Galicia/Igape/IG240.2020.1.185., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431G 2019/01
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Space-Efficient Data Structures for the Inference of Subsumption and Disjointness Relations

  • Fuentes Sepúlveda, José
  • Gatica, Diego
  • Navarro, Gonzalo
  • Rodríguez, M. Andrea
  • Seco, Diego
The data that support the findings of this study are openly available in GBP at https://github.com/dgaticar., [Abstract]: Conventional database systems function as static data repositories, storing vast amounts of facts and offering efficient query processing capabilities. The sheer volume of data these systems store has a direct impact on their scalability, both in terms of storage space and query processing time. Deductive database systems, on the other hand, require far less storage space since they derive new knowledge by applying inference rules. The challenge is how to efficiently obtain the required derivations, compared to having them in explicit form. In this study, we concentrate on a set of predefined inference rules for subsumption and disjointness relations, including their negations. We use compact data structures to store the facts and provide algorithms to support each type of relation, minimizing even further the storage space requirements. Our experimental findings demonstrate the feasibility of this approach, which not only saves space but is often faster than a baseline that uses well-known graph traversal algorithms implemented on top of a traditional adjacency list representation to derive the relations., This work was funded by: ANID Millennium Science Initiative Program - Code ICN17_002; ANID Grant 77190038 and FONDECYT Grant 11220545 (1st author); PFCHA/Doctorado Nacional/2020-21201986 (2nd author); FONDECYT Grant1-230755 (3rd author); GRC: ED431C 2021/53, partially funded by GAIN/Xunta de Galicia; PID2022-141027NB-C21(EarthDL), TED2021-129245B-C21 (PLAGEMIS), PID2020-114635RB-I00 (EXTRACompact), PDC2021-121239-C31(FLATCity-POC), and PDC2021-120917-C21 (SIGTRANS): partially funded by MCIN/AEI/10.13039/501100011033 and“NextGenerationEU”/PRTR (5th author). CITIC is funded by the Xunta de Galicia through the collaboration agreementbetween the Department of Culture, Education, Vocational Training and Universities and the Galician Universities forthe reinforcement of the research centers of the Galician University System (CIGUS)., Chile. Agencia National de Investigación y Desarrollo; ICN17_002, Chile. Agencia National de Investigación y Desarrollo; 77190038, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 11220545, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 1-230755, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 2020-21201986, Xunta de Galicia; ED431C2021/53
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

TRGST: An enhanced generalized suffix tree for topological relations between paths

  • Quijada Fuentes, Carlos
  • Rodríguez, M. Andrea
  • Seco, Diego
©2024 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 Journal of Controlled Release. The Version of Record is available online at https://doi.org/10.1016/j.is.2024.102406, Versión aceptada, [Abstract]: This paper introduces the TRGST data structure, which is designed to handle queries related to topological relations between paths represented as sequences of stops in a network. As an example, these paths could correspond to stops on a public transport network, and a query of interest is to retrieve paths that share at least k consecutive stops. While topological relations among spatial objects have received extensive attention, the efficient processing of these relations in the context of trajectory paths, considering both time and space efficiency, remains a relatively less explored domain. Taking inspiration from pattern matching implementations, the TRGST data structure is constructed on the foundation of the Generalized Suffix Tree. Its purpose is to provide a compact representation of a set of paths and to efficiently handle topological relation queries by leveraging the pattern search capabilities inherent in this structure. The paper provides a detailed account of the structure and algorithms of TRGST, followed by a performance analysis utilizing both real and synthetic data. The results underscore the remarkable scalability of the TRGST in terms of both query time and space utilization., This work was funded by: ANID Millennium Science Initiative Program, Chile - Code ICN17_002 (1st and 2nd author); ANID, Chile PFCHA/Doctorado Nacional/21200101 (1st author); CYTED, Spain grant 519RT0579 (1st and 3rd author); Ministerio de Ciencia e Innovación, Spain (partially funded by MCIN/AEI/10.13039/501100011033 and \u201CNextGenerationEU\u201D/PRTR) PID2022-141027NB-C21 EarthDL, TED2021-129245B-C21 PLAGEMIS, PID2020-114635RB-I00 EXTRACompact, PDC2021-121239-C31 FLATCity-POC, PDC2021-120917-C21 SIGTRANS; and GAIN/Xunta de Galicia, Spain GRC: ED431C 2021/53 (3rd author)., Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Ministerio de Educación; 21201986, Chile. Agencia Nacional de Investigación y Desarrollo; 519RT0579, Xunta de Galicia; ED431C 2021/53
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Compact representations of spatial hierarchical structures with support for topological queries

  • Fuentes Sepúlveda, José
  • Gatica, Diego
  • Navarro, Gonzalo
  • Rodríguez, M. Andrea
  • Seco, Diego
©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.ic.2023.105029, [Abstract]: Among different spatial data models, the topological model for spatial regions explicitly represents common boundaries. This model pursues the efficiency of topology-related queries and the elimination of data redundancy. This paper proposes several space-efficient data structures to support access to the topological representation of two-dimensional regions that are organized in a multi-granular or hierarchical structure, such as the political and administrative partition of a country. In the context of these hierarchies, we focus on queries that search for inclusion, disjointness, and adjacency between regions. The proposed structures build upon compact planar graph embeddings, which show to have a good trade-off between space and time., This work was funded by: ANID Millennium Science Initiative Program - Code ICN17_002 ; PAI grant PAI77190038 (1st author); PFCHA/Doctorado Nacional/2020-21201986 (2nd author); FONDECYT Grant 1-200038 (3rd author); CYTED grant 519RT0579 (4th and 5th authors); GRC: ED431C 2021/53 , partially funded by GAIN/Xunta de Galicia (5th author); TED2021-129245B-C21 (PLAGEMIS), PDC2021-120917-C21 (SIGTRANS), PID2020-114635RB-I00 (EXTRACompact) and PID2019-105221RB-C41 (MAGIST), partially funded by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR (5th author). An early partial version of this paper appeared in Proc. DCC 2021 [1] ., Xunta de Galicia; ED431C 2021/53, Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002, Chile. Agencia Nacional de Investigación y Desarrollo; PAI77190038, Chile. Ministerio de Educación; PFCHA/Doctorado Nacional/2020-21201986, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 1-200038, Chile. Agencia Nacional de Investigación y Desarrollo; 519RT0579
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Clustering-Based Compression for Raster Time Series

  • Muñoz, Martita
  • Fuentes Sepúlveda, José
  • Hernández, Cecilia
  • Navarro, Gonzalo
  • Seco, Diego
  • Silva-Coira, Fernando
Real world datasets, and scripts to generate the synthetic and semi-synthetic datasets are available at https://figshare.com/s/5ad53959f8eed8a83f83., [Abstract]: A raster time series is a sequence of independent rasters arranged chronologically covering the same geographical area. These are commonly used to depict the temporal evolution of represented variables. The T-k2-raster is a compact data structure that performs very well in practice for compact representations for raster time series. This structure classifies each raster as a snapshot or a log and encodes logs concerning their reference snapshots, which are the immediately preceding selected snapshots. An enhanced version of the T-k2-raster, called Heuristic T-k2-raster, incorporates a heuristic for automating the selection of snapshots. In this study, we investigate the optimality of the heuristic employed in Heuristic T-k2- raster by comparing it with a dynamic programming approach. Our experimental evaluation demonstrates that Heuristic T-k2-raster is a near-optimal solution, achieving compression performance almost identical to the dynamic programming method. These results indicate that variations of the structure that maintain the temporal order of the rasters are unlikely to significantly improve compression. Consequently, we explore an alternative approach based on clustering, where rasters are grouped according to their similarity, regardless of their temporal order. Our experimental evaluation reveals that this clustering-based strategy can enhance compression in scenarios characterized by cyclic behavior., This work was supported by the Agencia Nacional de Investigación y Desarrollo [21200810 to M.M. and FONDECYT grants 11220545 to J.F. and 1-230755 to G.N.]; the Centre for Biotechnology and Engineering [FB0001 to M.M., C.H., and G.N.]; the Agencia Nacional de Investigación y Desarrollo – Millennium Science Initiative Program [ICN17_002 to M.M., J.F., and G.N.]; and PID2022-141027NB-C21 (EarthDL), TED2021-129245B-C21 (PLAGEMIS), PID2020-114635RB-I00 (EXTRACompact), PDC2021-121239-C31 (FLATCITY-POC), and PDC2021-120917-C21 (SIGTRANS): partially funded by MCIN/AEI/10.13039/501100011033 and ’NextGenerationEU’/PRTR, GRC: ED431C 2021/53, partially funded by GAIN/Xunta de Galicia [D.S. and F.S.]. CITIC is funded by the Xunta de Galicia through the collaboration agreement between the Department of Culture, Education, Vocational Training and Universities, and the Galician universities for the reinforcement of the research centers of the Galician University System (CIGUS)., Chile. Agencia National de Investigación y Desarrollo; 21200810, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 11220545, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 1-230755, Chile. Centre for Biotechnology and Engineering; FB0001, Chile. Agencia National de Investigación y Desarrollo; ICN17_002, Xunta de Galicia; ED431C2021/53
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Stronger compact representations of object trajectories

  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Paramá, José R.
  • Brisaboa, Nieves R.
  • Gagie, Travis
[Absctract]: GraCT and ContaCT were the first compressed data structures to represent object trajectories, demonstrating that it was possible to use orders of magnitude less space than classical indexes while staying competitive in query times. In this paper we considerably enhance their space, query capabilities, and time performance with three contributions. (1) We design and evaluate algorithms for more sophisticated nearest neighbor queries, finding the trajectories closest to a given trajectory or to a given point during a time interval. (2) We modify the data structure used to sample the spatial positions of the objects along time. This improves the performance on the classic spatio-temporal and the nearest neighbor queries, by orders of magnitude in some cases. (3) We introduce RelaCT, a tradeoff between the faster and larger ContaCT and the smaller and slower GraCT, offering a new relevant space-time tradeoff for large repetitive datasets of trajectories., For the A Coruña team: This work was supported by GAIN/Xunta de Galicia: GRC: grants ED431C 2021/53, and CIGUS 2023-2026; Ministerio de Ciencia e Innovación and EU/ERDF A way of making Europe under grant [PID2022-141027NB-C21];Ministerio de Ciencia e Innovación under grant [PID2020-114635RB-I00]; Ministerio de Ciencia e Innovación and Next-GenerationEU/PRTR under grants [TED2021-129245B-C21; PDC2021-120917-C21]; Gonzalo Navarro was funded by ANID – Millennium Science Initiative Program – Code ICN17_002 and by Fondecyt under grants [1-200038; 1-230755]. Travis Gagie was funded by Fondecyt under grant [1171058] and by NSERC Discovery under grant [RGPIN-07185-2020]., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; CIGUS 2023-2026, Chile. National Agency of Research and Development (ANID); ICN17_002, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-200038, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-230755, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1171058, Canada. Natural Science and Engineering Research Council (NSERC); RGPIN-07185-2020