Using Lower-Bound Representations for Trajectory Similarity Learning

Using Lower-Bound Representations for Trajectory Similarity Learning Liwei Deng Aalborg University lide@cs.aau.dk

Haotian Meng, Yupu Zhang

Torben Bach Pedersen

Kai Zheng∗

Christian S. Jensen

Aalborg University tbp@cs.aau.dk

University of Electronic Science and Technology of ChinaB zhengkai@uestc.edu.cn

Aalborg University csj@cs.aau.dk

ABSTRACT

arXiv:2608.01039v1 [cs.DB] 2 Aug 2026

Yan Zhao

University of Electronic Science and University of Electronic Science and Technology of China Technology of ChinaB menghaotian,zhangyupu@std.uestc.edu.cn zhaoyan@uestc.edu.cn

Trajectory similarity learning is fundamental to efficient trajectory retrieval under complex distance measures. Existing learningbased 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échet Distance (DFD). Within this framework, we instantiate point-pivot components, which naturally support both metric and non-metric distances and remain compatible with standard vectorbased 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-𝑘 ranking accuracy by up to 20%–60% on the Hausdorff distance and DFD and by 15%–40% on DTW. PVLDB Reference Format: Liwei Deng, Haotian Meng, Yupu Zhang, Yan Zhao, Torben Bach Pedersen, Kai Zheng, and Christian S. Jensen. Using Lower-Bound Representations for Trajectory Similarity Learning. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: ∗ B The corresponding author.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

The source code, data, and other artifacts have been made available at https://github.com/LIWEIDENG0830/LB-TrajRep.

1

INTRODUCTION

Trajectory similarity computation [5, 6, 8, 10, 19, 21, 24, 37, 39, 40, 42, 47, 49] is a fundamental problem in spatio-temporal data analysis, with applications ranging from trajectory retrieval [11, 38] and clustering [2, 22] to traffic analysis and anomaly detection [46]. Given two trajectories, the task is to determine their similarity according to such as Dynamic Time Warping (DTW) [43], Hausdorff distance [2], or Discrete Fréchet Distance (DFD) [1]. While offering high utility, these classical distance measures are computationally expensive, typically having quadratic time complexity in the trajectory length, which is prohibitive for large-scale datasets [41]. To lower computational costs, trajectory similarity learning has emerged [25]. The core idea is to represent trajectories as a vectors such that the similarity between trajectories can be approximated by distance computations on fixed-length vectors [41]. A large body of recent studies propose neural network based methods to learn trajectory embeddings. Representative approaches include RNN-based methods that encode trajectories as point sequences, e.g., NeuTraj [41] and its variants, Transformer-based methods that capture long-range dependencies through self-attention, e.g., TrajGAT [42] and SIMformer [38], and CNN-based methods that emphasize local spatial patterns, e.g., TrjSR [5] and ConvTraj [11]. More recent studies incorporate ranking-aware losses [7, 19], graph structures [23, 42], or multi-granularity encoders [42] to improve approximation accuracy. Despite their architectural diversity, existing learning-based methods share a common goal: approximating complex trajectory distances or their induced similarity rankings using embeddings encoded by neural networks [25]. However, empirical evidence from our study suggests that this general approach faces several fundamental limitations. C1. Learned trajectory embeddings generally provide no guarantees with respect to the original trajectory distances and are difficult to interpret. Most existing learning-based methods encode trajectories into latent embedding spaces where similarity is measured by a simple vector distance. However, such embedding distances typically provide no explicit guarantees with respect to the original trajectory distance, making it difficult to

reason about their semantic consistency. This limitation is particularly relevant for non-metric or alignment-based distances such as DTW [3], whose values are sensitive to local variations and alignment choices [17, 33]. Moreover, neural trajectory embeddings are often opaque, offering little insight into why two trajectories are considered similar or dissimilar, which complicates failure analysis and systematic improvement. C2. Many learning-based approaches exhibit a mismatch between their modeling assumptions and the retrieval setting. Trajectory similarity learning is evaluated predominantly according to top-𝑘 ranking quality. Yet, most learning-based approaches are trained to minimize distance regression errors [38, 41] or pairwise surrogate losses over sampled trajectory pairs [11, 19]. Such objectives emphasize average approximation accuracy rather than explicitly prioritizing ranking-critical near-neighbor trajectories that affect retrieval performance the most. As a result, improvements in training loss do not necessarily translate into better ranking quality in similarity search scenarios. C3. Existing trajectory similarity learning methods are often tightly coupled to specific distance measures and incur substantial training costs. Distances such as Hausdorff [2, 26], DFD [1], and DTW [43] capture similarity from fundamentally different perspectives. Further, existing learning-based methods often rely on distance-specific supervision [38, 47] or architectural designs. Consequently, changing the target distance typically requires redesigning objectives, retuning of hyperparameters, and retraining of models. Combined with the high computational cost of training deep neural networks, this tight coupling to specific distance measures limits representation reuse across distances and reduces the practicality of learning-based solutions in real-world systems. In this paper, we study trajectory similarity learning adopting a new perspective. Instead of learning embeddings using neural networks that approximate trajectory distances directly, we propose to learn representations whose induced distances form tight, admissible lower bounds of classical trajectory distances (C1). This new approach aligns the representation learning objective more closely with the retrieval task, where preserving similarity ordering is more critical than minimizing absolute distance errors, while still respecting the structural properties of the original distance measures. Specifically, we propose a pivot-based lower-bound representation framework, where each trajectory is represented by its distances to a set of pivot points in the spatial domain, computed via simple point-to-trajectory distance primitives (C2). By defining pivots as points rather than trajectories, the framework naturally accommodates both metric and non-metric trajectory distances (C3). With this representation, the similarity between trajectories can be computed directly on their representations, yielding valid lower bounds for Hausdorff distance and DFD, as well as for DTW via one-dimensional projected sequences. Importantly, this design does not modify the original distance definitions and remains fully compatible with standard retrieval pipelines based on vector representations. A central challenge in pivot-based representations lies in selecting effective pivots, as poorly chosen pivots can result in loose lower bounds and degraded ranking performance. To address this issue, we propose two data-driven pivot selection algorithms tailored for

trajectory similarity learning. The first, tightness-aware pivot selection, explicitly optimizes the expected tightness between the induced lower bound and the ground-truth distance. The second, hardness-aware pivot selection, emphasizes preserving similarity ordering among hard (i.e., near-neighbor) trajectory pairs that are most critical for retrieval accuracy. Both algorithms operate efficiently on sampled training pairs and can be integrated seamlessly into the proposed pivot-based framework. Experiments on multiple real-world trajectory datasets and across diverse trajectory distance measures offer evidence that the proposed lower-bound representations, when equipped with effective pivot selection strategies, are able to consistently outperform stateof-the-art neural trajectory embeddings in terms of ranking accuracy and stability. These findings suggest that carefully designed lower-bound representations provide an attractive alternative to neural embeddings for trajectory similarity learning, offering improved quality, interpretability, efficiency, and distance-agnostic applicability. The paper’s contributions can be summarized as follows: • We adopt a lower-bound representation approach to trajectory similarity learning and propose LB-TrajRep, a unified pivot-based framework that induces admissible, interpretable lower bounds for multiple classical trajectory distances, including DTW, Hausdorff distance, and DFD. • We propose two data-driven pivot selection algorithms, namely tightness-aware and hardness-aware selection, which explicitly optimize representation quality for similarity ranking and effectively target ranking-critical trajectory pairs, while avoiding the reliance on costly neural models. • We report on extensive experiments on multiple real-world trajectory datasets and covering diverse distance measures, finding that the proposed lower-bound representations consistently outperform state-of-the-art neural trajectory embeddings by significant margins in terms of ranking accuracy and stability under a unified retrieval protocol. The remainder of this paper is organized as follows. Section 2 introduces preliminaries and defines the problem addressed. Section 3 presents the proposed lower-bound representation framework and the corresponding pivot selection strategies for trajectory similarity retrieval. Section 4 reports on extensive experimental evaluations on real-world trajectory datasets, including comparisons with stateof-the-art neural embedding methods. Section 5 reviews related work, and Section 6 concludes and proposes future research directions.

2

PRELIMINARIES

We introduce concepts that are important in the context of trajectory similarity learning and then define the problem addressed. Table 1 summarizes key notation used throughout the paper. Definition 1 (Trajectory). A trajectory is an ordered sequence of spatial points 𝑇 = ⟨𝑥 1, 𝑥 2, . . . , 𝑥 |𝑇 | ⟩, where each point 𝑥𝑖 ∈ R𝑑 represents a location in a 𝑑-dimensional space. We focus on spatial trajectories with 𝑑 = 2, corresponding to latitude and longitude coordinates. The length of a trajectory 𝑇 is denoted by |𝑇 |. 2

Table 1: Summary of notation. Notation

Description

𝑇 , 𝑆, 𝑄 𝐷 (·, ·) 𝐿𝐵 (·, ·) 𝐶 𝐿𝐵𝐶 (𝑇 , 𝑆 ) 𝜙𝑐 (𝑇 ) Φ𝐶 (𝑇 ) 𝑝 𝑃 𝑘 Ttrain S

Trajectories; 𝑄 denotes a query trajectory Ground-truth trajectory distance Lower bound of 𝐷 (·, ·) Set of lower-bound components Lower bound induced by component set 𝐶 Response of trajectory 𝑇 to component 𝑐 Lower-bound representation of trajectory 𝑇 Spatial pivot point Selected pivot set Pivot budget (|𝑃 | = 𝑘) Training trajectory set Sampled trajectory pairs

that the distance computed on representations reflects the similarity between the original trajectories under 𝐷. Formally, for any trajectories 𝑇𝑖 and 𝑇 𝑗 , the distance 𝑑 (𝑓 (𝑇𝑖 ), 𝑓 (𝑇 𝑗 )) is expected to correlate with the original distance 𝐷 (𝑇𝑖 ,𝑇 𝑗 ), e.g., 𝑑 (𝑓 (𝑇𝑖 ), 𝑓 (𝑇 𝑗 )) ≈ 𝐷 (𝑇𝑖 ,𝑇 𝑗 ), where 𝑑 (·, ·) is a vector similarity measure. Moreover, to support similarity retrieval, the representation should preserve the similarity ranking induced by 𝐷: for all query trajectory 𝑄 and a trajectory dataset D, the ranking induced by distances computed on representations should approximate the ground-truth ranking rank𝐷 (𝑄, D) (see Definition 5). Although many existing methods emphasize approximating the original distance values, in practice, trajectory similarity learning is predominantly evaluated using top-𝑘 ranking quality metrics such as Hit Ratio (HR) and Recall [41, 42]. These metrics focus on whether the nearest neighbors under the original distance are retrieved correctly, rather than on the exact numerical accuracy of distance approximation. As a result, preserving similarity ranking is often emphasized over minimizing absolute distance errors. Existing trajectory similarity learning methods address this objective by learning neural embedding representations whose pairwise distances are trained to approximate the original trajectory distance or its induced ranking [9, 11, 38]. These methods rely on complex neural models and optimization objectives, and they typically do not provide explicit guarantees with respect to the ground-truth distance. In contrast, we adopt a different perspective and consider representations derived from distance bounds. Lower bounds offer a principled mechanism to relate representation distances to the original trajectory distance, making them a natural foundation for constructing similarity-preserving representations with theoretical consistency guarantees.

