# Using Lower-Bound Representations for Trajectory Similarity Learning

arXiv: https://arxiv.org/abs/2608.01039 · HTML: https://mlsanity.com/paper/2608.01039/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 2 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [Contrastive Trajectory Similarity Learning with Dual-Feature Attention](https://mlsanity.com/paper/2210.05155/) (2022)
- [Deep Spatially and Temporally Aware Similarity Computation for Road Network Constrained Trajectories](https://mlsanity.com/paper/2112.09339/) (2021)
- [Trajectory Similarity Measurement: An Efficiency Perspective](https://mlsanity.com/paper/2311.00960/) (2023)
- [SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity](https://mlsanity.com/paper/2410.14629/) (2024)
- [Revisiting CNNs for Trajectory Similarity Learning](https://mlsanity.com/paper/2405.19761/) (2024)
- [Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints](https://mlsanity.com/paper/2006.05564/) (2020)
- [TSMini: A Simple Yet Highly Effective Trajectory Similarity Learning Model](https://mlsanity.com/paper/2502.00285/) (2025)
- [REPOSE: Distributed Top-k Trajectory Similarity Search with Local Reference Point Tries](https://mlsanity.com/paper/2101.08929/) (2021)

## Abstract (arXiv)

Trajectory similarity learning is fundamental to efficient trajectory retrieval under complex distance measures. Existing learning-based methods typically rely on embeddings trained to approximate trajectory distances or rankings, but they often lack guarantees with respect to the original distances, exhibit unstable performance across distance measures, and incur substantial training costs. We revisit trajectory similarity learning from a lower-bound representation perspective and propose LB-TrajRep, a unified lower-bound representation framework independent of deep neural embeddings. This framework constructs single-vector representations from a set of lower-bound components, enabling admissible and interpretable lower bounds for multiple classical trajectory distances, including Dynamic Time Warping (DTW), Hausdorff distance, and Discrete Fr'echet Distance (DFD). Within this framework, we instantiate point-pivot components, which naturally support both metric and non-metric distances and remain compatible with standard vector-based retrieval pipelines. To improve ranking quality, we develop two data-driven pivot selection strategies that explicitly optimize lower-bound tightness and prioritize hard near-neighbor trajectory pairs, respectively. Extensive experiments on real-world trajectory datasets show that the proposed lower-bound representations are able to consistently outperform state-of-the-art neural trajectory embeddings across diverse distance measures, improving top-k ranking accuracy by up to 20%--60% on the Hausdorff distance and DFD and by 15%--40% on DTW.