An index for moving objects with constant-time access to their compressed trajectories
![Thumbnail](/dspace/bitstream/handle/2183/34593/Brisaboa_Nieves_2021_An_index_for_moving_objects_with_constant_time_access_to_their_compressed_trajectories.pdf.jpg?sequence=5&isAllowed=y)
Use este enlace para citar
http://hdl.handle.net/2183/34593
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución-NoComercial-SinDerivadas 3.0 España
Coleccións
- GI-LBD - Artigos [51]
Metadatos
Mostrar o rexistro completo do ítemTítulo
An index for moving objects with constant-time access to their compressed trajectoriesData
2021Cita bibliográfica
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
É version de
https://doi.org/10.1080/13658816.2020.1833015
Resumo
[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.
Palabras chave
Moving objects
Trajectories representation
Spatio-temporal query
Trajectories representation
Spatio-temporal query
Descrición
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
Versión do editor
Dereitos
Atribución-NoComercial-SinDerivadas 3.0 España