Given trajectories as the basic data objects, trajectory similarity is typically quantified using distance measures that capture different aspects of spatial and sequential similarity. We consider three classical trajectory distance measures that capture different notions of similarity. Definition 2 (Hausdorff Distance [2, 26]). Given two trajectories 𝑇 and 𝑆, their Hausdorff distance is defined as follows:   𝐷 𝐻 (𝑇 , 𝑆) = max max min ∥𝑥 − 𝑦∥, max min ∥𝑥 − 𝑦∥ , (1) 𝑥 ∈𝑇 𝑦 ∈𝑆

𝑦 ∈𝑆 𝑥 ∈𝑇

where ∥ · ∥ denotes Euclidean distance. Hausdorff distance is a metric and measures the maximum spatial deviation between two trajectories. Definition 3 (Discrete Fréchet Distance [1]). The discrete Fréchet distance (DFD) between two trajectories 𝑇 and 𝑆 measures their similarity while respecting the ordering of the points in each trajectory. It is defined as the minimum distance between pairs of trajectory points required to traverse the trajectories from start to end. DFD can be computed using dynamic programming and satisfies the properties of a metric.

Definition 7 (Lower Bound of a Trajectory Distance). Given a trajectory distance measure 𝐷 (·, ·), a function 𝐿𝐵(·, ·) is called a lower bound of 𝐷 if it satisfies ∀ 𝑇 , 𝑆, 𝐿𝐵(𝑇 , 𝑆) ≤ 𝐷 (𝑇 , 𝑆). The effectiveness of a lower bound for ranking preservation depends on how closely it approximates the true distance.

Definition 4 (Dynamic Time Warping Distance [43]). Given two trajectories 𝑇 = ⟨𝑥 1, . . . , 𝑥𝑛 ⟩ and 𝑆 = ⟨𝑦1, . . . , 𝑦𝑚 ⟩, the Dynamic Time Warping (DTW) distance is defined as follows: ∑︁ 𝐷 DTW (𝑇 , 𝑆) = min ∥𝑥𝑖 − 𝑦 𝑗 ∥, (2)

Definition 8 (Lower-Bound Tightness). The tightness of a lower bound 𝐿𝐵(·, ·) with respect to a distance 𝐷 (·, ·) denotes how well 𝐿𝐵(𝑇 , 𝑆) approximates 𝐷 (𝑇 , 𝑆). Tighter lower bounds generally preserve similarity rankings better.

𝜋

While lower-bound tightness characterizes how closely a lower bound approximates the original distance, it is not an end goal in itself. Rather tightness affects the quality of similarity rankings induced by lower-bound–based representations. Motivated by this observation, we formulate the problem of trajectory similarity learning as constructing representations that leverage lower bounds to preserve the ground-truth similarity ranking.

(𝑖,𝑗 ) ∈𝜋

where 𝜋 denotes a warping path that aligns points from 𝑇 and 𝑆 while preserving their order. DTW can be computed in 𝑂 (𝑛𝑚) time using dynamic programming. Unlike Hausdorff distance and DFD, DTW does not satisfy the triangle inequality and is not a metric. Given a trajectory distance measure, similarity search is typically conducted by ranking trajectories according to their distances to a query trajectory.

Definition 9 (Problem Definition). Given a trajectory dataset D, a query set Q, and a trajectory distance measure 𝐷 (·, ·), the goal is to construct a representation function 𝑓 (·) that enables efficient similarity computation using simple vector distances, while approximately preserving the ground-truth similarity ranking rank𝐷 (𝑄, D) for all 𝑄 ∈ Q. In particular, we focus on representations derived from lower bounds of 𝐷, which makes it possible to provide theoretical guarantees on the consistency with the original distance in a retrieval-oriented setting.

Definition 5 (Trajectory Similarity Ranking). Given a query trajectory 𝑄 and a trajectory dataset D, the ranking induced by a distance measure 𝐷 (·, ·) is the ordering of trajectories in D by increasing distance to 𝑄, denoted as rank𝐷 (𝑄, D). Definition 6 (Trajectory Similarity Learning [11]). Given a trajectory similarity measure 𝐷 (·, ·), trajectory similarity representation learning aims to construct a representation function 𝑓 (·) such 3

METHODOLOGY

3.1

𝑐∈C

SE: Φ#$ ∈ ℝ%

PSE: [Φ#$ , Φ& ]

Trajectory Encoding: SE or PIVOT or PSE or IPSE

IPSE: [Φ& , 𝜓&( , 𝜓&) ]

Similarity Computation: 𝐿𝐵*$ or 𝐿𝐵&+,-. or 𝐿𝐵&#$ or 𝐿𝐵+&#$

Pivot-based Features

PIVOT: Φ& ∈ ℝ

Pivot Selection

'

Trajectory Encoding

Retrieval: Rank according to LB

Figure 1: LB-TrajRep framework overview. respect traversal order, the distances between corresponding endpoints provide valid lower bounds. Specifically, given trajectories 𝑇 = ⟨𝑥 1, . . . , 𝑥 |𝑇 | ⟩ and 𝑆 = ⟨𝑦1, . . . , 𝑦 |𝑆 | ⟩, we define the endpointbased lower bound:
𝐿𝐵 SE (𝑇 , 𝑆) = max ∥𝑥 1 − 𝑦1 ∥, ∥𝑥 |𝑇 | − 𝑦 |𝑆 | ∥ (6) This component is inexpensive to compute and captures coarse spatial alignment between trajectories. It serves as a strong baseline and is commonly used in classical trajectory similarity search [28]. However, this endpoint-based component provides a valid lower bound for alignment-based distances such as DTW and DFD, but not for Hausdorff distance. Pivot-Based Components. Next, we consider lower-bound components derived from a set of pivot points in the spatial domain. Pivot-based lower bounds have been considered for metric indexing and distance pruning [12, 14, 44], where approaches are typically designed for metric distances and rely on trajectory-level pivots [48]. In contrast, we consider pivot-based lower bounds from a trajectory similarity learning perspective and redefine pivots as points rather than trajectories. This seemingly simple design choice fundamentally differs from prior pivot-based approaches and allows the resulting components to remain valid for both metric and non-metric trajectory distances, including DTW (as covered in Section 3.3.1). In addition, defining pivots as points rather than trajectories substantially simplifies representation construction. At query time, encoding a trajectory only requires computing pointto-trajectory distances, avoiding the need for expensive trajectoryto-trajectory distance computations that are commonly required by trajectory-level pivots. Given a pivot point 𝑝 ∈ R2 and a trajectory 𝑇 , we define a pivot response function:

(3)

By construction, 𝐿𝐵 C (𝑇 , 𝑆) is also a valid lower bound of 𝐷 (𝑇 , 𝑆). This approach associates a representation with each trajectory that consists of its responses to the components in C. Specifically, for each component 𝑐, we define a scalar function 𝜙𝑐 (𝑇 ) such that: 𝐿𝐵𝑐 (𝑇 , 𝑆) = |𝜙𝑐 (𝑇 ) − 𝜙𝑐 (𝑆)|

𝑝!

Training Trajectories

Lower-Bound Representation Framework

𝐿𝐵 C (𝑇 , 𝑆) = max 𝐿𝐵𝑐 (𝑇 , 𝑆)

𝑝"

𝜙! (T)

The key idea underlying the proposed representation framework is to represent each trajectory using a set of lower-bound components derived from simple geometric primitives, so that the similarity between trajectories can be estimated efficiently while maintaining theoretical consistency with the original trajectory distance. Let C denote a set of lower-bound components. Each component 𝑐 ∈ C induces a valid lower bound 𝐿𝐵𝑐 (·, ·) of a given trajectory distance 𝐷 (·, ·). Given two trajectories 𝑇 and 𝑆, the overall lower bound induced by C is defined as follows:

(4)

This formulation applies to lower-bound components induced by scalar projections, which cover all instantiations considered in this work. As a result, a trajectory 𝑇 can be represented as a vector:   Φ C (𝑇 ) = 𝜙𝑐 1 (𝑇 ), 𝜙𝑐 2 (𝑇 ), . . . , 𝜙𝑐 |C| (𝑇 ) , (5) where C = {𝑐 1, . . . , 𝑐 | C | }. Similarity between trajectories can then be computed directly on these representations using simple distance functions, such as the ℓ∞ distance, which corresponds to the maximum over component-wise differences. Different instantiations of the framework correspond to different choices of the component set C. Next, we describe concrete lowerbound components and their instantiations, and we study how to select effective components to improve similarity ranking quality.

3.2

Input: Trajectories

Endpoint Features Input: Trajectory 𝑇 =< 𝑝! , ⋯ , 𝑝" >

3

We proceed to present LB-TrajRep, a unified framework for trajectory similarity learning based on lower-bound representations, as shown in Figure 1. Rather than learning embeddings using neural network based methods, our approach constructs representations from lower-bound components, thereby enabling theoretical guarantees with respect to the original trajectory distance. Specifically, a trajectory is represented using a small set of lower-bound components, enabling efficient similarity computation while effectively preserving ground-truth similarity rankings. We first introduce the pivot-based lower-bound representation framework, then describe different component instantiations, and finally present data-driven pivot selection strategies for improving ranking quality.

𝜙 𝑝 (𝑇 ) = min ∥𝑥 − 𝑝 ∥ 𝑥 ∈𝑇

(7)

Intuitively, 𝜙 𝑝 (𝑇 ) measures the minimum distance from trajectory𝑇 to the pivot point 𝑝. For two trajectories 𝑇 and 𝑆, the corresponding pivot-based lower bound is defined as follows:

Lower-Bound Components and Instantiations

𝐿𝐵𝑝 (𝑇 , 𝑆) = |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)|

Under the above lower-bound representation framework, the quality and behavior of a representation are determined by the choice of lower-bound components. We introduce two fundamental types of lower-bound components and show how combinations of these components lead to different instantiations of the framework. Endpoint-Based Components. A simple yet effective source of lower bounds arises from the start and end points of trajectories. For many trajectory distances that enforce point-wise alignment or

(8)

Each pivot thus induces a valid lower-bound component that captures the relative proximity between trajectories with respect to a reference location in space. The effectiveness of pivot-based components depends on the choice of pivots, which motivates the datadriven pivot selection strategies presented in Section 3.3. Framework Instantiations. The lower-bound representation framework introduced in Section 3.1 is generic and is open to different choices of the component set C. Using the endpoint-based 4

Table 2: Framework instantiations. Method

Component Set C

Representation

SE PIVOT PSE IPSE

{𝐿𝐵𝑆𝐸 } {𝐿𝐵𝑝 }𝑝 ∈𝑃 {𝐿𝐵𝑆𝐸 } ∪ {𝐿𝐵𝑝 }𝑝 ∈𝑃 {𝐿𝐵𝑝 }𝑝 ∈𝑃

Endpoints Pivot responses Endpoints & pivot responses Pivot responses & endpoint-to-pivot

result, they share the same theoretical guarantees with respect to the original trajectory distance, subject to the validity of the underlying lower-bound components. Moreover, an important property of defining pivots as points is that the resulting trajectory representation depends only on the selected pivot set, not on the specific trajectory distance. Once pivot points are fixed, the same representation vector can be reused to induce valid lower bounds for different trajectory distances, including Hausdorff distance, DFD, and DTW. Switching the target distance only affects how similarity is interpreted on the representation, without requiring re-encoding of trajectories.

