REST: A Reference-based Framework for Spatio-temporal Trajectory Compression

Yan Zhao, Shuo Shang, Yu Wang, Bolong Zheng, Quoc Viet Hung Nguyen, Kai Zheng

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

7 Citationer (Scopus)

Resumé

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.
OriginalsprogEngelsk
TitelKDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Antal sider10
Publikationsdato19 jul. 2018
Sider2797-2806
ISBN (Trykt)9781450355520
ISBN (Elektronisk)978-1-4503-5552-0
DOI
StatusUdgivet - 19 jul. 2018
BegivenhedACM International Conference on Knowledge Discovery & Data Mining - London, Storbritannien
Varighed: 19 aug. 201823 aug. 2018
Konferencens nummer: 24th

Konference

KonferenceACM International Conference on Knowledge Discovery & Data Mining
Nummer24th
LandStorbritannien
ByLondon
Periode19/08/201823/08/2018

Fingerprint

Trajectories
Query processing
Dynamic programming
Global positioning system
Communication

Citer dette

Zhao, Y., Shang, S., Wang, Y., Zheng, B., Nguyen, Q. V. H., & Zheng, K. (2018). REST: A Reference-based Framework for Spatio-temporal Trajectory Compression. I KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (s. 2797-2806 ) https://doi.org/10.1145/3219819.3220030
Zhao, Yan ; Shang, Shuo ; Wang, Yu ; Zheng, Bolong ; Nguyen, Quoc Viet Hung ; Zheng, Kai. / REST: A Reference-based Framework for Spatio-temporal Trajectory Compression. KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2018. s. 2797-2806
@inproceedings{cc3534239ed047dda39c5691dfbcdc50,
title = "REST: A Reference-based Framework for Spatio-temporal Trajectory Compression",
abstract = "The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.",
keywords = "Compression algorithm, Spatio-temporal data, Trajectory",
author = "Yan Zhao and Shuo Shang and Yu Wang and Bolong Zheng and Nguyen, {Quoc Viet Hung} and Kai Zheng",
year = "2018",
month = "7",
day = "19",
doi = "10.1145/3219819.3220030",
language = "English",
isbn = "9781450355520",
pages = "2797--2806",
booktitle = "KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

Zhao, Y, Shang, S, Wang, Y, Zheng, B, Nguyen, QVH & Zheng, K 2018, REST: A Reference-based Framework for Spatio-temporal Trajectory Compression. i KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. s. 2797-2806 , ACM International Conference on Knowledge Discovery & Data Mining, London, Storbritannien, 19/08/2018. https://doi.org/10.1145/3219819.3220030

REST: A Reference-based Framework for Spatio-temporal Trajectory Compression. / Zhao, Yan; Shang, Shuo; Wang, Yu; Zheng, Bolong; Nguyen, Quoc Viet Hung; Zheng, Kai.

KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2018. s. 2797-2806 .

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - REST: A Reference-based Framework for Spatio-temporal Trajectory Compression

AU - Zhao, Yan

AU - Shang, Shuo

AU - Wang, Yu

AU - Zheng, Bolong

AU - Nguyen, Quoc Viet Hung

AU - Zheng, Kai

PY - 2018/7/19

Y1 - 2018/7/19

N2 - The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

AB - The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

KW - Compression algorithm

KW - Spatio-temporal data

KW - Trajectory

UR - http://www.scopus.com/inward/record.url?scp=85051517166&partnerID=8YFLogxK

U2 - 10.1145/3219819.3220030

DO - 10.1145/3219819.3220030

M3 - Article in proceeding

SN - 9781450355520

SP - 2797

EP - 2806

BT - KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

ER -

Zhao Y, Shang S, Wang Y, Zheng B, Nguyen QVH, Zheng K. REST: A Reference-based Framework for Spatio-temporal Trajectory Compression. I KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2018. s. 2797-2806 https://doi.org/10.1145/3219819.3220030