GraCT: A Grammar-based Compressed Index for Trajectory Data

Use this link to cite
http://hdl.handle.net/2183/34603
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España
Collections
- Investigación (FIC) [1615]
Metadata
Show full item recordTitle
GraCT: A Grammar-based Compressed Index for Trajectory DataDate
2019Citation
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
Is version of
https://doi.org/10.1016/j.ins.2019.01.035
Abstract
[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.
Keywords
Compact data structures
Moving objects databases
Moving objects databases
Description
©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
Editor version
Rights
Atribución-NoComercial-SinDerivadas 3.0 España