component 𝐿𝐵𝑆𝐸 and the pivot-based components {𝐿𝐵𝑝 |𝑝 ∈ 𝑃 }, we instantiate the framework in four different ways, corresponding to different choices of C and different ways of constructing trajectory representations. Table 2 summarizes the four instantiations. SE: This instantiation uses only the endpoint-based lower-bound component 𝐿𝐵 SE defined in Eq. 6. This corresponds to the component set containing only the start–end component. Each trajectory is represented by a 4-dimensional vector consisting of the coordinates of its start and end points. This instantiation serves as an extremely compact and efficient baseline. PIVOT: This instantiation uses only the pivot-based components induced by a pivot set 𝑃. The induced lower bound is defined as follows: 𝐿𝐵 PIVOT (𝑇 , 𝑆) = max 𝐿𝐵𝑝 (𝑇 , 𝑆) = max |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)|. 𝑝 ∈𝑃

𝑝 ∈𝑃

3.3

The effectiveness of the proposed pivot-based representations depends on the choice of pivots, and different pivot sets can induce substantially different lower bounds, which in turn affect the quality of the resulting similarity rankings. Existing pivot selection strategies are primarily developed for metric indexing and lowerbound–based similarity search, where pivots are selected from the same domain as the indexed objects and are often guided by global geometric criteria such as spatial coverage or dispersion [12, 44]. In our setting, pivots are instantiated as spatial points while data objects are trajectories, leading to a heterogeneous pivot–data relationship. In this setting, global coverage alone does not fully capture how a pivot contributes to representation quality, as the effectiveness of a pivot also depends on how tightly it bounds distances between similar trajectories when used as a representation component. This observation motivates the development of pivot selection strategies that explicitly account for lower-bound behavior in the representation space. Before considering pivot selection, we clarify why the proposed point-based pivots induce valid lower bounds for both metric and non-metric trajectory distances.

(9)

Each trajectory𝑇 is represented by the pivot-response vector 𝜙 𝑃 (𝑇 ) = (𝜙 𝑝 1 (𝑇 ), . . . , 𝜙 𝑝𝑘 (𝑇 )), where 𝑃 = {𝑝 1, . . . , 𝑝𝑘 } and 𝜙 𝑝 (𝑇 ) = min𝑥 ∈𝑇 ∥𝑥 − 𝑝 ∥. Trajectory similarity is computed directly on these representations using the ℓ∞ distance. PSE: This instantiation combines pivot-based components with the endpoint-based component. The induced lower bound is defined as follows: 𝐿𝐵 PSE (𝑇 , 𝑆) = max (𝐿𝐵 SE (𝑇 , 𝑆), 𝐿𝐵 PIVOT (𝑇 , 𝑆))

Pivot Selection for Lower-Bound Representations

(10)

This combination integrates complementary information from endpoints and pivots and can be applied whenever the underlying components constitute valid lower bounds on the target distance. IPSE: Unlike PSE, which combines lower-bound values via a maximum operator, IPSE incorporates endpoint information at the representation level. Specifically, endpoint information is encoded by the distances from the start and end points to the selected pivots, and these features are concatenated with the pivot-response vector. Let 𝑃 = {𝑝 1, . . . , 𝑝𝑘 } be the selected pivot set and let 𝑇 = ⟨𝑥 1, . . . , 𝑥 |𝑇 | ⟩. We reuse the pivot-response vector 𝜙 𝑃 (𝑇 ) defined above and define the endpoint-to-pivot distance vectors as follows:   𝜓𝑃s (𝑇 ) = ∥𝑥 1 − 𝑝 1 ∥, . . . , ∥𝑥 1 − 𝑝𝑘 ∥ (11)   𝜓𝑃e (𝑇 ) = ∥𝑥 |𝑇 | − 𝑝 1 ∥, . . . , ∥𝑥 |𝑇 | − 𝑝𝑘 ∥

3.3.1 Pivot-Based Lower Bounds for Metric and Non-Metric Distances. We first clarify the theoretical basis of pivot-based lower bounds and explain why defining pivots as points, rather than trajectories, makes it possible to support non-metric trajectory distances such as DTW. Pivot-based lower bounds in metric spaces. Pivot-based lower bounds are a classical technique for metric distances [13, 14]. Let 𝐷 (·, ·) be a metric trajectory distance and let 𝑃 be a set of pivots drawn from the same domain as the data objects. For any pivot 𝑃𝑖 and any two trajectories 𝑇 and 𝑆, the reverse triangle inequality implies

The IPSE representation is the concatenation of the above three vectors:   ΦIPSE (𝑇 ) = 𝜙 𝑃 (𝑇 ) ∥ 𝜓𝑃s (𝑇 ) ∥ 𝜓𝑃e (𝑇 ) (12) Trajectory similarity is then computed directly on ΦIPSE (·) using the ℓ∞ distance, i.e., 𝐿𝐵 IPSE (𝑇 , 𝑆) = ∥ΦIPSE (𝑇 ) − ΦIPSE (𝑆)∥ ∞ . For DTW and DFD, this distance also constitutes a valid lower bound, and it is also compatible with the representation-based paradigm commonly adopted in trajectory similarity learning. Discussion. All instantiations described above are derived from the same lower-bound representation framework and differ only in the choice and combination of lower-bound components. As a

|𝐷 (𝑇 , 𝑃𝑖 ) − 𝐷 (𝑆, 𝑃𝑖 )| ≤ 𝐷 (𝑇 , 𝑆),

(13)

which yields a valid lower bound. Most existing pivot-based methods implicitly rely on this property and therefore select pivots that are homogeneous with the data objects, i.e., trajectories themselves. This formulation is applicable to metric distances such as Hausdorff distance and DFD. Limitations for non-metric distances. For non-metric distances such as DTW, the triangle inequality does not hold. As a result, trajectory-level pivoting does not, in general, induce valid lower bounds. This limitation prevents direct application of existing 5

pivot-based techniques to DTW and other non-metric trajectory distances. Point pivots and non-metric lower bounds. To overcome this limitation, we define pivots as spatial points rather than trajectories. Given a pivot point 𝑝 ∈ R2 , the pivot response 𝜙 𝑝 (𝑇 ) = min𝑥 ∈𝑇 ∥𝑥 − 𝑝 ∥ induces a scalar projection of a trajectory. Importantly, this projection does not rely on any metric property of the trajectory distance itself.

Algorithm 1: Tightness-Aware Point-Pivot Selection Input: training trajectories Ttrain ; ground-truth distance access 𝐷 (·, ·) on Ttrain ; pivot budget 𝑘; number of sampled trajectory pairs 𝑀; candidate pool size 𝐵; small constant 𝜖>0 Output: selected pivot point set 𝑃 1 Build a point candidate pool 𝑈 from trajectories in Ttrain ; 2 Sample 𝑀 trajectory pairs S = { (𝑇𝑎 ,𝑇𝑏 ) } from Ttrain ; 3 foreach (𝑇𝑎 ,𝑇𝑏 ) ∈ S do 4 𝑑 (𝑇𝑎 ,𝑇𝑏 ) ← 𝐷 (𝑇𝑎 ,𝑇𝑏 ) + 𝜖; 𝑐 (𝑇𝑎 ,𝑇𝑏 ) ← 0;

Lemma 3.1 (Lipschitz Projection Induced by Point Pivots). For any pivot point 𝑝 ∈ R2 and any two points 𝑥, 𝑦 ∈ R2 , the mapping 𝑔𝑝 (𝑧) = ∥𝑧 − 𝑝 ∥ is 1-Lipschitz, i.e., |𝑔𝑝 (𝑥) − 𝑔𝑝 (𝑦)| ≤ ∥𝑥 − 𝑦∥.

𝑃 ← ∅; 𝑅 ← 𝑈 ; for 𝑖 ← 1 to 𝑘 do 7 Sample a subset 𝐶 ⊆ 𝑅 where |𝐶 | = min{𝐵, |𝑅 | }; 8 𝑝 ★ ← max(𝑐 (𝑇𝑎 ,𝑇𝑏 ), |𝜙 𝑝 (𝑇𝑎 ) − 𝜙 𝑝 (𝑇𝑏 ) | )/𝑑 (𝑇𝑎 ,𝑇𝑏 ) over all (𝑇𝑎 ,𝑇𝑏 ) ∈ S; 9 𝑃 ← 𝑃 ∪ {𝑝 ★ }; 𝑅 ← 𝑅 \ {𝑝 ★ }; 10 foreach (𝑇𝑎 ,𝑇𝑏 ) ∈ S do 11 𝑐 (𝑇𝑎 ,𝑇𝑏 ) ← max(𝑐 (𝑇𝑎 ,𝑇𝑏 ), |𝜙 𝑝 ★ (𝑇𝑎 ) − 𝜙 𝑝 ★ (𝑇𝑏 ) | ); 5 6

Lemma 3.2 (Trajectory-level lower bound induced by point pivots). Let 𝑝 ∈ R2 be a pivot point and define the pivot response of a trajectory 𝑇 as 𝜙 𝑝 (𝑇 ) = min𝑥 ∈𝑇 ∥𝑥 − 𝑝 ∥ = min𝑥 ∈𝑇 𝑔𝑝 (𝑥). Consider any trajectory distance 𝐷 (·, ·) that dominates pointwise distances in the sense that for any two trajectories 𝑇 , 𝑆: ∀𝑥 ∈ 𝑇 : min ∥𝑥 − 𝑦 ∥ ≤ 𝐷 (𝑇 , 𝑆), ∀𝑦 ∈ 𝑆 : min ∥𝑥 − 𝑦 ∥ ≤ 𝐷 (𝑇 , 𝑆) 𝑦 ∈𝑆

𝑥 ∈𝑇

12

(14) Then for any trajectories 𝑇 and 𝑆, the following lower bound holds: |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)| ≤ 𝐷 (𝑇 , 𝑆)

(15)

return 𝑃 ;

Optimization via greedy selection. Eq. 16 states a cardinalityconstrained submodular maximization problem, which is NP-hard in general [32]. We thus proceed to approximate this problem efficiently using a greedy approach. The key idea is to iteratively select pivot points that maximize the improvement in lower-bound tightness. Starting from an empty pivot set, the algorithm repeatedly evaluates candidate pivots according to their marginal gains and adds the most informative pivot to the current pivot set. Algorithm 1 implements this idea using a sampled set of trajectory pairs. It first constructs a candidate pool of pivot points and samples trajectory pairs to estimate the tightness objective (lines 1–2). For each sampled pair, the ground-truth distance is computed once and is then used to initialize the current lower-bound value (lines 3–5). During each iteration, the algorithm samples a subset of candidate pivots and evaluates their marginal gains on the sampled trajectory pairs (lines 7–8). The pivot with the largest gain is selected, and the corresponding lower-bound values are updated (lines 9–11). This process continues until the pivot budget is reached, after which the selected pivot set is returned (line 12). The greedy procedure described in Algorithm 1 admits a formal approximation guarantee, as stated below.

Proof. Please see the artifact repository for the detailed proof. □ The domination condition in Eq. 14 is mild and is satisfied by the classical trajectory distances considered in this study. For Hausdorff distance, it follows directly from its max–min definition, which explicitly takes the maximum over point-to-trajectory nearestneighbor distances. For alignment-based distances such as DTW, although they are non-metric, every point participates in the alignment and contributes a non-negative matching cost, implying that the minimum distance from any point to the other trajectory cannot exceed the total alignment cost. DFD satisfies the condition for similar reasons. Therefore, Eq. 15 holds for Hausdorff distance, DFD, and DTW. 3.3.2 Tightness-Aware Pivot Selection. We now study how to select pivots that optimize the quality of the induced lower-bound representations. Given a candidate pivot set P and a target pivot budget 𝑘, our goal is to select a subset 𝑃 ⊆ P, |𝑃 | = 𝑘, such that the induced lower bounds are as tight as possible for trajectory similarity learning. Tightness-aware objective. For a pivot set 𝑃, recall that the induced lower bound between trajectories 𝑇 and 𝑆 is 𝐿𝐵𝑃 (𝑇 , 𝑆) = max𝑝 ∈𝑃 𝑓𝑝 (𝑇 , 𝑆), where 𝑓𝑝 (𝑇 , 𝑆) = |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)|. Given a set of sampled trajectory pairs S, we define the following tightness-aware objective:   𝐿𝐵𝑃 (𝑇 , 𝑆) (16) max 𝐹 (𝑃) = E (𝑇 ,𝑆 )∼S 𝐷 (𝑇 , 𝑆) 𝑃 ⊆ P, |𝑃 |=𝑘

