Skip to main content

Resultados relacionados

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

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

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

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

GraCT: A Grammar-based Compressed Index for Trajectory Data

  • Brisaboa, Nieves R.
  • Gómez-Brandón, Adrián
  • Navarro, Gonzalo
  • Paramá, José R.
©2019 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/bync-nd/4.0/. This version of the article has been accepted for publication in Information Sciences. The Version of Record is available online at https://doi.org/10.1016/j.ins.2019.01.035, Versión final aceptada de: N. R. Brisaboa, A. Gómez-Brandón, G. Navarro, and J. R. Paramá, "GraCT: A Grammar-based Compressed Index for Trajectory Data", Information Sciences, Vol. 483, pp. 106-135, May 2019, doi: 10.1016/j.ins.2019.01.035, [Abstract]: We introduce a compressed data structure for the storage of free trajectories of moving objects that efficiently supports various spatio-temporal queries. Our structure, dubbed GraCT, stores the absolute positions of all the objects at regular time intervals (snapshots) using a k2-tree, which is a space- and time-efficient region quadtree. Positions between snapshots are represented as logs of relative movements and compressed using a grammar-based compressor. The non-terminals of this grammar are enhanced with MBR information to enable fast queries. The GraCT structure of a dataset occupies less than the raw data compressed with a powerful traditional compressor. Further, instead of requiring full decompression to access the data like a traditional compressor, GraCT supports direct access to object trajectories or to their position at specific time instants, as well as spatial range and nearest-neighbor queries on time instants and/or time intervals. Compared to traditional methods for storing and indexing spatio-temporal data, GraCT requires two orders of magnitude less space, and is competitive in query times. In particular, thanks to its compressed representation, the GraCT structure may reside in main memory in situations where any classical uncompressed index must resort to disk, thereby being one or two orders of magnitude faster., This work has been funded by the European Union Horizon 2020 Marie Skłodowska-Curie Action Fund [grant agreement EU H2020 MSCA RISE BIRDS: 690941]; Ministerio de Economía y Competitividad (PGE and FEDER) [grant number TIN2016-78011-C4-1-R], Centro para el desarrollo Tecnológico e Industrial Programaco-founded with FEDER) [grant number CIEN 2014 IDI-20141259; INNTERCONECTA ITC-20161074], Ministerio de Educación y Formación Profesional (FPU) [grant number FPU16/02914]; Xunta de Galicia (co-founded with FEDER) [grant numbers ED431C 2017/58; ED431G/01; the Chilean National Science and Technology Development Fund (Fondecyt Grant 1-170048); and the Millennium Institute for Foundational Research on Data (IMFD), Chile., Xunta de Galicia; ED431C 2017/58, Xunta de Galicia; ED431G/01, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 1-170048