PaperlayerView exact revision on arXiv

Source-linked AI summary

PRESS: A Novel Framework of Trajectory Compression in Road Networks

Renchu Song, Weiwei Sun, Baihua Zheng, Yu Zheng

arXiv:1402.1546v1cs.DB

TL;DR

Trajectory data contains redundant points, motivating high-ratio, high-quality compression under road-network constraints. PRESS introduces a road-network trajectory-compression framework, and experiments report superior compression power, including savings of up to 78.4% of original storage, while not supporting all queries.

  • Problem

    Trajectory data can be huge and contain redundant points, creating a need for high compression ratios with high-quality trajectories under road-network constraints.

  • Method

    PRESS is a trajectory-compression framework under road-network constraints that uses a two-stage Hybrid Spatial Compression process for spatial paths.

  • Results

    Up to 78.4% of the original storage can be saved, and simulation results demonstrate PRESS's superior compression power.

  • Takeaways & Limitations

    PRESS provides strong trajectory-compression performance while allowing processing over compressed trajectories for the studied queries.

  • Takeaways & Limitations

    PRESS cannot support all queries because shifting properties during compression brings drawbacks, including inability to support some queries.

Abstract

from arXiv · show

Location data becomes more and more important. In this paper, we focus on the trajectory data, and propose a new framework, namely PRESS (Paralleled Road-Network-Based Trajectory Compression), to effectively compress trajectory data under road network constraints. Different from existing work, PRESS proposes a novel representation for trajectories to separate the spatial representation of a trajectory from the temporal representation, and proposes a Hybrid Spatial Compression (HSC) algorithm and error Bounded Temporal Compression (BTC) algorithm to compress the spatial and temporal information of trajectories respectively. PRESS also supports common spatial-temporal queries without fully decompressing the data. Through an extensive experimental study on real trajectory dataset, PRESS significantly outperforms existing approaches in terms of saving storage cost of trajectory data with bounded errors.

1 Introduction

PRESS addresses trajectory compression under road-network constraints by separating spatial and temporal information, compressing each with specialized methods, and retaining query support. Experiments report substantial storage savings and faster spatial-temporal queries.

  • PRESS targets high compression and high-quality trajectories under road-network constraints, where compression can reduce trajectory utility.
  • PRESS represents trajectories as separate spatial paths and temporal sequences, enabling their independent compression.The framework processes the two components in parallel.
  • HSC losslessly compresses spatial paths using shortest-path replacement followed by frequent-sub-trajectory coding.Frequent sub-trajectories receive shorter codes when they are more popular.
  • BTC compresses temporal information with error bounds specified by different applications.The approach is described as flexible for application-specific error bounds.
  • PRESS supports whereat, whenat, and range queries without fully recovering compressed trajectories.
  • 78.4% of original storage cost can be saved, while PRESS also reports linear compression and decompression complexity and faster spatial-temporal queries.The paper states that PRESS outperforms state-of-the-art approaches in compression ratio, time consumption, and query acceleration.

2 Trajectory Representation

PRESS separates a road-network trajectory into a spatial path and a temporal sequence, using network distance and timestamps to preserve movement information. This representation addresses limitations of position-time triples, including movement between vertices and stops along edges.

  • PRESS represents a trajectory with a spatial path of consecutive road-network edges and a separate temporal sequence.The representation replaces combined position-time triples with distinct spatial and temporal components.
  • Separating spatial and temporal information lets PRESS compress both components independently without constraining one compression process by the other.
  • Traditional position-time triples do not directly provide network distance for speed queries, requiring road-network exploration between timestamps.
  • The temporal sequence uses tuples (d_i, t_i), where d_i is distance traveled from the trajectory start at timestamp t_i.The distance can instead represent other edge weights, such as travel time or application-specific costs.
  • Vertex-based representations can miss stops between vertices and incorrectly imply uniform motion, whereas PRESS captures such within-edge temporal behavior.The example distinguishes slow movement, a stop, and subsequent slow movement along the trajectory.

3 Spatial Compression

PRESS’s Hybrid Spatial Compression (HSC) preserves a trajectory’s exact spatial path while reducing storage through shortest-path and frequent-sub-trajectory compression.

  • 3 Spatial Compression: HSC performs shortest-path compression first, followed by frequent sub-trajectory compression on the spatial trajectory.The input trajectory is processed in two stages.
  • 3 Spatial Compression: Existing position-reduction approaches lower storage but cannot fully capture the spatial path, whereas HSC is error-free.HSC retains the original spatial path despite using less space.
  • 3.1 Shortest path compression: Shortest-path compression replaces a sub-trajectory with its endpoint edges when it exactly matches the corresponding shortest path.The method exploits the frequent use of shortest paths in real movement.
  • 3.1 Shortest path compression: The greedy shortest-path algorithm is proven optimal for maximizing the compression ratio, with linear scan complexity O(|T|).The algorithm scans trajectory edges sequentially and skips edges contained in matching shortest paths.
  • 3.2 Frequent sub-trajectory compression: Frequent-sub-trajectory compression represents recurring edge sequences as strings, mines them with a Trie and Aho-Corasick automaton, and encodes them using Huffman coding.The method relies on repeated sub-trajectories in the training data.

4 Temporal Compression