Theorem 3.3. The tightness-aware objective function 𝐹 (𝑃) is monotone and submodular. Let 𝑃 ★ be the optimal pivot set of size 𝑘, and let 𝑃𝑘 be the set returned by the greedy algorithm. Then, the greedy algorithm returns a pivot set whose objective value is guaranteed to be within a constant factor of the optimum, i.e., 𝐹 (𝑃𝑘 ) ≥ (1−1/𝑒) 𝐹 (𝑃 ★). Proof. Please see the artifact repository for the detailed proof. □

By normalizing the lower bound with the ground-truth distance, this objective measures how well the induced representation preserves relative similarity ordering across trajectory pairs, which directly aligns with ranking-based evaluation metrics. Maximizing 𝐹 (𝑃) encourages the selected pivots to produce tight lower bounds relative to the original distance, which benefits similarity ranking.

Intuitively, tightness-aware pivot selection favors pivots that consistently separate trajectory pairs under the original distance, thereby improving the global discriminative power of the induced representation. 6

Table 3: Trajectory dataset statistics. Dataset

#Total

Geolife 13,386 Chengdu 5,000 Porto 1,601,579 T-Drive 10,000 AIS 10,000

selection is better suited for retrieval-oriented scenarios that call for distinguishing highly similar trajectories.

#Train #Query #Candidates Avg. #Points 3,000 1,000 3,000 2,000 2,000

1,000 1,000 500 7,000 7,000

9,386 3,000 1,598,079 7,000 7,000

437.80 228.44 48.91 69.99 80.45

3.4

3.3.3 Hard-Aware Pivot Selection. While the tightness-aware strategy seeks pivots that improve lower-bound quality over uniformly sampled trajectory pairs, not all trajectory pairs contribute equally to retrieval performance. Trajectory similarity learning is typically evaluated using top-𝑘 ranking metrics such as HR and Recall, where errors among nearby trajectories are often far more influential than errors among distant trajectories. Consequently, optimizing the average lower-bound quality may not always yield the best retrieval performance. Motivated by this observation, we introduce a hard-aware pivot selection strategy that focuses on ranking-critical trajectory pairs. Specifically, instead of estimating the objective using uniformly sampled pairs, we construct a hard-pair distribution consisting of near-neighbor trajectory pairs under the ground-truth distance. Hard pair construction. To bias the tightness objective towards ranking-critical regions, we construct a hard-pair sample set as follows. Let Ttrain denote the training trajectory dataset and let 𝐷 (·, ·) be the ground-truth trajectory distance. For each anchor trajectory 𝑇 ∈ Ttrain , we define its hard neighbor set as follows: 𝐻 (𝑇 ) = Top-𝑚 nearest neighbors of 𝑇 under 𝐷

(17)

The hard-pair sample set is then constructed as follows: Shard = {(𝑇 , 𝑆) | 𝑇 ∈ Ttrain, 𝑆 ∈ 𝐻 (𝑇 )}

Complexity Analysis

We analyze the computational complexity of the proposed framework, separating offline preprocessing from online query processing. The former is performed once per dataset, while the latter is executed per query during retrieval. Offline preprocessing. Let |𝑈 | be the size of the point candidate pool, 𝑀 = |S| be the number of sampled trajectory pairs, 𝑘 be the pivot budget, and 𝐵 be the per-iteration candidate subset size. Let T (S) denote the set of trajectories appearing in S and define Í 𝐿 S = 𝑇 ∈ T ( S) |𝑇 |. For a candidate pivot 𝑝, its pivot responses 𝜙 𝑝 (𝑇 ) = min𝑥 ∈𝑇 ∥𝑥 − 𝑝 ∥ are computed for all 𝑇 ∈ T (S) in 𝑂 (𝐿 S ) time. Given these responses, evaluating the normalized marginal gain of 𝑝 on S takes 𝑂 (|S|) time. In each iteration, evaluating 𝐵 candidate pivots takes 𝑂 (𝐵(𝐿 S + |S|)) time, and the total greedy selection cost is 𝑂 (𝑘𝐵(𝐿 S + |S|)). Once pivots are fixed, encoding each database trajectory takes 𝑂 (𝑘 |𝑇 |) time (plus 𝑂 (𝑘) for endpointto-pivot features in IPSE). Online query processing. For a query trajectory 𝑄, representation construction takes 𝑂 (𝑘 |𝑄 |) time (and 𝑂 (𝑘) additional time for IPSE). Let 𝑑 be the representation dimensionality (e.g., 𝑑 = 𝑘 for PIVOT and 𝑑 = 3𝑘 for IPSE). Computing the representation distance to a database trajectory takes 𝑂 (𝑑) time, independently of the original trajectory lengths. The resulting lower-bound scores are used directly for candidate ranking, and the top-𝑘 trajectories are returned as the results enabling efficient large-scale top-𝑘 retrieval via standard vector search. Discussion. In practice, both 𝑘 and |S| are small (e.g., 𝑘 = 32 and |S| on the order of a few thousand), and all offline preprocessing is performed once per dataset. Unlike neural embedding methods that require iterative model training, the proposed framework relies on a finite greedy selection procedure with predictable computational cost and low query-time overhead. Moreover, from a system perspective, the proposed framework follows the same high-level retrieval pipeline as learning-based trajectory embedding methods, i.e., offline encoding followed by efficient vector distance computation at query time, while avoiding expensive model training. This design allows the framework to achieve strong ranking performance with predictable and low query-time cost.

(18)

In practice, 𝑚 is small (e.g., 10–50), and hard neighbors are computed only for a subset of anchor trajectories to control preprocessing cost and to obtain an efficient estimate of the objective. Hard-aware objective. Using the hard-pair set Shard , we obtain the following hard-aware instantiation of the tightness objective:   𝐿𝐵𝑃 (𝑇 , 𝑆) (19) 𝐹 hard (𝑃) = E (𝑇 ,𝑆 )∼Shard 𝐷 (𝑇 , 𝑆) By concentrating the expectation on near-neighbor trajectory pairs, this instantiation emphasizes lower-bound quality in regions where small distortions are most likely to affect the top-𝑘 ranking. Optimization. The hardness-aware objective differs from Eq. 16 only in the trajectory-pair distribution used to estimate the expectation. Therefore, it has the same monotonicity and submodularity properties, and Algorithm 1 can be reused directly. The only difference is that marginal gains are evaluated on the hard-pair set 𝑆 hard instead of on uniformly sampled trajectory pairs. Discussion. Although both strategies optimize the same lowerbound objective, they target different notions of representation quality. Tightness-aware selection aims to improve the average lower-bound quality over broadly sampled trajectory pairs, resulting in a globally robust representation. In contrast, hardness-aware selection concentrates on near-neighbor trajectory pairs that are most likely to affect retrieval rankings. Therefore, tightness-aware selection is preferable when the goal is to obtain uniformly strong lower bounds across the trajectory space, whereas hardness-aware

4 EXPERIMENTS 4.1 Experimental Setting Datasets. We evaluate the proposed approach on five real-world trajectory datasets that are used in recent trajectory similarity learning studies. Specifically, we use the Geolife, Chengdu, and Porto datasets as employed in ConvTraj [11], as well as the T-Drive and AIS datasets as used in SIMformer [38]. These datasets cover diverse application scenarios, including pedestrian, urban taxi, and maritime vessel movement, and they exhibit varying trajectory lengths, sampling rates, and spatial distributions. All datasets are used following the preprocessing procedures, data splits, and evaluation protocols reported in the corresponding studies. This allows us to conduct direct and consistent comparisons with previously 7

reported methods without introducing dataset- or protocol-specific variations. Table 3 summarizes key dataset statistics. Baselines. We compare the proposed lower-bound representations with state-of-the-art learning-based trajectory similarity methods covered in the ConvTraj [11] and SIMformer [38] studies, including t2vec [31], TrjSR [5], NeuTraj [41], Traj2SimVec [47], TrajGAT [42], TrajCL [8], ConvTraj [11], T3S [40], TMN-NM [39], and SIMformer [38]. For these baselines, we report the results from the ConvTraj and SIMformer studies directly under their reported experimental settings. Since the experiments are conducted on the same preprocessed datasets, data splits, and evaluation protocols as those studies, the reported results remain directly comparable. This is common practice in recent trajectory similarity learning studies [11] and avoids the re-training of complex neural models with potentially different hyperparameter configurations, which may lead to unfair comparisons. In addition to the above learning-based baselines, we compare different pivot selection methods for constructing lower-bound representations. Specifically, we consider several widely used heuristic pivot selection methods [13, 50], including random selection, facility location based selection [30], farthest point sampling (FPS) [22], and 𝑘-medoids clustering [27]. These methods have been used for metric indexing and similarity search to improve pivot coverage or dispersion, but they do not explicitly optimize ranking quality. Our proposed tightness- and hard-aware pivot selection methods serve as learning-based alternatives under the same framework. Evaluation protocol and metrics. Following the standard evaluation protocol adopted in trajectory similarity learning [11], we evaluate retrieval effectiveness using ranking-based metrics, including Hit Ratio at 𝑘 (HR@𝑘) and Recall@50 with top-10 ground-truth neighbors (R10@50) [19]. For each query trajectory, candidate trajectories are ranked according to the representation distance and are compared against the ground-truth ranking induced by the original trajectory distance. Ground-truth similarity rankings are induced by the considered trajectory distance measure (i.e., Hausdorff distance, DFD, or DTW), and they are used only for evaluation and for pivot selection during training. Implementation details. Pivot selection is performed offline using sampled trajectory pairs from the training set. Unless stated otherwise, the pivot budget and the number of sampled trajectory pairs are set to 𝑘 = 32 and |S| = 512, respectively. For hard-aware pivot selection, hard pairs are constructed by selecting the top-𝑚 nearest neighbors under the ground-truth distance for each anchor trajectory, with 𝑚 = 50.

4.2

