Approaching the Skyline in Z Order

Approaching the Skyline in Z Order

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 matcher Map trajectory Trajectory

re-formatter Temporal sequence Spatial path GPS trajectory Spatial compressor Temporal compressor

Compressed spatial path Compressed temporal sequence Query processor Location-based services 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) STAGE 2 Frequent Sub-Tra. Compression

o Input: non-consecutive edge sequence o Output: non-consecutive edge sequence 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 ei, e2, e3, e4, e5, e6, ej

If the sequence refers to the shortest path from ei to ej , we will replace the sequence with ei, ej e1, e2, e3, e4, e5, e6, e7 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 (contd) Training Trajectory Set { Ts1=e1, e5, e8, e6, e3, Ts2=e1, e5, e2, e1, e4, e8,

Ts3=e2, e1, e4, e6} 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} 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 (contd) 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. Mapmatched trajectory compression. JSS, 86(6):15661579, 2013. Nonmaterial: Hu Cao and Ouri Wolfson. Nonmaterialized motion information in transport networks. In ICDT05, pages 173188, 2005. Compression ratio of commercial compressors

RAR: 3.78 ZIP: 2.09 16 Q &A

Recently Viewed Presentations

  • Planning for Automated Vehicle Technologies Impact on Energy

    Planning for Automated Vehicle Technologies Impact on Energy

    Planning for Automated Vehicle TechnologiesImpact on Energy. Tyler C. Folsom, PhD, PE. Project Manager, Qi2, Kent, WA. Professor, University of Washington, Bothell, WA
  • Sample Title Slide Standard Template

    Sample Title Slide Standard Template

    Stop Buying Storage Call Program Marketing Team: Scott Kosciuk, Carol Siebenmorgen, & Patty Christofferson Beaverton, June 9 &10, 2009 Call Program Overview Objectives Generate new storage management and data protection business by addressing our customer's topical IT and business pain-points...
  • The IP, TCP, UDP protocols A quick refresher

    The IP, TCP, UDP protocols A quick refresher

    UDP The IP, TCP, UDP protocols A quick refresher IP protocol Defines a uniform mechanism to access resources between internets Enables networking across networks that are not connected at level 2 (data-link). Defines IP addresses and how to route network...
  • Film Appreciation Notes - DHHS Theatre

    Film Appreciation Notes - DHHS Theatre

    Program Objectives . To enhance student interest in and knowledge about the motion picture development and production process. To encourage students to use critical thinking, creative writing and language skills as they learn how cinematographers contribute to the process of...
  • CIL Documents Database - Maritime Boundary Office

    CIL Documents Database - Maritime Boundary Office

    on the basis of international law, as referred to in Article 38 of the ICJ Statute in order to achieve an equitable solution. Adjudication - Arbitration. Article 286 Articles 74 & 83(2) If no agreement can be reached within a...
  • TeamSTEPPS WELCOME WEDNESDAY PLENARY Mod 1 05.2 Page

    TeamSTEPPS WELCOME WEDNESDAY PLENARY Mod 1 05.2 Page

    Culture--Basics. Evolved from Anthropology to mean allhuman phenomena that are not genetically determined.It is the way humans represent their lives in symbols, values and behaviors—language, dress, food, religion, commerce--the totality of our "way of life.". How tradition, values and social...
  • ANTHC DIVISION OF ENVIRONMENTAL HEALTH & ENGINEERING Evolution

    ANTHC DIVISION OF ENVIRONMENTAL HEALTH & ENGINEERING Evolution

    Calibri Arial Franklin Gothic Medium Arial Black ANTHC DEHE PowerPoint Presentation Birth of the Washeteria Birth of the Washeteria Wainwright Floor Plan II Emmonak Floor Plan Beaver Floor Plan AVDP Project Reporting Standardization in 2013 Plumbing Philosophy and Floor Plan...
  • TRial to Assess Improvement in Therapeutic Outcomes by

    TRial to Assess Improvement in Therapeutic Outcomes by

    TRial to Assess Improvement in Therapeutic Outcomes by Optimizing Platelet InhibitioN with Prasugrel TRITON-TIMI 38 AHA 2007 Orlando, Florida Disclosure Statement: The TRITON-TIMI 38 trial was supported by a research grant to the Brigham and Women's Hospital from Daiichi Sankyo...