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:
- 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.
- Multi-Codebook Hashing: To ensure high fidelity, the system employs $M$ independent quantizers. Each quantizer compares a trajectory against a specific "codebook" of prototypes.
- 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.
- 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).
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.
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