and effective. Across the datasets, PSE improves HR@50 by roughly 15%–40% compared to the baselines in most settings. On the largescale Porto dataset, our methods continue to deliver strong ranking performance, achieving improvements of 30+% on key metrics such as HR@1 and R10@50. These results demonstrate that lowerbound representations provide a robust and competitive alternative to learning-based trajectory embeddings across diverse distance measures and data volumes. Notably, even the extremely simple SE baseline achieves surprisingly strong performance in several settings, indicating that coarse geometric lower-bound cues already capture a substantial portion of trajectory similarity. Furthermore, we observe that the proposed lower-bound representations achieve competitive performance across all three trajectory distance measures, despite their substantially different matching semantics. An additional observation is that the proposed framework separates representation construction from distance evaluation. Distanceindependent pivot selection strategies such as Random and FPS remain competitive across DTW, DFD, and Hausdorff distance, suggesting that the learned representations capture geometric characteristics useful across multiple trajectory similarity definitions. Distance-aware pivot selection can further improve retrieval quality when a target distance is known in advance. Ablation Study. We further analyze the impact of the different representation instantiations and pivot selection strategies. Comparing SE, PIVOT, PSE, and IPSE in Tables 4–8, we observe clear distance-dependent behaviors. PIVOT consistently achieves the best performance under Hausdorff distance, yielding improvements of approximately 10%–25% over PSE and IPSE. This behavior can be attributed to the max–min structure of Hausdorff distance, which is naturally aligned with pivot-based lower bounds. In contrast, the endpoint-based component does not constitute a valid lower bound for Hausdorff distance. As a result, instantiations that incorporate endpoint information (i.e., SE, PSE, and IPSE) tend to exhibit weaker performance, confirming the importance of respecting distance-specific lower-bound validity. Next, for alignment-based distances such as DFD and DTW, PSE consistently outperforms both SE and PIVOT across all datasets and evaluation metrics, improving HR@10 and HR@50 by around 5%–15% over PIVOT. This behavior is consistent with the construction of PSE. Since both SE and PIVOT constitute valid lower bounds for DFD and DTW, the max-combination used in PSE produces a lower bound that is never weaker than either individual component. Consequently, PSE is able to preserve trajectory similarity relationships more effectively than is either SE or PIVOT alone. IPSE achieves comparable but slightly less stable performance in some settings. We also evaluate different pivot selection strategies. Learned pivot selection consistently outperforms the random and heuristic baselines, with the tightnessand hardness-aware strategies providing additional gains of 5%– 20% on the top-𝑘 metrics in most cases. Notably, hardness-aware selection is particularly effective for HR@1 and HR@10, confirming the importance of focusing on hard, near-neighbor trajectory pairs during pivot learning.

Effectiveness

Overall Performance. We evaluate the overall ranking performance of the proposed lower-bound representations against stateof-the-art trajectory embeddings. Results on the five datasets are reported in Tables 4–8. Overall, our methods outperform the baselines across most dataset–distance combinations. In particular, on the Hausdorff and DFD distances, the proposed representations improve HR@1 by approximately 20%–60% over the strongest learning-based baselines, while achieving better gains on HR@10 and HR@50. Under DTW, where several baseline methods suffer from severe performance degradation, our approach remains stable

4.3

Sensitivity Study

We study the sensitivity of our framework to key hyper-parameters on the Geolife dataset, with results shown in Fig. 2. Following the 8

Table 4: Embedding results on Geolife. Best is marked by bold+underline, second best is marked by underline. Within each instantiation, the best and the second best results are highlighted by darker and lighter shading, respectively. Method

Hausdorff DFD DTW HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50

t2vec [31] TrjSR [5] TrajCL [8] NeuTraj [41] Traj2SimVec [47] TrajGAT [42] ConvTraj [11]

22.00 28.30 22.03 34.53 26.46 19.80 46.17

24.48 37.26 37.21 48.40 42.39 30.57 63.69

26.64 42.75 52.49 61.88 48.26 44.03 76.12

44.60 66.56 72.55 80.38 65.12 66.69 95.20

25.70 25.70 25.40 46.37 27.13 17.30 51.80

28.33 33.29 38.98 64.47 42.75 25.87 68.86

32.44 36.94 54.72 76.43 50.27 37.90 79.52

53.45 61.62 75.82 94.44 70.20 61.91 97.34

25.30 27.80 8.47 25.13 16.22 13.80 31.70

28.91 36.52 14.63 33.68 15.39 24.77 46.46

32.81 40.74 19.16 41.72 20.37 35.26 59.26

55.40 67.91 32.05 62.87 35.09 59.36 83.70

SE

38.20

51.25

57.97

69.20

55.10

73.92

86.43

97.91

37.00

46.89

55.30

82.38

Random Facility FPS PIVOT KM Tightness Hardness

55.20 66.50 68.80 67.00 68.00 70.70

69.53 79.54 83.72 81.43 82.32 85.89

77.07 87.33 90.72 88.52 90.11 92.86

95.50 98.47 99.33 98.81 98.89 99.67

38.90 43.60 46.80 46.50 45.80 47.20

49.60 54.47 56.16 55.27 54.70 56.82

54.54 58.99 60.11 59.44 59.17 60.19

89.82 94.12 95.61 94.32 94.39 95.42

31.20 34.70 35.70 34.80 34.50 35.50

39.84 42.19 42.64 42.29 42.23 42.78

44.64 45.93 46.19 46.27 45.76 46.35

76.03 78.59 78.82 78.75 78.25 79.16

PSE

Random Facility FPS KM Tightness Hardness

47.50 48.50 49.50 48.40 48.40 49.70

57.79 57.94 57.98 58.02 58.09 58.23

60.59 60.92 61.12 61.11 61.15 61.26

70.89 70.94 71.06 71.04 71.05 71.11

73.30 74.90 76.50 74.60 75.20 77.90

88.61 89.71 90.68 90.24 90.46 91.30

94.18 95.42 96.23 96.01 95.80 96.69

99.56 99.71 99.96 99.92 99.94 99.97

42.20 42.60 43.20 42.70 42.40 43.20

51.77 52.00 52.22 52.19 51.88 52.49

57.63 57.83 58.10 58.08 57.93 58.16

83.97 84.18 84.42 84.32 84.25 84.52

IPSE

Random Facility FPS KM Tightness Hardness

51.50 57.80 58.30 58.50 58.70 59.70

66.56 71.84 72.22 72.87 73.32 74.13

71.88 79.60 80.64 80.31 81.81 82.53

89.59 91.19 89.87 90.99 91.45 90.61

47.00 54.80 57.40 54.90 55.80 57.70

59.75 65.63 68.62 66.40 65.78 68.43

62.90 68.29 70.69 69.01 68.77 70.39

92.77 96.34 97.63 96.57 96.60 97.37

37.80 40.70 41.10 40.30 39.70 41.20

46.92 48.79 49.62 48.91 48.89 49.24

50.77 52.28 53.13 52.70 52.50 52.96

79.73 81.73 82.25 82.04 81.74 82.25

Table 5: Embedding results on Porto. See the caption of Table 4 for notation. Method

Hausdorff DFD DTW HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50

t2vec TrjSR TrajCL NeuTraj Traj2SimVec TrajGAT ConvTraj

4.00 6.87 7.07 9.30 6.34 6.48 15.33

7.28 14.79 15.37 24.07 16.32 18.29 33.27

10.46 26.71 23.47 34.22 27.34 22.31 45.98

17.08 33.46 35.37 51.43 37.45 43.58 67.20

5.20 8.12 7.07 15.13 7.64 8.39 22.73

7.66 14.26 18.01 33.64 20.03 20.38 40.59

11.09 20.37 28.31 45.47 30.09 24.31 53.35

17.84 37.48 42.97 66.58 44.11 39.78 77.33

6.80 9.66 0.53 8.40 7.26 5.73 10.13

9.60 18.29 2.33 16.33 13.22 12.58 24.46

12.53 21.08 4.56 22.98 15.30 16.97 35.36

20.92 38.23 6.96 34.81 18.30 20.79 52.83

SE

8.80

18.72

28.01

50.02

10.20

21.16

32.56

57.96

11.60

21.12

28.56

51.06

Random Facility FPS PIVOT KMedoids Tightness Hardness

15.80 21.80 23.80 23.00 22.40 23.80

31.46 41.76 44.38 42.92 43.12 45.22

43.56 55.64 58.52 57.08 58.36 60.38

66.98 80.84 82.26 81.52 81.72 83.28

14.00 19.20 22.00 20.80 19.60 20.60

28.24 35.52 37.02 36.78 37.32 37.72

36.95 44.37 46.39 45.29 46.10 46.65

61.28 72.24 73.74 73.44 74.26 74.64

13.20 19.80 19.40 21.00 19.40 18.60

27.82 35.26 35.40 35.00 35.54 35.94

34.76 39.93 41.08 40.48 40.90 41.06

57.68 65.98 66.74 65.80 66.58 67.06

PSE

Random Facility FPS KMedoids Tightness Hardness

21.80 24.00 22.60 23.80 22.60 23.00

41.44 42.26 41.80 42.32 41.22 42.50

51.06 51.33 51.58 51.68 51.24 52.17

71.28 71.16 71.32 71.54 71.02 71.80

27.60 31.80 30.80 32.20 30.00 31.20

51.18 52.92 53.00 53.64 52.90 53.00

66.83 68.88 69.59 69.73 69.48 69.84

86.92 87.10 87.66 87.92 87.32 87.82

22.40 24.40 23.80 23.40 23.20 22.40

39.82 40.60 40.62 40.80 40.28 40.26

47.35 48.28 48.26 48.16 48.28 48.32

73.58 74.26 73.92 73.92 74.02 74.44

IPSE

Random Facility FPS KMedoids Tightness Hardness

17.80 22.80 24.20 24.80 21.80 24.60

35.22 43.20 44.24 43.82 43.76 44.80

46.22 54.22 56.25 55.40 56.02 58.04

71.20 77.98 77.42 78.36 77.44 79.26

17.80 22.80 25.20 25.40 23.20 24.60

33.48 40.40 42.30 41.40 42.50 42.60

43.22 51.16 53.98 52.51 53.88 54.08

68.94 77.34 78.58 78.26 79.14 79.18

17.00 23.60 22.20 23.40 22.00 21.20

33.08 39.06 39.68 38.60 39.60 39.74

40.70 44.70 46.04 45.43 45.91 46.04

65.02 70.16 71.56 70.18 71.00 71.06

best-performing configuration in Section 4.2, we use PIVOT for Hausdorff distance and PSE for DFD/DTW, and we adopt the hardaware pivot selection strategy throughout. We vary one parameter

at a time while keeping the others fixed (default 𝑘 = 32, 𝑚 = 50, and |S| = 512).

9

Table 6: Embedding results on Chengdu. See the caption of Table 4 for notation. Method HR@5

Hausdorff HR@10 R10@50

HR@5

DFD HR@10

R10@50

HR@5

DTW HR@10

R10@50

t2vec [31] TrjSR [5] TrajCL [8] NeuTraj [41] Traj2SimVec [47] TrajGAT [42] ConvTraj [11]

16.16 10.44 22.14 21.82 18.34 19.98 36.26

16.52 12.09 27.04 23.27 20.17 25.26 42.78

30.69 25.44 61.93 39.09 43.67 57.57 76.67

21.34 11.08 19.00 32.28 25.16 16.24 53.34

22.34 12.77 21.42 34.70 28.33 19.11 58.18

44.06 25.96 51.79 49.51 42.78 49.18 93.14

21.00 16.42 23.48 28.40 18.66 23.96 34.90

22.68 18.32 27.20 29.33 19.37 28.32 40.40

46.03 36.63 59.89 46.90 40.69 65.41 76.23

SE

33.18

36.79

53.04

58.20

64.78

97.46

34.06

36.78

72.40

PIVOT

Random Facility FPS KM Tightness Hardness

59.02 50.00 73.42 50.16 80.78 80.88

63.43 54.70 78.31 55.53 85.63 85.54

95.56 92.92 99.81 93.40 99.95 99.94

33.86 30.18 39.04 30.28 40.46 40.70

36.35 33.54 41.25 33.39 42.89 42.92

83.29 79.06 92.11 79.45 94.39 94.45

31.66 30.88 33.04 29.62 32.44 32.42

32.72 32.30 34.26 31.10 34.14 33.90

68.85 67.91 70.74 66.53 70.17 70.28

PSE

Random Facility FPS KM Tightness Hardness

41.70 40.78 42.38 40.52 42.78 42.84

43.17 42.83 43.82 42.68 44.15 43.99

55.11 55.04 55.55 55.01 55.61 55.56

