When analyzing spatial movement data—such as GPS tracks from vehicles, animal migration paths, or delivery routes—a fundamental operation is determining how similar two paths are. Historically, this has been computed using geometric sequence-alignment metrics like Dynamic Time Warping (DTW) or the Fréchet distance.
However, these traditional metrics suffer from a severe shared limitation: quadratic time complexity ($O(n^2)$) relative to the length of the sequences. As spatial datasets scale to millions of trajectories, this quadratic bottleneck makes real-time processing, large-scale data joins, and interactive queries computationally impossible.
To break this bottleneck, researchers have developed several distinct strategies. Rather than just optimizing the underlying math, these modern approaches fundamentally redefine how trajectories are represented and compared.
The Geometry of the Quadratic Bottleneck
To understand why traditional trajectory comparison is slow, consider how metrics like DTW and Fréchet distance operate. They treat a trajectory as an ordered sequence of discrete points.
To compute the similarity between two sequences of length $n$, an algorithm must evaluate how every point in the first sequence aligns with every point in the second sequence. For DTW, this requires constructing an $n \times n$ cost matrix to find the optimal time-warped alignment path. For the Fréchet distance (often visualized as a person walking a dog on a leash, trying to find the shortest leash length that allows both to traverse their respective paths), it requires computing a continuous "free-space diagram" across all segment pairs.
As noted by Sheng Wang et al. in A Survey on Trajectory Data Management, Analytics, and Learning, this $O(n^2)$ overhead severely hinders real-time applications. Even when spatial databases use indexing trees to prune the search space, the underlying pairwise comparison remains a critical bottleneck whenever the index fails to filter out a large number of candidate paths (Sayan Ranu et al. in Indexing and matching trajectories under inconsistent sampling rates).
Subquadratic Approximations and Algorithm Engineering
The first line of defense against the quadratic bottleneck is to optimize or approximate the exact geometric calculations.
One approach is to exploit the physical constraints of real-world trajectories. Physical objects rarely move completely randomly; their paths exhibit geometric continuity. Kyle Fox et al. leverage these properties in Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences to design the first subquadratic-time approximation schemes for DTW, breaking the theoretical $O(n^2)$ barrier for well-behaved sequences.
Alternatively, instead of approximating the distance, researchers can optimize the exact execution. André Nusser et al. demonstrate in Walking the dog fast in practice: Algorithm engineering of the Fréchet distance that rigorous algorithm engineering—such as aggressively pruning the unfeasible regions of the free-space diagram before computing them—can accelerate exact Fréchet computations by multiple orders of magnitude, making exact metrics viable for larger datasets than previously possible.
Sketching and Hashing
Another strategy avoids comparing raw point sequences by compressing trajectories into compact, easily searchable "sketches" or bit vectors.
Maria Sinziana Astefanoaei et al. introduce this concept in Multi-resolution sketches and locality sensitive hashing for fast trajectory processing. By deploying random spatial disks across a geographic area, they represent a complex trajectory as a simplified bit vector based on which disks the path intersects. These sketches can then be indexed using Locality Sensitive Hashing (LSH), transforming an expensive geometric search into a fast bitwise operation.
Building on this, Matteo Ceccarello et al. develop FRESH: Fréchet Similarity with Hashing, which couples LSH with a cascade of increasingly fine-grained verification heuristics. Instead of running a full $O(n^2)$ Fréchet calculation on every item in a database, the system uses the hash to quickly filter out obviously dissimilar curves, only running the expensive exact calculations on a tiny fraction of highly likely candidates. To scale this to millions of paths within strict memory constraints, Shunsuke Kanda et al. propose Succinct Trit-array Trie for Scalable Trajectory Similarity Search, which organizes hashed trajectory tokens into highly compressed trie structures, drastically reducing RAM usage while accelerating nearest-neighbor lookups.
Decoupling Complexity via Representation Learning
The most prominent modern paradigm shifts the computational burden entirely by using deep learning to map variable-length trajectories into fixed-dimensional latent spaces.
The core intuition is simple: if a neural network can encode an entire trajectory into a single low-dimensional vector $\mathbf{v} \in \mathbb{R}^d$, the similarity between two trajectories can be calculated using simple vector operations (like Cosine or Euclidean distance). This drops the pairwise comparison cost from a sequence-dependent $O(n^2)$ to a constant vector-dependent $O(d)$.
Traditional (Point-by-Point Alignment):
Trajectory A (len n) \__ Pairwise Alignment Matrix __/ Complexity: O(n²)
Trajectory B (len n) / (DTW / Fréchet Free-Space) \ Every query is expensive
Learned Embeddings (Decoupled):
Trajectory A (len n) ---> [ Neural Encoder ] ---> Vector A (dim d) \__ Vector Dot Product __/ Complexity: O(d)
Trajectory B (len n) ---> [ Neural Encoder ] ---> Vector B (dim d) / (O(1) w.r.t length) \ Highly scalable
The authors of these learned frameworks focus on capturing different facets of movement within the embedding:
- Spatio-Temporal Constraints: Ziquan Fang et al. develop Spatio-Temporal Trajectory Similarity Learning in Road Networks (ST2Vec), which integrates road network topology and periodic time embeddings to preserve both where and when an object moved, yielding a 200–400x speedup over heuristic calculations.
- Self-Supervised Contrastive Learning: To avoid the need for massive labeled datasets, frameworks like TrajCL (Jianzhong Qi et al. in Contrastive Trajectory Similarity Learning with Dual-Feature Attention) and KGTS (Dalin Zhang et al. in KGTS: Contrastive Trajectory Similarity Learning over Prompt Knowledge Graph Embedding) use data augmentation (such as dropping or jittering points) alongside attention mechanisms to teach networks to map structurally similar paths to nearby points in the latent space.
While early representation models relied on heavy recurrent neural networks (RNNs), recent architectures demonstrate that lighter models are often superior. Renhe Jiang demonstrates in SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity that a minimalist, single-layer Transformer can learn free-space similarities accurately by pairing it with tailored similarity functions. Concurrently, Zhihao Chang et al. argue in Revisiting CNNs for Trajectory Similarity Learning that complex sequence models are often overkill; their model, ConvTraj, uses simple Convolutional Neural Networks focusing on local spatial features to train up to 240x faster than Transformer baselines.
The Encoding Tax
Despite the speed of vector comparisons, learned models introduce a critical trade-off known as the "encoding tax." As Yanchuan Chang et al. demonstrate in Trajectory Similarity Measurement: An Efficiency Perspective, passing a raw trajectory through a deep neural network to generate an embedding is computationally expensive.
If your task is a massive offline search or an all-to-all join across millions of trajectories, paying this encoding tax upfront is highly efficient because the $O(n^2)$ cost is eliminated for all subsequent queries. However, for a one-off, real-time comparison between just two isolated trajectories, classic non-learned algorithms are actually faster because they skip the heavy neural network inference phase entirely.
Bypassing Alignment via Distributional and Functional Views
A final paradigm completely bypasses the sequential nature of trajectories, arguing that treating a path as an ordered sequence of points is what creates the quadratic alignment problem in the first place.
One alternative is the distributional approach, which treats a trajectory as a spatial probability distribution (a density cloud over space) rather than an ordered sequence. Ye Zhu et al. introduce this in Distribution-Based Trajectory Clustering (TIDKC) by utilizing the Isolation Distributional Kernel (IDK). By converting trajectories into probability distributions, similarity is calculated based on distribution overlap rather than sequential point alignment, reducing the computational complexity to linear time ($O(n)$).
Yufan Wang et al. expand on this in A Principled Distributional Approach to Trajectory Similarity Measurement and its Application to Anomaly Detection, showing that this distributional kernel approach requires zero training data, completely sidesteps the sequential alignment phase, and runs orders of magnitude faster than traditional methods while outperforming deep learning models in identifying anomalies.
Another alternative is the functional approach, which treats a trajectory as a continuous mathematical curve. Zengwei Zheng et al. demonstrate this in Trajectory Similarity Computation based on Interpolation and Integration (S). Instead of comparing discrete GPS pings, they use Lagrange interpolation to fit continuous curves to the data, and then compute similarity using a "deformed integration" technique. This mathematical shift achieves a linear time complexity of $O(n+v)$, providing strong robustness against irregular sampling rates and sensor noise without ever triggering a combinatorial matrix explosion.
Key Foundational Work
Visually driven analysis of movement data by progressive clustering (2008) — contributed 1 concept elements to this direction.
Dynamics-aware similarity of moving objects trajectories (2007) — contributed 1 concept elements to this direction.