GeoPTH: A Lightweight Approach to Category-Based Trajectory Retrieval via Geometric Prototype Trajectory Hashing

Yang Xu, Zuliang Yang, Kai Ming TingarXiv 2025 · DOI · arXiv

Abstract

Trajectory similarity retrieval is a fundamental task in urban planning, traffic analysis, and mobility modeling. While traditional metrics are accurate but computationally expensive, and deep learning methods require significant training resources, this paper introduces GeoPTH (Geometric Prototype Trajectory Hashing). GeoPTH is a lightweight, non-learning framework that maps trajectories to binary codes using geometric prototypes and the Hausdorff distance. By treating hashing as a vector quantization problem, GeoPTH achieves state-of-the-art retrieval performance with speeds one to two orders of magnitude faster than existing deep learning competitors.

Introduction

Finding similar paths in large-scale trajectory databases is vital for understanding human mobility patterns. Researchers currently face a trade-off between accuracy and efficiency. Traditional metrics like Dynamic Time Warping (DTW) or Hausdorff distance offer high precision but suffer from $O(n^2)$ complexity, making them unsuitable for real-time applications. Conversely, learning-based methods map trajectories into fixed-length embeddings for fast retrieval but require massive training datasets and often lose significant accuracy when converted into compact binary codes (the "binarization tax").

GeoPTH addresses these challenges by providing a "quantization-native" hashing approach that bypasses the need for expensive neural network training while maintaining high geometric fidelity.

Methodology

GeoPTH treats trajectory hashing as a data-driven, non-iterative Vector Quantization (VQ) problem. The framework consists of several key stages:

  1. Prototype Construction: A small set of trajectories is randomly sampled from the database to serve as "prototypes." These are represented as sets of $k$ points that preserve essential geometric shapes.
  2. Multi-Codebook Hashing: To ensure high fidelity, the system employs $M$ independent quantizers. Each quantizer compares a trajectory against a specific "codebook" of prototypes.
  3. Hausdorff Distance Integration: Trajectories are assigned to their nearest prototype using the Hausdorff distance. As a true mathematical metric, Hausdorff provides theoretical guarantees that trajectories mapped to the same index are geometrically close.
  4. Binary Mapping: The indices of the nearest prototypes are converted into binary and concatenated to form a final $L$-bit hash code. Retrieval is then performed using lightning-fast Hamming distance calculations (bitwise XOR).
The GeoPTH framework uses multiple codebooks and Hausdorff distance to encode trajectories into binary hash codes.

Experimental Evaluation

The framework was evaluated on seven diverse real-world datasets, ranging from small-scale behavioral data (Cyclists, Traffic) to large-scale mobility data like Geolife, which contains over 8 million points from 182 users in Beijing.

A key finding from the experiments is that GeoPTH avoids the information loss typically seen in learning-based methods (like TrajGAT) when their dense embeddings are forced into binary formats. Because GeoPTH generates binary codes directly from geometric prototypes, it remains robust to local noise while capturing global shapes effectively.

Results and Discussion

GeoPTH demonstrated superior performance in both accuracy and efficiency:

  • Accuracy: GeoPTH achieved the highest Mean Average Precision (mAP) on 5 out of 7 datasets when compared to state-of-the-art learning-based hashing methods. As shown in the performance comparison below, it also remains highly competitive with, and sometimes exceeds, traditional "gold standard" metrics like the raw Hausdorff distance.
  • Efficiency: The method consistently ranked first in execution time, outperforming learning-based competitors by one to two orders of magnitude on large datasets like Geolife.
  • Scalability: Accuracy scales gracefully with hash code length ($L$), allowing for fine-grained representation as needed.
Performance comparison (mAP) of GeoPTH against traditional trajectory similarity metrics across various datasets.

Conclusion

GeoPTH proves that for many trajectory retrieval tasks, complex neural architectures may be unnecessary. By leveraging direct geometric mapping, the framework achieves high-speed, high-accuracy retrieval without the "training tax" of deep learning. Future work will explore more sophisticated prototype selection strategies and the integration of temporal or semantic metadata to handle even more complex mobility distributions.

Summary updated

Abstract

Trajectory similarity retrieval is an important part of spatiotemporal data mining, however, existing methods have the following limitations: traditional metrics are computationally expensive, while learning-based methods suffer from substantial training costs and potential instability. This paper addresses these problems by proposing Geometric Prototype Trajectory Hashing (GeoPTH), a novel, lightweight, and non-learning framework for efficient category-based trajectory retrieval. GeoPTH constructs data-dependent hash functions by using representative trajectory prototypes, i.e., small point sets preserving geometric characteristics, as anchors. The hashing process is efficient, which involves mapping a new trajectory to its closest prototype via a robust, Hausdorff metric. Extensive experiments show that GeoPTH's retrieval accuracy is highly competitive with both traditional metrics and state-of-the-art learning methods, and it significantly outperforms binary codes generated through simple binarization of the learned embeddings. Critically, GeoPTH consistently outperforms all competitors in terms of efficiency. Our work demonstrates that a lightweight, prototype-centric approach offers a practical and powerful alternative, achieving an exceptional retrieval performance and computational efficiency.
BibTeX
@misc{xu2025geopth,
  author = {Yang Xu and Zuliang Yang and Kai Ming Ting},
  title = {{GeoPTH: A Lightweight Approach to Category-Based Trajectory Retrieval via Geometric Prototype Trajectory Hashing}},
  year = {2025},
  eprint = {2511.16258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.16258},
}
Figure