83.48 80.76 87.66 79.66 88.46 88.82

86.16 84.37 90.07 83.08 90.97 91.24

99.52 99.53 100.00 99.58 100.00 100.00

42.10 41.48 42.74 40.82 42.70 42.76

43.84 43.68 44.80 43.01 44.96 44.87

77.12 76.94 78.25 76.96 78.42 78.37

IPSE

Random Facility FPS KM Tightness Hardness

58.78 49.62 72.92 50.28 80.28 80.38

63.26 54.58 78.17 55.44 85.47 85.40

95.56 92.92 99.81 93.40 99.95 99.94

34.52 30.88 39.46 31.24 40.90 41.08

36.53 33.74 41.38 33.86 42.99 43.01

83.29 79.06 92.11 79.45 94.39 94.45

32.26 31.54 33.50 30.60 32.92 32.86

33.00 32.53 34.37 31.57 34.22 33.98

68.85 67.91 70.74 66.53 70.17 70.28

Table 7: Embedding results on T-Drive. See the caption of Table 4 for notation. Method NeuTraj Traj2SimVec T3S TMN-NM SIMFormer w/ Euc. SIMFormer w/ Cos. SIMFormer w/ Cheby.

Hausdorff DFD DTW HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50 13.34 14.59 19.35 21.92 36.97 34.40 43.66

31.04 32.05 41.10 44.42 57.08 53.46 66.79

48.57 48.88 57.01 60.41 68.31 64.15 78.85

68.57 67.67 82.14 86.23 95.43 92.84 98.04

26.30 24.94 31.74 32.43 34.52 28.47 41.04

44.94 43.00 49.80 50.85 52.50 45.19 61.35

57.10 55.30 61.32 62.14 63.35 55.47 73.22

83.40 80.54 88.84 89.88 91.26 84.68 94.41

10.18 11.88 9.19 9.83 11.05 19.88 14.50

22.71 26.59 22.58 23.34 24.36 36.00 29.16

35.64 41.17 36.91 37.57 38.33 52.56 43.72

49.31 58.01 50.26 52.48 52.89 73.94 58.80

SE

5.87

12.63

20.32

25.83

12.67

26.38

40.26

70.66

8.04

16.41

24.48

42.16

PIVOT

Random Facility FPS KM Tightness Hardness

31.81 49.76 52.56 48.36 52.63 53.44

47.41 68.32 71.68 66.78 72.69 72.78

57.11 78.64 82.70 77.17 83.82 83.68

86.26 96.38 99.32 96.09 99.57 99.44

9.97 13.47 13.73 12.99 13.76 13.61

18.14 22.59 23.01 22.39 22.78 22.96

26.82 32.20 32.93 31.99 32.95 33.01

53.69 66.56 67.85 65.87 67.83 68.15

9.91 11.59 11.57 11.21 11.76 11.54

17.36 19.88 19.76 19.84 19.77 19.75

25.93 28.34 28.08 28.33 28.17 28.19

43.34 47.62 47.39 47.48 47.57 47.52

PSE

Random Facility FPS KM Tightness Hardness

14.40 16.37 16.46 16.13 16.76 16.60

23.04 24.84 25.21 24.73 25.30 25.19

31.72 34.07 34.58 33.93 34.70 34.60

35.57 37.74 38.14 37.63 38.25 38.19

44.63 51.83 51.36 51.34 51.39 52.04

61.56 69.42 69.60 68.89 69.71 70.06

71.90 79.44 80.35 79.01 80.66 80.79

93.97 97.42 98.02 97.38 97.99 98.02

17.47 18.97 18.74 18.73 18.67 18.80

27.33 28.72 28.63 28.60 28.66 28.70

34.19 35.51 35.54 35.46 35.63 35.66

54.84 56.68 56.82 56.62 56.88 56.91

IPSE

Random Facility FPS KM Tightness Hardness

20.29 12.61 11.29 13.43 12.19 11.99

33.92 20.20 19.12 21.26 20.20 20.16

45.32 27.85 26.44 29.24 27.76 27.70

50.68 33.05 31.89 34.26 33.02 32.94

29.54 38.07 34.06 39.40 36.19 36.39

41.93 52.96 48.87 55.18 52.15 52.25

49.63 60.68 56.89 63.34 60.34 60.36

83.38 87.24 83.62 90.69 87.73 87.71

17.69 16.07 14.80 16.53 15.39 15.74

26.80 24.79 23.70 25.62 24.41 24.71

33.61 31.13 29.95 32.11 30.60 31.10

54.17 50.46 48.82 52.09 49.80 50.60

Effect of pivot budget 𝑘. Increasing 𝑘 consistently improves ranking quality for all three distances. The improvement is most pronounced for the Hausdorff distance, where larger pivot sets provide better spatial coverage and thus stronger discrimination. For DFD and DTW, the gains are still monotonic but saturate quickly. The

performance becomes relatively stable once 𝑘 reaches a moderate value (e.g., 𝑘 = 32 or 64), indicating that a small set of informative pivots captures most ranking-relevant information. Effect of hardness parameter 𝑚. Varying 𝑚 (the number of near neighbors used to construct hard pairs) has a noticeably smaller 10

Table 8: Embedding results on AIS. See the caption of Table 4 for notation.

DFD (\%)

Hausdorff (\%)

Method

Hausdorff DFD DTW HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50 HR@1 HR@10 HR@50 R10@50

NeuTraj Traj2SimVec T3S TMN-NM SIMFormer w/ Euc. SIMFormer w/ Cos. SIMFormer w/ Cheby.

15.14 22.25 11.49 24.65 31.66 24.03 35.58

32.29 40.38 30.12 47.99 56.11 45.31 59.68

49.99 57.26 51.54 66.48 72.32 63.13 75.88

66.14 72.40 67.10 84.96 91.72 82.11 92.76

29.01 36.43 32.92 37.58 37.30 27.73 39.52

51.26 59.16 56.64 60.13 59.69 48.70 62.83

65.81 71.50 71.03 72.74 72.51 64.17 76.75

85.57 91.26 89.59 92.72 92.49 85.21 93.26

16.18 18.13 14.87 15.41 15.89 21.73 17.66

33.77 36.04 32.98 33.26 33.08 42.15 35.58

49.26 50.46 50.05 49.51 48.83 60.05 51.26

69.12 71.84 69.01 68.61 68.08 78.16 70.48

SE

15.30

25.40

32.19

42.56

26.71

43.90

56.26

73.25

17.16

33.06

45.08

67.40

PIVOT

Random Facility FPS KM Tightness Hardness

35.83 52.39 57.96 50.76 57.91 59.59

54.48 70.79 76.27 70.43 77.29 78.12

66.95 82.87 86.74 82.33 88.17 88.77

91.15 97.98 98.89 97.83 99.14 99.33

20.30 26.63 28.97 26.37 28.71 29.20

33.70 39.38 41.50 39.26 41.74 41.89

41.75 47.07 48.30 46.98 48.71 48.58

75.98 85.40 86.96 85.28 87.36 87.44

19.01 21.86 22.63 21.43 22.50 22.49

32.75 36.07 36.64 35.99 36.94 36.71

41.66 44.80 45.32 44.81 45.54 45.46

70.69 76.39 77.07 76.39 77.29 77.24

PSE

Random Facility FPS KM Tightness Hardness

34.81 40.10 40.97 39.70 40.21 40.73

45.76 49.07 49.45 48.86 49.30 49.21

49.75 52.43 52.76 52.35 52.63 52.73

59.94 61.13 61.30 61.10 61.25 61.24

53.10 61.11 62.09 60.37 61.71 61.59

73.32 80.16 80.74 79.51 80.64 80.65

83.79 89.76 90.30 89.37 90.10 90.38

96.79 98.45 98.50 98.40 98.50 98.51

33.83 35.61 36.04 35.54 35.91 35.56

52.09 53.92 53.96 53.68 53.86 53.75

62.20 63.24 63.30 63.20 63.28 63.28

87.41 88.52 88.51 88.45 88.55 88.50

IPSE

Random Facility FPS KM Tightness Hardness

32.61 37.33 36.70 37.33 36.77 37.07

45.91 47.56 46.27 47.59 46.86 46.74

52.57 50.95 49.82 51.17 50.30 50.26

63.56 60.35 59.75 60.56 60.19 59.93

42.40 53.99 53.19 54.06 53.63 53.03

60.99 73.04 72.23 72.73 72.89 72.87

68.27 81.45 81.71 81.20 82.00 82.13

93.49 97.26 97.44 97.34 97.58 97.58

32.46 33.97 33.76 34.01 33.90 33.70

49.29 52.46 51.73 52.34 51.81 51.58

58.66 61.56 61.24 61.58 61.29 61.14

84.74 87.37 86.94 87.42 87.01 86.92

HR@1

100

HR@10

HR@50

R10@50

Fig. 2 supports the use of compact default settings (e.g., 𝑘 = 32, 𝑚 = 50, and |S| = 512), which achieve near-saturated ranking performance.

80 60 40 100

4.4

We evaluate the efficiency of the two strongest learning-based trajectory similarity methods, ConvTraj and SIMformer. Fig. 3 reports the training cost, offline encoding time, and online distance computation time under a unified and fair setting. All experiments are conducted on an Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz with 128 GB RAM and a GeForce RTX 3080 GPU. For training, all learning-based methods are implemented and trained on a GPU, and both ConvTraj and SIMformer encode trajectories into 128-dimensional vectors following their original configurations. We report the total training time required to reach convergence (i.e., 200 and 500 training epochs for ConvTraj and SIMformer, respectively). For offline encoding, we measure the time to encode all candidate trajectories in the Porto dataset, which is also performed on a GPU to ensure consistency with the training setup. For online similarity computation, we evaluate the per-pair distance computation time by disabling parallel acceleration and randomly sampling 10,000 trajectory pairs, reporting the average cost per pair. Since SIMformer supports multiple vector distance functions, we report results for all distance metrics proposed in the original study. All online distance computations are conducted on a CPU, reflecting a realistic deployment scenario. Overall, the results show that while the neural-based methods achieve strong effectiveness, they incur substantial computational overhead during training and encoding, and their online efficiency depends heavily on the choice of representation distance, whereas

80 60

DTW (\%)

40 100 80 60 40 16

32

k

64

128 20

30

m

50

Efficiency

100 128 256 512 1024

| |

Figure 2: Hyper-parameter study on Geolife. impact than 𝑘. We observe mild, consistent improvements when increasing 𝑚, especially on Hausdorff and DFD, while DTW remains largely stable. This suggests that hard-aware pivot learning is not overly sensitive to the exact choice of 𝑚 as long as it focuses on sufficiently challenging near-neighbor pairs. Effect of training sample size |S|. Increasing |S| yields small but consistent improvements at early stages and then quickly plateaus across all distances. This indicates that the pivot learning objective can be estimated reliably using a moderate number of training pairs, with larger sample sizes achieving diminishing returns. Overall, 11

10

2

10

0

r s s y S aj Tr me om ilit FP KM htnes dnes r nv mfor Rand Fac a g o i H i C S T

(a) Training

Time per pair (ms)

4

Encoding time (s)

Total training time (s)

10

10

5

0

r aj Tr me nv mfor o i C S

SE OT PSE PSE I V PI

(b) Encoding

10

−2

10

−3

L2 os eb SE OT PSE PSE I V er- er-C r-Ch PI m r m me r fo M IMfo for I S S (c) Distance M SI

