An Overview of Moving Object Trajectory Compression Algorithms <s> Priority Queue Based Trajectory Compression. <s> GPS-equipped mobile devices such as smart phones and in-car navigation units are collecting enormous amounts spatial and temporal information that traces a moving object's path. The popularity of these devices has led to an exponential increase in the amount of GPS trajectory data generated. The size of this data makes it difficult to transmit it over a mobile network and to analyze it to extract useful patterns. Numerous compression algorithms have been proposed to reduce the size of trajectory data sets; however these methods often lose important information essential to location-based applications such as object's position, time and speed. This paper describes the Spatial QUalIty Simplification Heuristic (SQUISH) method that demonstrates improved performance when compressing up to roughly 10% of the original data size, and preserves speed information at a much higher accuracy under aggressive compression. Performance is evaluated by comparison with three competing trajectory compression algorithms: Uniform Sampling, Douglas-Peucker and Dead Reckoning. <s> BIB001 </s> An Overview of Moving Object Trajectory Compression Algorithms <s> Priority Queue Based Trajectory Compression. <s> GPS-equipped mobile devices such as smart phones and in-car navigation units are collecting enormous amounts of spatial and temporal information that traces a moving object's path. The exponential increase in the amount of such trajectory data has caused three major problems. First, transmission of large amounts of data is expensive and time-consuming. Second, queries on large amounts of trajectory data require computationally expensive operations to extract useful patterns and information. Third, GPS trajectories often contain large amounts of redundant data that waste storage and cause increased disk I/O time. These issues can be addressed by algorithms that reduce the size of trajectory data. A key requirement for these algorithms is to minimize the loss of information essential to location-based applications. This paper presents a new compression method called SQUISH-E (Spatial QUalIty Simplification Heuristic - Extended) that provides improved run-time performance and usability. A comprehensive comparison of SQUISH-E with other algorithms is carried out through an empirical study across three types of real-world datasets and a variety of error metrics. <s> BIB002
Priority queue based trajectory compression selects the best subset of trajectory points and permanently removes redundant and inessential trajectory points from original trajectory by utilizing local optimization strategies, until some halting condition is met. The Spatial QUalIty Simplification Heuristic (SQUISH) method based on the priority queue data structure proposed by Muckell et al. BIB001 prioritizes the most important points in a trajectory stream. It uses local optimization to select the best subset of points and permanently removes redundant or insignificant points from the original GPS trajectory. Three years later, Muckell et al. BIB002 presented a new version of SQUISH, called SQUISH-E (Spatial QUalIty Simplification Heuristic-Extended) which has the flexibility of tuning compression with respect to compression ratio and error. Priority queue based trajectory compression is not only an online trajectory compression algorithm but also a trajectory compression algorithm that requires presetting the memory buffer. Hence, it can be well applied to real-time applications and small memory devices. It is suitable for all kinds of trajectories, but the compression effect and matching effect may be a little worse than the other compression methods.