Skip to main content

Resultados relacionados

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

RUC. Repositorio da Universidade da Coruña
Publication Contribución de congreso (ConferenceOutput)

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

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

A New Method to Index and Store Spatio-Temporal Data

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

Dv2v: A Dynamic Variable-to-Variable Compressor

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

Semantrix: A Compressed Semantic Matrix

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

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

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

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

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

Compact Representations of Event Sequences

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

Design of Mutation Operators for Testing Geographic Information Systems

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

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

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

Efficient Representation of Multidimensional Data over Hierarchical Domains

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

Compact Trip Representation over Networks

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

GraCT: A Grammar Based Compressed Representation of Trajectories

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

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

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