A Novel Framework for Online Amnesic Trajectory Compression in Resource-Constrained Environments
A Novel Framework for Online Amnesic Trajectory Compression in Resource-Constrained Environments
复制标题
DOI：
10.1109/tkde.2016.2598171
复制
发表时间：
2015-02
影响因子：
8.9
通讯作者：
Jiajun Liu;Kun Zhao;P. Sommer;Shuo Shang;Branislav Kusy;Jae-Gil Lee;R. Jurdak
中科院分区：
文献类型：
--
作者：
Jiajun Liu;Kun Zhao;P. Sommer;Shuo Shang;Branislav Kusy;Jae-Gil Lee;R. Jurdak
最先进的轨迹压缩方法通常涉及高时空复杂度或产生不令人满意的压缩率，导致内存、计算、存储和能源快速耗尽。当在资源受限的环境中运行时，特别是当数据量（即使压缩时）远远超过存储限制时，它们的能力通常受到限制。因此，我们提出了一种用于错误有界轨迹压缩和老化的新型在线框架，称为遗忘有界象限系统（ABQS），其核心是有界象限系统（BQS）算法系列，包括正常版本（BQS）、快速版本（FBQS）和渐进版本（PBQS）。 ABQS 智能地管理给定的存储，并根据其年龄以不同的容错能力压缩轨迹。在实验中，我们对BQS算法族和ABQS框架进行了综合评估。利用来自狐蝠和汽车的经验 GPS 轨迹以及来自模拟的合成数据，我们证明了独立 BQS 算法在显着降低轨迹压缩的时间和空间复杂性方面的有效性，同时大大提高了最先进算法的压缩率（高达 45%）。我们还表明，目标资源受限硬件平台的运行时间最多可延长 41%。然后，我们通过 ABQS 验证，在数据量远大于存储空间的情况下，ABQS 能够实现比基线小 15 到 400 倍的误差。我们还表明该算法对于极端轨迹形状具有鲁棒性。
State-of-the-art trajectory compression methods usually involve high space-time complexity or yield unsatisfactory compression rates, leading to rapid exhaustion of memory, computation, storage, and energy resources. Their ability is commonly limited when operating in a resource-constrained environment especially when the data volume (even when compressed) far exceeds the storage limit. Hence, we propose a novel online framework for error-bounded trajectory compression and ageing called the Amnesic Bounded Quadrant System (ABQS), whose core is the Bounded Quadrant System (BQS) algorithm family that includes a normal version (BQS), Fast version (FBQS), and a Progressive version (PBQS). ABQS intelligently manages a given storage and compresses the trajectories with different error tolerances subject to their ages. In the experiments, we conduct comprehensive evaluations for the BQS algorithm family and the ABQS framework. Using empirical GPS traces from flying foxes and cars, and synthetic data from simulation, we demonstrate the effectiveness of the standalone BQS algorithms in significantly reducing the time and space complexity of trajectory compression, while greatly improving the compression rates of the state-of-the-art algorithms (up to 45 percent). We also show that the operational time of the target resource-constrained hardware platform can be prolonged by up to 41 percent. We then verify that with ABQS, given data volumes that are far greater than storage space, ABQS is able to achieve 15 to 400 times smaller errors than the baselines. We also show that the algorithm is robust to extreme trajectory shapes.