Novel Trajectory Compression Framework for Road Networks
Explore a cutting-edge trajectory compression framework that efficiently reduces the burden of storing and processing spatial trajectories in road networks. This innovative approach separates spatial and temporal information, proposing lossless spatial compression algorithms, error-bounded temporal compression algorithms, and support for various location-based services. Enhance your understanding of trajectory representation and the hybrid spatial compression stages involved in this groundbreaking solution.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SMU Corporate Home Page PRESS: A Novel Framework of Trajectory Compression in Road Networks Renchu Song, Weiwei Sun, Fudan University Baihua Zheng, Singapore Management University Yu Zheng, Microsoft Research, Beijing
Background Big Data Huge volume of spatial trajectories cause heavy burden to data storage and data process Trajectories contain redundant parts that contribute very limited to spatial and temporal information Solution: Trajectory Compression
PRESS: Paralleled Road-Network-based Trajectory Compression PRESS Map trajectory Map matcher Trajectory re-formatter Temporal sequence Spatial path Temporal compressor Spatial compressor GPS trajectory Location-based services Compressed spatial path Compressed temporal sequence Query processor
PRESS (contd) Key highlights Separate the spatial path from the temporal information when presenting a trajectory Propose a lossless spatial compression algorithm HSC Propose an error-bounded temporal compression algorithm BTC Support multiple popular location-based services without fully decompressing the trajectories 4
Trajectory Representation Traditional representation (x1, y1, t1), (x2, y2, t1) Spatial path The sequence of road segments passed by a trajectory Temporal sequence The sequence of (di, ti) vectors di refers to the distance travelled from the start of the trajectory until time stamp ti
HSC: Spatial Compression Hybrid Spatial Compression (HSC) is lossless, and it consists of two stages STAGE 1 Shortest Path Compression o Input: spatial path (consecutive edge sequence) o Output: non-consecutive edge sequence o Input: non-consecutive edge sequence STAGE 2 Frequent Sub-Tra. Compression o Output binary code 6
HSC Stage 1: Shortest Path Compression Observation: given a source s and a destination d, most of the time we take the shortest path between s and d if all the edges roughly share the similar traffic condition Given an edge sequence If the sequence refers to the shortest path from to , we will replace the sequence with e1, e2, e3, e4, e5, e6, e7 ei, e2, e3, e4, e5, e6, ej ej ei ei, ej e1, e7 7
HSC Stage 2: Frequent Sub-trajectory Compression Observation: certain road segments are much more popular than others Basic idea: We can treat the sequence of edges as a string, and can employ suitable coding techniques to use fewer bits to represent more common sub-strings Main approach Identify the frequent sub-trajectories (FSTs) using a training set Decompose a trajectory into a sequence of FSTs Use Huffman coding to represent the decomposed trajectory 8
HSC Stage 2: Frequent Sub-trajectory Compression (cont d) Training Trajectory Set All the sub-trajectories with length { e1, e5, e8 , e5, e8, e6 , e8, e6, e3 , e6, e3 , e3 , e1, e5, e2 , e5, e2, e1 , e2, e1, e4 , e1, e4, e8 , e4, e8 , e8 , e2, e1, e4 , e1, e4, e6 , e4, e6 , e6 } { Ts1= e1, e5, e8, e6, e3 , Ts2= e1, e5, e2, e1, e4, e8 , Ts3= e2, e1, e4, e6 } Aho-Corasick Automaton: facilitate trajectory decomposition Trie: capture sub-trajectories and their frequency Huffman tree: code each node in Trie 9
HSC Stage 2: Frequent Sub-trajectory Compression (cont d) Aho-Corasick Automaton: facilitate trajectory decomposition Huffman tree: code each node in Trie 10
BTC: Temporal Compression Temporal info: TSND (Time Synchronized Network Distance): Given a trajectory T and its compressed one T , TSND measures the maximum difference between the distance object travels via trajectory T and that via trajectory T at any time slot with TSND(T, T ) = Maxtx(|Dis(T, tx) Dis(T , tx)|). NSTD (Network Synchronized Time Difference) defines the maximum time difference between a trajectory T and its compressed form T while traveling any same distance with NSTD(T, T ) = Maxdx (|Tim(T, dx) Tim(T , dx)|). 11
Experiments The experiments are based on real trajectory data from one major taxi company in Singapore. Each taxi has installed GPS, and it reports its locations regularly. In our studies, we use the trajectories reported within January 2011, in total 465,000 trajectories generated by about 15,000 taxis. The original storage cost of this dataset is 13.2GB. 12
Experiment (contd) Compression ratio of HSC (spatial compression algorithm) 13
Experiment (contd) Compression ratio of BTC (temporal compression algorithm) 14
Experiment (contd) Compression ratio of PRESS framework 15
Experiment (contd) Comparison of PRESS and its competitors (note both competitors are not bounded by TSND and NSTD but TSED only) MMTC: Georgios Kellaris, Nikos Pelekis, and Yannis Theodoridis. Map- matched trajectory compression. JSS, 86(6):1566 1579, 2013. Nonmaterial: Hu Cao and Ouri Wolfson. Nonmaterialized motion information in transport networks. In ICDT 05, pages 173 188, 2005. Compression ratio of commercial compressors RAR: 3.78 ZIP: 2.09 16