Figure 3: System-level efficiency: (a) training cost, (b) offline encoding time, and (c) online distance computation time per pair. the proposed lower-bound representations enable lightweight encoding and fast CPU-based similarity computation. In particular, compared with ConvTraj and SIMformer, the proposed approach eliminates expensive iterative neural training and reduces offline training time by over 2,000×. In addition, it reduces the offline trajectory encoding time by 3×–35× and accelerates per-pair online distance computation by 3×–24×, depending on the representation instantiation. These efficiency improvements lead to lower query latency and higher system throughput, thus representing a real practical advantage of the proposed methods in large-scale settings.

5

search in metric spaces. By precomputing distances between data objects and a small set of pivots, these methods exploit the triangle inequality to derive lower and upper bounds for pruning expensive distance computations. The effectiveness of such techniques depends heavily on the quality of the selected pivots. Different pivot selection methods have been proposed to improve the effectiveness of pivot-based lower bounds in metric spaces. Early approaches focus on selecting well-dispersed pivots, such as random selection and farthest-first traversal (FFT) [22], motivated by better space coverage. Other methods exploit pivot–object distance distributions and select pivots that induce informative distance profiles, including variance- and correlation-based strategies [34, 35]. A complementary line of work considers object–object distance relationships and selects pivots that directly strengthen lower bounds over sampled object pairs, thereby improving pruning effectiveness [4]. These methods are studied primarily in the context of metric indexing. We refer to a survey for additional details [50]. In contrast, our study revisits pivot selection from a representation learning perspective, optimizing pivots to construct compact lowerbound based representations that directly support ranking-oriented trajectory similarity search.

RELATED WORK

Trajectory Similarity Learning. The high computational cost of classical trajectory distance measures such as DTW, Hausdorff distance, and DFD motivate trajectory similarity learning (TSL). Computing the classical distances typically involves expensive alignment or pointwise matching procedures [15, 16, 18, 20, 29, 36, 45], making them costly for large-scale analysis and learning. Therefore, recent studies explore learning-based approaches that approximate trajectory similarity by mapping trajectories to fixed-length vector representations. Early sequence encoder based methods such as t2vec [31] and NeuTraj [41] employ recurrent architectures to model trajectories as point sequences and learn embeddings that preserve similarity under different distances. ConvTraj [11] revisits convolutional neural networks for trajectory similarity learning, finding that carefully designed CNN encoders, together with appropriate training objectives can achieve strong performance without relying on complex architectures. More recently, SIMformer [38] shows that a lightweight, single-layer Transformer encoder is sufficient for modeling free-space trajectory similarity, and also highlights the importance of tailoring representation similarity functions beyond Euclidean distance to mitigate the curse of dimensionality and improve ranking quality. Despite differences in model design, these approaches all adhere to an encoder-based paradigm, where trajectories are represented as vectors and compared using simple similarity measures. While effective, most learning-based methods rely on complex training pipelines and distance-specific supervision, which limit their robustness and reuse across different distance measures. In contrast, the framework proposed here focuses on representation-level learning based on analytical lower bounds, providing a lightweight and distance-agnostic alternative for trajectory similarity modeling. Pivot-Based Methods and Pivot Selection. Pivot-based techniques have been studied extensively for accelerating similarity

6

CONCLUSION AND FUTURE WORK

We propose a pivot-based lower-bound representation framework for trajectory similarity learning. By using point-based pivots and encoding a trajectory as a single fixed-length vector, our method provides fast similarity computation and supports multiple trajectory distances, including Hausdorff distance, DFD, and DTW, in a unified framework. We further propose tightness- and hardnessaware pivot selection strategies to improve ranking quality by learning informative pivots offline. Experiments on multiple real-world datasets show that our lower-bound representations are capable of strong and robust ranking performance, often outperforming stateof-the-art neural embeddings while remaining simple and efficient. As future work, one direction is to extend the proposed framework to more expressive trajectory similarity settings beyond free-space spatial distances, by incorporating additional constraints and semantics such as temporal information or road-networks. Another direction is to explore hybrid models that combine lower-bound representations with neural trajectory embeddings, combining the efficiency and robustness of analytical lower bounds with the representation capacity of learning-based methods, potentially achieving performance beyond either approach alone. 12

REFERENCES

[26] Daniel P. Huttenlocher, Gregory A. Klanderman, and William J. Rucklidge. 2002. Comparing images using the Hausdorff distance. TPAMI 15, 9 (2002), 850–863. [27] Leonard Kaufman and Peter J. Rousseeuw. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley. [28] Eamonn J. Keogh and Chotirat Ann Ratanamahatana. 2002. Exact indexing of dynamic time warping. Knowl. Inf. Syst. 7 (2002), 358–386. [29] Satoshi Koide, Chuan Xiao, and Yoshiharu Ishikawa. 2020. Fast subtrajectory similarity search in road networks under weighted edit distance constraints. PVLDB 13, 12 (2020), 2188–2201. [30] Andreas Krause and Carlos Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. In ICML. [31] Xiucheng Li, Kaiqi Zhao, Gao Cong, Christian S Jensen, and Wei Wei. 2018. Deep representation learning for trajectory similarity computation. In ICDE. 617–628. [32] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions—I. Math. Program. 14, 1 (1978), 265–294. [33] Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. 2020. A survey of trajectory distance measures and performance evaluation. VLDBJ 29, 1 (2020), 3–32. [34] Reinier H. Van Leuken and Remco C. Veltkamp. 2011. Selecting vantage objects for similarity indexing. TOMM 7, 3 (2011), 1–18. [35] Jayendra Venkateswaran, Tamer Kahveci, Christopher Jermaine, and Deepak Lachwani. 2008. Reference-based indexing for metric spaces with costly distance measures. VLDBJ 17, 5 (2008), 1231–1251. [36] Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Zizhe Xie, Qizhi Liu, and Xiaolin Qin. 2018. Torch: A search engine for trajectory data. In SIGIR. 535–544. [37] Zheng Wang, Cheng Long, Gao Cong, and Ce Ju. 2019. Effective and efficient sports play retrieval with deep representation learning. In KDD. 499–509. [38] Chuang Yang, Renhe Jiang, Xiaohang Xu, Chuan Xiao, and Kaoru Sezaki. 2024. SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity. In PVLDB, Vol. 18. 390–398. [39] Peilun Yang, Hanchen Wang, Defu Lian, Ying Zhang, Lu Qin, and Wenjie Zhang. 2022. TMN: trajectory matching networks for predicting similarity. In ICDE. 1700–1713. [40] Peilun Yang, Hanchen Wang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2021. T3S: Effective representation learning for trajectory similarity computation. In ICDE. 2183–2188. [41] Di Yao, Gao Cong, Chao Zhang, and Jingping Bi. 2019. Computing trajectory similarity in linear time: A generic seed-guided neural metric learning approach. In ICDE. 1358–1369. [42] Di Yao, Haonan Hu, Lun Du, Gao Cong, Shi Han, and Jingping Bi. 2022. TrajGAT: A graph-based long-term dependency modeling approach for trajectory similarity computation. In KDD. 2275–2285. [43] Byoung-Kee Yi, Hosagrahar V. Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In ICDE. 201–208. [44] Peter N. Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA. 311–321. [45] Haitao Yuan and Guoliang Li. 2019. Distributed in-memory trajectory similarity search and join on road network. In ICDE. 1262–1273. [46] Dongxiang Zhang, Zhihao Chang, Sai Wu, Ye Yuan, Kian-Lee Tan, and Gang Chen. 2020. Continuous trajectory similarity search for online outlier detection. TKDE 34, 10 (2020), 4690–4704. [47] Hanyuan Zhang, Xingyu Zhang, Qize Jiang, Baihua Zheng, Zhenbang Sun, Weiwei Sun, and Changhu Wang. 2021. Trajectory similarity learning with auxiliary supervision and optimal matching. In IJCAI. 3209–3215. [48] Bolong Zheng, Lianggui Weng, Xi Zhao, Kai Zeng, Xiaofang Zhou, and Christian S. Jensen. 2021. REPOSE: Distributed Top-k Trajectory Similarity Search with Local Reference Point Tries. In ICDE. 708–719. [49] Silin Zhou, Jing Li, Hao Wang, Shuo Shang, and Peng Han. 2023. GRLSTM: trajectory similarity computation with graph-based residual LSTM. In AAAI, Vol. 37. 4972–4980. [50] Yifan Zhu, Lu Chen, Yunjun Gao, and Christian S. Jensen. 2022. Pivot selection algorithms in metric spaces: a survey and experimental study. VLDBJ 31, 1 (2022), 23–47.

[1] Helmut Alt and Michael Godau. 1995. Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5, 01n02 (1995), 75–91. [2] Stefan Atev, Grant Miller, and Nikolaos P. Papanikolopoulos. 2010. Clustering of vehicle trajectories. TITS 11, 3 (2010), 647–657. [3] Donald J. Berndt and James Clifford. 1994. Using dynamic time warping to find patterns in time series. In KDD. 359–370. [4] B. Bustos, G. Navarro, and E. Chavez. 2001. Pivot selection techniques for proximity searching in metric spaces. In SCCC. 33–40. [5] Hanlin Cao, Haina Tang, Yulei Wu, Fei Wang, and Yongjun Xu. 2021. On accurate computation of trajectory similarity via single image super-resolution. In IJCNN. 1–9. [6] Yuan Cao, Lei Li, Xiangru Chen, Xue Xu, Zuojin Huang, and Yanwei Yu. 2024. Hypergraph hash learning for efficient trajectory similarity computation. In CIKM. 175–186. [7] Yanchuan Chang, Xu Cai, Christian S. Jensen, and Jianzhong Qi. 2025. K Nearest Neighbor-Guided Trajectory Similarity Learning. arXiv (2025). arXiv:2502.00285 [8] Yanchuan Chang, Jianzhong Qi, Yuxuan Liang, and Egemen Tanin. 2023. Contrastive trajectory similarity learning with dual-feature attention. In ICDE. 2933– 2945. [9] Yanchuan Chang, Egemen Tanin, Gao Cong, Christian S. Jensen, and Jianzhong Qi. 2024. Trajectory Similarity Measurement: An Efficiency Perspective. PVLDB 17, 9 (2024), 2293–2306. [10] Zhihao Chang, Ding Wang, Xiu Tang, Kingsum Chow, and Jianwei Yin. 2025. General Neural Embedding for Sequence Distance Approximation. In SIGIR. 1066–1075. [11] Zhihao Chang, Linzhu Yu, Huan Li, Sai Wu, Gang Chen, and Dongxiang Zhang. 2024. Revisiting CNNs for Trajectory Similarity Learning. PVLDB 18, 4 (2024), 1013–1021. [12] Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José L. Marroquín. 2001. Searching in metric spaces. CSUR 33 (2001), 273–321. [13] Lu Chen, Yunjun Gao, Xinhan Li, Christian S. Jensen, and Gang Chen. 2015. Efficient metric indexing for similarity search. In ICDE. 591–602. [14] Lu Chen, Yunjun Gao, Xuan Song, Zheng Li, Xiaoye Miao, and Christian S. Jensen. 2020. Indexing Metric Spaces for Exact Similarity Search. CSUR 55 (2020), 1 – 39. [15] Lei Chen and Raymond Ng. 2004. On the marriage of LP-norms and edit distance. In PVLDB. 792–803. [16] Lei Chen, M Tamer Özsu, and Vincent Oria. 2005. Robust and fast similarity search for moving object trajectories. In SIGMOD. 491–502. [17] Marco Cuturi. 2011. Fast global alignment kernels. In ICML. 929–936. [18] Liwei Deng, Fei Wang, Tianfu Wang, Yan Zhao, Yuyang Xia, and Kai Zheng. 2025. Exact and Efficient Similar Subtrajectory Search: Integrating Constraints and Simplification. In ICDE. 1056–1069. [19] Liwei Deng, Yan Zhao, Jin Chen, Shuncheng Liu, Yuyang Xia, and Kai Zheng. 2024. Learning to hash for trajectory similarity computation and search. In ICDE. IEEE, 4491–4503. [20] Liwei Deng, Yan Zhao, Zidan Fu, Hao Sun, Shuncheng Liu, and Kai Zheng. 2022. Efficient trajectory similarity computation with contrastive learning. In CIKM. 365–374. [21] Ziquan Fang, Yuntao Du, Xinjun Zhu, Danlei Hu, Lu Chen, Yunjun Gao, and Christian S. Jensen. 2022. Spatio-temporal trajectory similarity learning in road networks. In KDD. 347–356. [22] Teofilo F. Gonzalez. 1985. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38 (1985), 293–306. [23] Peng Han, Jin Wang, Di Yao, Shuo Shang, and Xiangliang Zhang. 2021. A graphbased approach for trajectory similarity computation in spatial networks. In KDD. 556–564. [24] Danlei Hu, Lu Chen, Hanxi Fang, Ziquan Fang, Tianyi Li, and Yunjun Gao. 2023. Spatio-temporal trajectory similarity measures: A comprehensive survey and quantitative study. TKDE 36, 5 (2023), 2191–2212. [25] Danlei Hu, Yilin Li, Lu Chen, Ziquan Fang, Yushuai Li, Yunjun Gao, and Tianyi Li. 2025. SimRN: Trajectory Similarity Learning in Road Networks based on Distributed Deep Reinforcement Learning. In PVLDB. 2057–2069.