PRESS separates trajectory spatial and temporal information, then compresses temporal data with bounded TSND and NSTD errors while preserving spatial information through HSC.

  • Temporal representation: PRESS represents temporal information as distance-time tuples, but this representation can remain storage-consuming and temporal compression introduces information loss.Each tuple (d_i, t_i) records when the object is at a specific location.
  • Error metrics: TSND bounds maximum distance discrepancy at a common time, while NSTD bounds maximum time discrepancy at a common traveled distance.TSND uses Dis(T, t_x), whereas NSTD uses Tim(T, d_x).
  • Error metrics: The TSND and NSTD metrics are meaningful only when HSC preserves the original trajectory's spatial information exactly.HSC retains the same spatial information while using less space.
  • Bounded Temporal Compression: BTC sequentially tests whether intermediate tuples can be skipped while keeping TSND within τ and NSTD within η.A valid skip links nonadjacent tuples directly; an invalid attempt retains the intermediate tuple and continues from the last successful point.
  • Bounded Temporal Compression: PRESS improves BOPW's time complexity from O(|T|^2) to O(|T|) by maintaining and shrinking an angular range of feasible trajectories.The range is intersected with constraints induced by evaluated points, enabling linear-time compression.

5 Applications on Compressed Trajectory

PRESS supports spatial-temporal queries directly over compressed trajectories, while preserving exact spatial paths and bounding temporal errors. Its query-processing design uses auxiliary structures and can accelerate selected operations, but does not support every query without decompression.

  • Error guarantees: PRESS preserves exact spatial information and bounds temporal information loss by TSND and NSTD when decompressing trajectories for applications.
  • Supported queries: PRESS supports whereat, whenat, and range queries over compressed trajectories without fully recovering them.These are presented as three common location-based-service queries supported directly on compressed data.
  • Supported queries: |whenat(T, x, y)−whenat(T′, x, y)| ≤ NSTD(T, T′), so temporal query error remains bounded by PRESS’s temporal error guarantee.
  • Query performance: Query processing may be faster than processing original trajectories, including shorter comparison time for minimum-distance operations using maintained MBRs and shortest paths.
  • Trade-offs: Auxiliary distance and path structures add storage overhead, and some queries, such as edge-level most-travelled-path counting, still require spatial decompression.
  • Applications: The framework also supports nearby-trajectory, minimum-distance, traffic-flow, congestion, and trajectory-similarity analyses through combinations of its basic queries.

6 Experiments Study

PRESS is evaluated on real Singapore taxi trajectories for compression effectiveness, efficiency, and spatial-temporal query support. Its spatial and temporal compression achieve strong storage savings while remaining efficient and supporting queries on compressed data.

  • Spatial compression: HSC combines SP and FST compression for an expected optimal compression ratio of approximately 4.64, using ratios of 1.52 and 3.05.The FST ratio improves with θ initially, reaches 3.05 at θ = 3, and does not improve further when θ > 3.
  • Temporal compression: PRESS reaches a compression ratio of 8.52 at TSND = 1000m and NSTD = 1000s, compared with 2.71 when both error settings are zero.The ratio increases as TSND and/or NSTD increase.
  • Query support: PRESS supports common spatial-temporal queries directly on compressed trajectories and averages 26% of the time required by the original uncompressed dataset.It saves around 34% of MMTC’s time and roughly 28% of Nonmaterial’s time for these queries.

7 Related Work

Prior trajectory-compression methods use line simplification or map-matching, while PRESS targets road-network trajectories with separate spatial and temporal compression. The paper reports linear-time processing, spatial losslessness, temporal error bounding, and better effectiveness and efficiency than MMTC and Nonmaterial.

  • Line simplification: PRESS has complexity O(|T |), compared with the higher complexities reported for dynamic-programming and Bellman-style simplification algorithms.The paper contrasts PRESS with DP-variants and Bellman’s algorithms in related work.
  • Compression setting: Unlike Euclidean-space simplification methods, PRESS works in road-network spaces and is spatially lossless with temporally bounded compression.The road-network setting introduces constraints not present in ordinary Euclidean trajectory compression.
  • Online adaptation: PRESS scans spatial and temporal representations from head to tail without tracing back, enabling adaptation to online compression.Its BTC component uses an angular-range approach with O(|T |) time complexity based on a variant of the opening-window method.
  • Road-network compression: PRESS separates spatial and temporal components, using sequential patterns to reduce storage and achieving higher compression ratios with linear time complexity.This design differs from existing road-network approaches that compress the trajectory representation more directly.
  • Road-network baselines: Experiments report that PRESS outperforms Nonmaterial and MMTC in both compression effectiveness and efficiency.The compressed trajectories can also answer spatial-temporal queries without full decompression.

8 Conclusion

The paper presents PRESS as a trajectory-compression framework that separates spatial paths from temporal sequences and evaluates it on real Singapore taxi data. The experiments demonstrate superior compression power, while future work targets broader trajectory types and formal selection of the FST parameter θ.

  • Conclusion: PRESS represents trajectories with a spatial path and temporal sequence, then applies separate algorithms to compress each component.The framework is evaluated on a real dataset of Singapore taxi trajectories collected over one month.
  • Conclusion: Experiments on Singapore taxi trajectories demonstrate PRESS’s superior compression power.The conclusion summarizes the evaluation as evidence for the framework’s effectiveness.
  • Future work: Future work will formalize selection of the θ value for FST compression and evaluate PRESS on additional trajectory types such as pedestrian trajectories.These plans extend parameter selection and evaluation beyond the current setting.
Loading 1402.1546v1…