TS Algorithm: Balancing Geometry and Semantics in Trajectory Simplification

TL;DR

Standard line simplification algorithms like Douglas-Peucker (DP) often "kill" the most interesting parts of a traveler's journey—the winding walks and scenic stops—because they focus purely on geometric shapes. The TS (Trajectory Simplification) algorithm solves this by prioritizing "semantic density." It outperforms DP with a 59% improvement in accuracy and is 4.5x faster, making it a new benchmark for Location-Based Social Networks (LBSN).

The "Highway Paradox" in Trajectory Sharing

In modern social networks, we don't just share coordinates; we share experiences. Traditional algorithms were designed for CAD and cartography, where the goal is to keep the line looking like the original.

However, consider a trip involving a 50km highway drive and a 2km walk around a lake.

• The Problem: A geometric algorithm (DP) sees the large deviations on the highway and allocates most of the point budget there.
• The Semantic Reality: Users don't care about the exact curve of a highway; they care about the zigzag path in the park where the photos were taken.

Losing 20 meters of detail in a walk can mean losing the entire "story" of the trip, while 100 meters of deviation on a highway is barely noticeable.

Methodology: The Four-Step Semantic Filter

The TS algorithm moves away from pure geometry by introducing a weighting system that respects human behavior.

1. Segmentation

The system first partitions the raw GPS log into Walk and non-Walk segments. This is a critical Inductive Bias: human activity differs fundamentally across transportation modes.

2. Point Distribution & Weighting

Instead of a global budget, points are distributed across segments based on the product of Segment Distance and Average Heading Change.

Inside each segment, every point receives a weight ($p.w$) calculated as: $p.w=p.d\ast p.\gamma$ Where $d$ is the neighbor distance (skeleton) and $\gamma$ is the heading change (semantics). This ensures that sharp turns and stops—places where people typically interact with their surroundings—are preserved.

Figure: The interaction between heading change and distance in determining point importance.

Experiments and Results

The authors tested TS against the DP algorithm using a massive dataset of 335 travel routes.

Performance Gains

• Accuracy: TS achieved a 10-times higher "Correct Rate" compared to DP. While DP often "flattened" intricate walking paths, TS maintained the details that matter to LBSN users.
• Efficiency: DP uses a recursive "divide and conquer" approach, which can hit $O(n^2)$ in the worst case. TS maintains a stable $O(n\log m)$ complexity, making it significantly faster for mobile and web rendering.

Above: Trajectory simplified by DP (loses walking detail). Above: Trajectory simplified by TS (preserves semantic clusters).

Critical Insight: Why it Works

The genius of TS lies in its Normalized Perpendicular Distance metric. By acknowledging that a 10-meter error in a park is "heavier" than a 100-meter error on a highway, the algorithm aligns itself with human perception rather than just Euclidean geometry.

Conclusion & Future Work

The TS algorithm is a significant step forward for LBSN platforms like Strava or specialized travel communities. It recognizes that in the world of social data, Meaning > Geometry.

Limitations: The current model relies heavily on the 50% walk-time assumption. Future iterations could benefit from more granular transportation mode detection (cycling, trains) to further refine weighting strategies.

Takeaway for Researchers: When dealing with user-generated movement data, your loss function should reflect the user's intent, not just the sensor's error.