Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Semantrix: A Compressed Semantic Matrix

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

up
1 user has voted: Dominik Koeppl

Comments

Thank's for the illustrated presentation!
The problem looks interesting to work on.
Following your talk and shortly reading the arXiv paper, I have the following two questions:
1. I wonder whether there are publicly available datasets for this problem.
2. The space usage of Semantrix is much higher than storing the plain matrix. To shrink this large gap:
- Do you see any particularity in the obtained matrix OS of your used datasets (which hopefully reflect a real-world situation)? You used run-length encoding and encode the run lengths by the bit vector.
However, I think that using a grammar-based approach could give better compression if the OS sequence is highly repetitive.
For instance, ESP also exploits run-length encoding, and there are index data structures supporting pattern search queries.
- the rows of all matrices S1 to S7 are non-decreasing sequences. How about storing these values like the PLCP array unary with a select support data structure? Is there a problem that the values become much larger than the width of the rows?

Thank's for your review, Dominik!

First, we are currently generating the truck data over real truck trips for a private company, I do not think that dataset would be public any time soon. On the other hand, as far as I am concerned, there are not public datasets for this particular problem available.

Talking about other possible alternatives on used structures, it could be interesting to apply ESP over our runs to solve pattern queries or even SLP-based indexes.
However, as we are focused on time response in acumulative queries, I am nor really sure that using PLCP would improve our matrices for our particular interests.

Stay safe, Dominik!

Tirso, thank's for your answers.
About the PLCP-based compression: I think that you gain compression, but perhaps you will be a little bit slower since you have to evaluate a select operation for each access.

Paper Details

Authors:
Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro
Submitted On:
20 March 2020 - 3:35pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Tirso Varela Rodeiro
Session:
Session 4
Document Year:
2020
Cite

Document Files

DCC20.pdf

(66)

Keywords

Additional Categories

Subscribe

[1] Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro, "Semantrix: A Compressed Semantic Matrix", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5011. Accessed: Aug. 05, 2020.
@article{5011-20,
url = {http://sigport.org/5011},
author = {Nieves R. Brisaboa; Antonio Fariña; Gonzalo Navarro },
publisher = {IEEE SigPort},
title = {Semantrix: A Compressed Semantic Matrix},
year = {2020} }
TY - EJOUR
T1 - Semantrix: A Compressed Semantic Matrix
AU - Nieves R. Brisaboa; Antonio Fariña; Gonzalo Navarro
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5011
ER -
Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro. (2020). Semantrix: A Compressed Semantic Matrix. IEEE SigPort. http://sigport.org/5011
Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro, 2020. Semantrix: A Compressed Semantic Matrix. Available at: http://sigport.org/5011.
Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro. (2020). "Semantrix: A Compressed Semantic Matrix." Web.
1. Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro. Semantrix: A Compressed Semantic Matrix [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5011