13

5DQGRPk 5DQGRP| |

+DUGQHVV 











   10 2



   





   















   10 2

+DUGk

')'







   





   















   10 2

+DUG| |

7LJKWQHVV 

'7:

 10 2



   





   





















  





  

Similarly, we can upper bound 𝜙 𝑝 (𝑆) − 𝜙 𝑝 (𝑇 ) symmetrically. Combining the two inequalities gives |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)| ≤ 𝐷 (𝑇 , 𝑆). □

+DXVGRUII

A.2 























Proof Sketch. We formalize the above intuition by showing that the objective can be decomposed into a sum of monotone submodular functions defined on individual trajectory pairs. Fix a trajectory pair (𝑇 , 𝑆) ∈ S and define the normalized contribution of a pivot 𝑝 as follows: |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)| 𝑎𝑝 (𝑇 , 𝑆) = ≥0 (26) 𝐷 (𝑇 , 𝑆) The per-pair objective can be written as follows: 𝐿𝐵𝑃 (𝑇 , 𝑆) = max 𝑎𝑝 (𝑇 , 𝑆) (27) 𝑔𝑇 ,𝑆 (𝑃) = 𝑝 ∈𝑃 𝐷 (𝑇 , 𝑆) The function 𝑔𝑇 ,𝑆 (𝑃) is monotone, since adding elements to 𝑃 cannot decrease a maximum. It is also submodular because it exhibits diminishing returns, i.e., for any 𝐴 ⊆ 𝐵 and any 𝑝 ∉ 𝐵, 𝑔𝑇 ,𝑆 (𝐴 ∪ {𝑝}) − 𝑔𝑇 ,𝑆 (𝐴) ≥ 𝑔𝑇 ,𝑆 (𝐵 ∪ {𝑝}) − 𝑔𝑇 ,𝑆 (𝐵), (28) as the marginal gain equals max(0, 𝑎𝑝 − max𝑞 ∈𝐴 𝑎𝑞 ), which is no smaller than max(0, 𝑎𝑝 − max𝑞 ∈𝐵 𝑎𝑞 ). Since 𝐹 (𝑃) is an expectation (or empirical average) of 𝑔𝑇 ,𝑆 (𝑃) over sampled pairs, and nonnegative linear combinations preserve monotonicity and submodularity, 𝐹 (𝑃) is also monotone submodular. Applying the classical result of Nemhauser et al. [32] for greedy maximization of a monotone submodular function under a cardinality constraint yields the stated approximation guarantee. □

Figure 4: Average lower-bound tightness of tightness-aware and hardness-aware pivot selection on Geolife under DTW, DFD, and Hausdorff distance.

A ADDITIONAL THEORETICAL ANALYSIS A.1 Proof of Lemma 3.2 Lemma 3.2 (Trajectory-level lower bound induced by point pivots). Let 𝑝 ∈ R2 be a pivot point and define the pivot response of a trajectory 𝑇 as 𝜙 𝑝 (𝑇 ) = min𝑥 ∈𝑇 ∥𝑥 −𝑝 ∥ = min𝑥 ∈𝑇 𝑔𝑝 (𝑥). Consider any trajectory distance 𝐷 (·, ·) that dominates pointwise distances in the sense that for any two trajectories 𝑇 , 𝑆:

B ADDITIONAL EXPERIMENTAL RESULTS B.1 Analysis of Tightness-Aware and Hardness-Aware Pivot Selection

∀𝑥 ∈ 𝑇 : min ∥𝑥 − 𝑦 ∥ ≤ 𝐷 (𝑇 , 𝑆), ∀𝑦 ∈ 𝑆 : min ∥𝑥 − 𝑦 ∥ ≤ 𝐷 (𝑇 , 𝑆) 𝑦 ∈𝑆

𝑥 ∈𝑇

(20) Then for any trajectories 𝑇 and 𝑆, the following lower bound holds: |𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆)| ≤ 𝐷 (𝑇 , 𝑆)

We compare tightness-aware and hardness-aware pivot selection on Geolife and Chengdu datasets under DTW, DFD, and Hausdorff distance. Following Definition 8, pivot-selection quality is measured using the average lower-bound tightness, mean(𝐿𝐵𝑃 (𝑇 , 𝑆)/𝐷 (𝑇 , 𝑆)), where 𝐿𝐵𝑃 (𝑇 , 𝑆) denotes the lower bound induced by the selected pivot set 𝑃 and 𝐷 (𝑇 , 𝑆) denotes the corresponding ground-truth trajectory distance. Results are reported for pivot budgets 𝑘 ∈ {16, 32, 64, 128} and training-pair sets of size |S| ∈ {128, 256, 512, 1024}. When varying 𝑘, we fix |S| = 512; when varying |S|, we fix 𝑘 = 32. To characterize both global and retrieval-critical behavior, we evaluate the selected pivot sets on two fixed evaluation sets, namely randomly sampled trajectory pairs and hard near-neighbor pairs. The latter are constructed by selecting the nearest neighbor (𝑚 = 1) for each anchor trajectory under the corresponding trajectory distance. Figures 4 and 5 reveal a consistent pattern across both datasets. On randomly sampled trajectory pairs, tightness-aware selection

(21)

Proof. Fix 𝑝 ∈ R2 and let 𝑔𝑝 (𝑧) = ∥𝑧 − 𝑝 ∥ as in Lemma 3.1. Let ★ 𝑥 = arg min𝑥 ∈𝑇 𝑔𝑝 (𝑥), and 𝑦★ = arg min𝑦 ∈𝑆 𝑔𝑝 (𝑦), so that 𝜙 𝑝 (𝑇 ) = 𝑔𝑝 (𝑥 ★) and 𝜙 𝑝 (𝑆) = 𝑔𝑝 (𝑦★). We first upper bound 𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆). For any 𝑦 ∈ 𝑆, by the triangle inequality, we have: 𝑔𝑝 (𝑥 ★) = ∥𝑥 ★ − 𝑝 ∥ ≤ ∥𝑥 ★ − 𝑦∥ + ∥𝑦 − 𝑝 ∥ = ∥𝑥 ★ − 𝑦∥ + 𝑔𝑝 (𝑦). (22) Rearranging terms yields 𝑔𝑝 (𝑥 ★) − 𝑔𝑝 (𝑦) ≤ ∥𝑥 ★ − 𝑦∥ Taking the minimum over 𝑦 ∈ 𝑆 on both sides gives 𝑔𝑝 (𝑥 ★) − min 𝑔𝑝 (𝑦) ≤ min ∥𝑥 ★ − 𝑦 ∥ 𝑦 ∈𝑆

𝑦 ∈𝑆

(23)

Using min𝑦 ∈𝑆 𝑔𝑝 (𝑦) = 𝜙 𝑝 (𝑆), we obtain: 𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆) ≤ min ∥𝑥 ★ − 𝑦 ∥ 𝑦 ∈𝑆

(24)

By the domination assumption (applied to 𝑥 ★ ∈ 𝑇 ), min𝑦 ∈𝑆 ∥𝑥 ★ − 𝑦 ∥ ≤ 𝐷 (𝑇 , 𝑆), hence: 𝜙 𝑝 (𝑇 ) − 𝜙 𝑝 (𝑆) ≤ 𝐷 (𝑇 , 𝑆)

(25)

Proof of Theorem 3.3

Theorem 3.3. The tightness-aware objective function 𝐹 (𝑃) is monotone and submodular. Let 𝑃 ★ be the optimal pivot set of size 𝑘, and let 𝑃𝑘 be the set returned by the greedy algorithm. Then, the greedy algorithm returns a pivot set whose objective value is guaranteed to be within a constant factor of the optimum, i.e., 𝐹 (𝑃𝑘 ) ≥ (1 − 1/𝑒) 𝐹 (𝑃 ★).

14

5DQGRPk 5DQGRP| |

+DUGQHVV 











   10 2



   





   















   10 2

+DUGk

')'







   





   















   10 2

+DUG| |

7LJKWQHVV 

'7:

 10 2



   





   





















  





  

generally achieves higher lower-bound tightness across all three distance measures, indicating stronger global lower-bound quality. In contrast, hardness-aware selection consistently produces tighter lower bounds on hard pairs, with the advantage becoming more pronounced as the pivot budget increases. These observations suggest that the two strategies optimize different aspects of representation quality. Tightness-aware selection emphasizes global lower-bound quality over the entire trajectory space, whereas hardness-aware selection prioritizes near-neighbor trajectory pairs that are more likely to influence retrieval rankings. As a result, tightness-aware selection is generally preferable when the objective is to maximize average lower-bound quality, while hardness-aware selection is more effective when the evaluation focuses on hard near-neighbor relationships. Interestingly, higher tightness on hard pairs does not necessarily translate into better retrieval performance. For example, on the Chengdu dataset (see Table 6), hardness-aware selection consistently achieves higher tightness on hard pairs, yet its HR@1 performance remains comparable to that of tightness-aware selection. This indicates that retrieval quality depends not only on lowerbound tightness, but also on whether the resulting lower-bound scores alter the relative ordering among the top-ranked candidates. Therefore, hardness-aware selection is most beneficial when improved tightness on hard pairs leads to meaningful ranking changes, whereas tightness-aware selection may remain competitive when the two strategies induce similar retrieval orderings.

+DXVGRUII

























Figure 5: Average lower-bound tightness of tightness-aware and hardness-aware pivot selection on Chengdu under DTW, DFD, and Hausdorff distance.

15

Related documents

• TrajTok: Adaptive Spatial Tokenization for Trajectory Representation Learning#204772
• TraVEL: Trajectory-Guided Video Embedding Learning for Driving-Video Retrieval#451285
• Geometric Characterisation and Structured Trajectory Surrogates for Clinical Dataset Condensation#126528
• Accurate trajectory inference in time-series spatial transcriptomics with structurally-constrained optimal transport#485115
• Representation learning methods for robotic perception and learning - at the intersection of computational neuroscience and machine learning.#489525